Parallel machine scheduling, linear programming, and parameter list scheduling heuristics
成果类型：
Article
署名作者：
Chan, LMA; Muriel, A; Simchi-Levi, D
署名单位：
University of Toronto; University of Michigan System; University of Michigan; Northwestern University
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.46.5.729
发表日期：
1998
页码：
729-741
关键词：
摘要：
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.