Near-Optimal Solutions and Integrality Gaps for Almost All Instances of Single-Machine Precedence-Constrained Scheduling
<-- Return to the list
Date: 09-23-2008
Start Time:
1:00pm
End Time: 2:00pm
Speaker: Andreas Schulz, Sloan School of Management: Massachusetts Institute of Technology
Location: Uris 333
ABSTRACT
We consider the problem of minimizing the total waiting cost 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, or as a special case of the vertex cover problem. This scheduling 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.
BIO
Andreas S. Schulz is Associate Professor of Mathematics of Operations Research at the Sloan Sloan of Management. He received his doctorate in Mathematics from the Technische Universität Berlin. He has been on the M.I.T. faculty since 1998, and he has held visiting appointments at the Swiss Federal Institute of Technology Zurich and at Maastricht University in the Netherlands. He is best known for his works on polyhedral characterizations and approximation algorithms for scheduling problems, on the complexity of 0/1-integer programming and 0/1-polytopes, and on the price of anarchy in network games. In 2000, he was elected founding member of "Die Junge Akademie" of the Berlin-Brandenburg Academy of Sciences and Humanities and the Academy of Natural Scientists Leopoldina. Other awards include the Glover-Klingman Prize for the best paper published in the journal Networks during 2006 for the paper "Efficiency and Fairness of System-Optimal Routing with User Constraints," which he coauthored with his former PhD student Nicolas Stier Moses, an excellence-in-teaching award from Sloan's MBA program, the Class of 1958 Career Development Chair, which recognizes and encourages innovative and imaginative teaching by gifted junior faculty members, and the Dissertation Prize of the German Society for Mathematics, Economics, and Operations Research. He organized IPCO IX, the Ninth International Conference on Integer Programming and Combinatorial Optimization, and he is one of three members of the IPCO steering committee. He also is a council member of the Mathematical Programming Society. He has been on the editorial boards of several journals, including ACM Transactions on Algorithms, Algorithmic Operations Research, Discrete Optimization, INFORMS Journal on Computing, Journal of Scheduling, Naval Research Logistics, and Operations Research.