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

Andreas S. Schulz (schulzmit.edu)
Nelson A. Uhan (nuhanpurdue.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. This NP-hard scheduling problem can be equivalently viewed as a graph orientation problem on a mixed complete bipartite graph. For various probability distributions over these instances--including the uniform distribution--we show several "almost all"-type results, including that for almost all instances, every feasible solution is arbitrarily close to optimal. To the best of our knowledge, our results are the first of their kind for scheduling and graph orientation problems.

Keywords:

Category 1: Combinatorial Optimization

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

Citation: Working Paper, August 2008. Revised February 2009, May 2009.

Download: [PDF]

Entry Submitted: 08/21/2008
Entry Accepted: 08/22/2008
Entry Last Modified: 05/03/2009

Modify/Update this entry