Lenstra, Machine scheduling with precedence constraints, NATO Adv. Discrete Math., 2 ( 1978), 75–90, Algorithmic aspects of combinatorics (Conf., Vancouver Island, B.C., 1976) 58:13890 Crossref Google Scholar Lawler, Sequencing jobs to minimize total weighted completion time subject to precedence constraints, Ann. Isaacs, Bounds for the optimal scheduling of n jobs on m processors, Management Sci., 11 ( 1964/1965), 268–279 30:3760 Crossref ISI Google Scholar 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. In the course of our proof it is helpful to use what might be called two-dimensional (2D) Gantt charts. 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. We do this by using a linear programming formulation of $1 | prec | \sum_j w_j C_j$ introduced by Queyranne and Wang.
In this note we give an alternate proof that a scheduling algorithm of Lawler finds the optimal solution for the scheduling problem $1 | prec | \sum_j w_j C_j$ when the precedence constraints are series-parallel.
0 kommentar(er)
