Two-dimensional Gantt charts and a scheduling algorithm of Lawler

Michel X. Goemans () and David P. Williamson ()
Additional contact information
Michel X. Goemans: Center for Operations Research and Econometrics (CORE), Université catholique de Louvain (UCL), Louvain la Neuve, Belgium
David P. Williamson: IBM T.J. Watson Research Center, Yorktown Heights, New York

No 1998001, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: 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

Date: 1998-01-01
References: Add references at CitEc
Citations:

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp1998.html (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:1998001

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().