Parallel Machine Scheduling, Linear Programming, and Parameter List Scheduling Heuristics

Lap Mui Ann Chan, Ana Muriel and David Simchi-Levi
Additional contact information
Lap Mui Ann Chan: University of Toronto, Ontario, Canada
Ana Muriel: University of Michigan, Ann Arbor, Michigan
David Simchi-Levi: Northwestern University, Chicago, Illinois

Operations Research, 1998, vol. 46, issue 5, 729-741

Abstract: In this paper we consider a class of parallel machine scheduling problems and their associated set-partitioning formulations. We show that the tightness of the linear programming relaxation of these formulations is directly related to the performance of a class of heuristics called parameter list scheduling heuristics. This makes it possible to characterize the worst possible gap between optimal solutions for the scheduling problems and the corresponding linear programming relaxations. In the case of the classical parallel machine weighted completion time model we also show that the solution to the linear programming relaxation of the set-partitioning formulation is asymptotically optimal under mild assumptions on the distribution of job weights and processing times. Finally, we extend most of the results to the time-discretized formulation of machine scheduling problems.

Keywords: Scheduling; deterministic; single machine; Programming; integer; set-partitioning; Analysis of algorithms; worst-case and probabilistic analysis (search for similar items in EconPapers)
Date: 1998
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.46.5.729 (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:46:y:1998:i:5:p:729-741

Access Statistics for this article

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