08-13
On Preemptive Scheduling on Uniform Machines to Minimize Mean Flow Time
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)
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.