Otto-von-Guericke-Universität Magdeburg



by Kravchenko, S.A.; Werner, F.


Preprint series: 08-13, Preprints

The paper is published: Computers & Operations Research, Vol. 36, No. 10, 2009, 2816 - 2821 (under the title: Preemptive Scheduling on Uniform Machines to Minimize Mean Flow Time)

90B35 Scheduling theory, See also {68M20}


Abstract: In this paper we give a polynomial algorithm for the preemptive scheduling problem on uniform machines with given release dates, equal processing times and minimizing mean flow time whose complexity status was open yet. The algorithm is based on a reduction of the scheduling problem to a linear program. The crucial condition for implementing the proposed reduction is the known order of job completion times.

Keywords: Parallel uniform machines, Linear programming, Maximum flow, Polynomial algorithm

The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.

Letzte Änderung: 10.02.2016 - Ansprechpartner: Pierre Krenzlin