by Kravchenko, S.A., Werner, F..
Series: 2008-13, Preprints
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.
Parallel uniform machines, Linear programming, Maximum flow, Polynomial algorithm
This paper was published in:
Computers & Operations Research, Vol. 36, No. 10, 2009, 2816 - 2821 (under the title: Preemptive Scheduling on Uniform Machines to Minimize Mean Flow Time)