Zurück zu den Preprints des Jahres 1998


1998-13

On Preemptive Scheduling on Uniform Machines to Minimize Mean Flow Time

by Kravchenko, S., Werner, F..


Series: 1998-13, Preprints

MSC:
90B35 Scheduling theory, deterministic

Abstract:
In this paper we give a polynomial algorithm for problem
Q|r_j, p_j=p, pmtn | \sum C_j 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