Elements of Scheduling

Abstract

In the winter of 1976, Alexander Rinnooy Kan and Jan Karel Lenstra defended their PhD theses at the University of Amsterdam. Gene Lawler was on their committees. It was a natural idea to turn the theses into a textbook on scheduling. They set out to compile a survey with Ron Graham (1979), but progress on the book was hampered by the many research opportunities offered by the field. After David Shmoys joined the team in the mid 1980's, several chapters were drafted, and the survey was rewritten (1993). Gene passed away in 1994. Colleagues were asked to contribute chapters or to complete existing drafts. However, by the turn of the century the project was losing its momentum, and finite convergence to completion fell beyond our reach. Over the years, several chapters have been used in the classroom. We continue to receive requests from colleagues who look for a text on the elements of scheduling at an advanced undergraduate or early graduate level. This document is a compilation of what currently exists. We have made a marginal effort in patching it up at some places but is essentially what was written long ago. We did make an attempt to include most of the citations in the bibliography.