Strongly Polynomial Algorithms for the High Multiplicity Scheduling Problem

Dorit S. Hochbaum and Ron Shamir
Additional contact information
Dorit S. Hochbaum: University of California, Berkeley, California
Ron Shamir: Rutgers University, Piscataway, New Jersey

Operations Research, 1991, vol. 39, issue 4, 648-653

Abstract: A high multiplicity scheduling problem consists of many jobs which can be partitioned into relatively few groups, where all the jobs within each group are identical. Polynomial, and even strongly polynomial, algorithms for the standard scheduling problem, in which all jobs are assumed to be distinct, become exponential for the corresponding high multiplicity problem. In this paper, we study various high multiplicity problems of scheduling unit-time jobs on a single machine. We provide strongly polynomial algorithms for constructing optimal schedules with respect to several measures of efficiency (completion time, lateness, tardiness, the number of tardy jobs and their weighted counterparts). The algorithms require a number of operations that are polynomial in the number of groups rather than in the total number of jobs. As a by-product, we identify a new family of nxn transportation problems which are solvable in O ( n log n ) time by a simple greedy algorithm.

Keywords: computers/computer science: strongly polynomial algorithms; networks/graphs; flow algorithms: greedy algorithms for transportation; production/scheduling: sequencing; deterministic; single machine (search for similar items in EconPapers)
Date: 1991
References: Add references at CitEc
Citations: View citations in EconPapers (17)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.39.4.648 (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:oropre:v:39:y:1991:i:4:p:648-653

Access Statistics for this article

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