Two-Dimensional Gantt Charts and a Scheduling Algorithm of Lawler

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. We do this by using a linear programming formulation due
to Queyranne and Wang. 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 is an alternate proof of this fact.

By: Michel X. Goemans and David P. Williamson

Published in: RC21032 in 1997

LIMITED DISTRIBUTION NOTICE:

This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.

8747.ps.gz