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 scheduling problem can be equivalently viewed as a graph orientation problem on a mixed complete bipartite graph. This problem is strongly NP-hard, and---despite considerable effort---no approximation algorithm with a performance guarantee better than 2 is known. By using well-established models from random graph theory, we are able to 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 its kind for scheduling problems. As a first step, we show that almost all instances of this scheduling problem are non-Sidney-decomposable. This implies that the divide-and-conquer approach proposed by Sidney (1975) will almost never help in solving this problem. It also implies, together with earlier results of Chekuri and Motwani (1999), Margot, Queyranne, and Wang (2003), and Goemans and Williamson (2000), that for almost all instances, the objective value of every feasible schedule is within a factor of 2 of the optimum. Using two-dimensional Gantt charts, we then show the much stronger result mentioned above: for any \epsilon > 0, the probability of a random instance having the property that every feasible schedule's objective value is within a factor of 1 + \epsilon of the optimum tends to 1 as the number of jobs goes to infinity. In contrast, we also give non-trivial lower bounds on the integrality gaps of various well-studied linear programming relaxations for this scheduling problem, for almost all instances.

Keywords:

Category 1: Combinatorial Optimization

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

Citation: Working Paper, August 2008.

Download: [PDF]

Entry Submitted: 08/21/2008
Entry Accepted: 08/22/2008
Entry Last Modified: 08/21/2008

Modify/Update this entry