Zurück zu den Preprints des Jahres 2008


2008-13

On Preemptive Scheduling on Uniform Machines to Minimize Mean Flow Time

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


Series: 2008-13, Preprints

MSC:
90B35 Scheduling theory, deterministic

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

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)