Preemptive Scheduling of Uniform Machines by Ordinary Network Flow Techniques

A. Federgruen and H. Groenevelt
Additional contact information
A. Federgruen: Graduate School of Business, Columbia University, New York, New York 10027
H. Groenevelt: Graduate School of Management, University of Rochester, Rochester, New York 14627

Management Science, 1986, vol. 32, issue 3, 341-349

Abstract: We consider the problem of scheduling n jobs, each with a specific processing requirement, release time and due date on m uniform parallel machines. It is shown that a feasible schedule can be obtained by determining the maximum flow in a network, thus permitting the use of standard network flow codes. Using a specialized maximum flow procedure, the complexity reduces to O(tn 3 ) operations when t is the number of distinct machine types. Previous algorithms solve the feasibility problem in O((m + log n)(m 2 n 3 + n 4 )) operations. In addition to the feasibility problem, we describe algorithms for the maximum lateness criterion. Here we develop a bound which compares even more favorably to the best previous bound. We also show how other criteria with respect to the amount of work completed on each job prior to its due date or the amount of work scheduled in each of a sequence of periods can be optimized by similar path augmenting techniques.

Keywords: preemptive scheduling; polymatroidal network flow; network flow (search for similar items in EconPapers)
Date: 1986
References: Add references at CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.32.3.341 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:32:y:1986:i:3:p:341-349

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().