Two-dimensional Gantt charts and a scheduling algorithm of Lawler

In this note we give an alternate proof that a scheduling algorithm of Lawler [3,4] finds the optimal solution for 1 / prec / SIGMAj wj Cj when the precedence constraints are series-parallel. We do this by using a linear programming formulation of 1 / prec / SIGMAj wj Cj introduced by Queyranne and Wang [10]. Queyranne and Wang proved that their formulation completely describes the scheduling polyhedron in the case of series-parallel constraints; a by-product of our proof of correctness of Lawler’s algorithm is an alternate proof of this fact. In the course of our proof it is helpful to use what might be called two-dimensional Gantt charts. We think these may find independent use, and to illustrate this we show that some recent work in the area becomes transparent using 2D Gantt charts