Optimization Online


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

Andreas S. Schulz (schulz***at***mit.edu)
Nelson A. Uhan (nuhan***at***purdue.edu)

Abstract: We consider the problem of minimizing the weighted sum of completion times on a single machine subject to bipartite precedence constraints where 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.


Category 1: Combinatorial Optimization

Category 2: Applications -- OR and Management Sciences (Scheduling )

Citation: Mathematics of Operations Research, to appear, 2011. DOI: 10.1287/moor.1100.0479


Entry Submitted: 08/21/2008
Entry Accepted: 08/22/2008
Entry Last Modified: 02/03/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society