Two-Dimensional Gantt Charts

Michel Goemans
Associate Professor of Applied Mathematics
MIT

In this talk, we show the usefulness of 2-dimensional Gantt charts to tackle machine scheduling problems in which the goal is to minimize a weighted sum of completion times. As an appetizer, we describe how simple results such as Smith's rule and more recent work in the area are easily understood by 2-dimensional Gantt charts. Our main course is a restatement(in terms of 2-d Gantt charts) of Lawler's algorithm for optimally scheduling jobs on one machine under series-parallel constraints to minimize a weighted sum of completion times. This gives a fairly simple duality-based proof of its correctness using a linear programming relaxation introduced by Queyranne and Wang. This is joint work with David Williamson.