Two-dimensional gantt charts and a scheduling algorithm of lawler

Abstract

In this note we give an alternate proof that a scheduling algorithm of Lawler [E. L. Lawler, Ann. Discrete Math., 2 (1978), pp. 75-90, E.L. Lawler and J.K. Lenstra, in Ordered Sets, I. Rival, ed., D. Reidel, 1982, pp. 655-675] finds the optimal solution for the scheduling problem 1|prec| ∑j w3C3 when the precedence constraints are series-parallel. We do this by using a linear programming formulation of 1|prec| ∑j w3C3 introduced by Queyranne and Wang [Math. Oper. Res., 16 (1991), pp. 1-20]. 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 (2D) 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.