Near-Optimal Solutions and Large Integrality Gaps for Almost All Instances of Single-Machine Precedence-Constrained Scheduling

• 成果类型: Article
• 署名作者: Schulz, Andreas S.; Uhan, Nelson A.
• 署名单位: Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); Purdue University System; Purdue University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1100.0479
• 发表日期: 2011
• 页码: 14-23
• 关键词: algorithm; network; jobs

摘要

We consider the problem of minimizing the weighted sum of completion times on a single machine subject to bipartite precedence constraints in which all minimal jobs have unit processing time and zero weight, and all maximal jobs have zero processing time and unit weight. For various probability distributions over these instances-including the uniform distribution-we show several almost all-type results. First, we show that almost all instances are prime with respect to a well-studied decomposition for this scheduling problem. Second, we show that for almost all instances, every feasible schedule is arbitrarily close to optimal. Finally, for almost all instances, we give a lower bound on the integrality gap of various linear programming relaxations of this problem.