98-13

On Preemptive Scheduling on Uniform Machines to Minimize Mean Flow Time

by Kravchenko, S.; Werner, F.

 

Preprint series: 98-13, Preprints

MSC:
90B35 Scheduling theory, See also {68M20}

 

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


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

Letzte Änderung: 01.03.2018 - Ansprechpartner: Webmaster