Two-dimensional Gantt charts and a scheduling algorithm of Lawler

摘要

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 Sigma(j) w(j)C(j) when the precedence constraints are series-parallel. We do this by using a linear programming formulation of 1precSigma(j) w(j)C(j) 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.