About

Elements of Scheduling

collected and edited by Jan Karel Lenstra and David B. Shmoys
19 December 2019; revised 20 September 2021

This website presents the fragments of a book on machine scheduling. Work on the book started in 1977 but was never completed. The existing material is now made available for teaching purposes.

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. What exists is now available on this website. We have made a marginal effort in patching it up at some places but essentially put it up as it was written long ago. We did make an attempt to include all of the citations in the bibliography.

We owe many thanks and apologies to our colleagues who contributed chapters that waited years to be published. We hope that the material, in spite of all the gaps and omissions that the reader will encounter, will serve a useful purpose.

We gratefully acknowledge the help of Shijiin Rajakrishnan (Cornell University) in formatting the chapters, of Michael Guravage (Centrum Wiskunde & Informatica) in realizing the website, of Lisa Lenstra (University of Amsterdam) in drawing the figures, and of Richard Shapley (Cornell University) in suggesting a number of corrections.

Below we review the status of each of the chapters and provide pointers to the pdf files.

PRELIMINARIES

1. Deterministic machine scheduling problems
Eugene L. Lawler, Jan Karel Lenstra, Alexander H.G. Rinnooy Kan, David B. Shmoys
Chapter 1 defines the class of scheduling problems under consideration and introduces the three-field classification. Notes and references are up to date until about 1990.

2. Tools from algorithms and complexity theory
David P. Williamson
Chapter 2 reviews the tools and concepts from combinatorial optimization that are useful in designing scheduling algorithms: linear programming, network flows, dynamic programming, polynomial-time solvability, NP-hardness, and techniques for coping with NP-hardness. Notes and references are up to date until about 1997.

THE SINGLE MACHINE

3. Minmax criteria
Eugene L. Lawler, Jan Karel Lenstra, David B. Shmoys
Chapter 3 considers two optimality criteria in a number of settings. For minimizing maximum cost, the focus is on polynomial-time optimization. For minimizing maximum lateness, the full spectrum of polynomial-time optimization, approximation and branch-and-bound is covered. Notes and references are up to date until 1992.

4. Weighted sum of completion times
Eugene L. Lawler, Maurice Queyranne, Andreas S. Schulz, David B. Shmoys
Chapter 4 centers around Smith’s ratio rule. It follows two threads of work: the extension of the rule to other objective functions and various kinds of precedence constraints, and the design of approximation algorithms for NP-hard variants with general precedence constraints or release dates. Notes and references cover work up to 2006.

5. Weighted number of late jobs
Eugene L. Lawler
Chapter 5 deals with various problems with the objective of minimizing the unweighted or weighted number of late jobs, with dynamic programming as a leitmotiv. Notes and references are up to date until about 1990.

6. Total tardiness and beyond
A draft describing the branch-and-bound methods of the 1970’s was made obsolete by later developments and never rewritten.

PARALLEL MACHINES

7. Minsum criteria
Eugene L. Lawler
Chapter 7 is a fragmented text, focusing on polynomial-time and pseudopolynomial-time optimization and providing pointers to results on NP-hardness, approximation and branch-and bound. Notes and references are up to date until about 1990.

8. Minmax criteria without preemption
David B. Shmoys, Jan Karel Lenstra
Chapter 8 is about the design and performance analysis of approximation algorithms, including impossibility results and a brief excursion into probabilistic analysis. Notes and references are up to date until 1992.

9. Minmax criteria with preemption
Eugene L. Lawler, Charles U. Martel
Chapter 9 again focuses on polynomial-time optimization, using techniques ranging from the wrap-around rule to linear programming. Notes and references are up to date until 1990.

10. Precedence constraints
This is the most glaring omission.

MULTI-OPERATION MODELS

11. Open shops
Gerhard J. Woeginger
Chapter 11 is based on a paper that was written for the 35th Symposium on Theoretical Aspects of Computer Science (2018). It deals with the minimization of makespan. A pivotal role is played by a vector sum theorem of Steinitz (1913). Many open problems are listed; exercises are missing. References are up to date until 2018.

12. Flow shops
Jan Karel Lenstra, David B. Shmoys
Chapter 12 discusses the design of approximation algorithms using Johnson’s 2-machine flow shop algorithm and the vector sum theorem, and briefly reviews the empirical performance of heuristics. The literature on branch-and-bound and on flow shops with no wait in process or limited buffers is not covered. Notes and references cover work up to 1990.

13. Job shops
Johann L. Hurink, Jan Karel Lenstra, David B. Shmoys
Chapter 13 consists of three sections, presenting the disjunctive graph model, heuristics based on schedule construction and local search, and an approximation result based on the vector sum theorem. The many detailed complexity results for special cases and the advances in branch-and-bound are not covered. References are up to date until 2001.

MORE SCHEDULING

14. Stochastic scheduling models
Michael L. Pinedo
Chapter 14 gives an overview of stochastic counterparts of the models considered in Chapters 3–13. Notes and references are missing.

15. Scheduling in practice
Michael L. Pinedo
Chapter 15 describes a diversity of practical applications of machine scheduling and discusses various aspects of scheduling systems. Figures and notes are missing.

BIBLIOGRAPHY

The bibliography consists of the literature cited in the 1993 survey, supplemented with the references in Chapters 1–15. Citations are collected in bibliographic notes at the end of each chapter.

The reader can download the surveys by Graham, Lawler, Lenstra, and Rinnooy Kan [1979] and Lawler, Lenstra, Rinnooy Kan, and Shmoys [1993], a paper in memory of Gene Lawler by Lenstra [1998], and a translation of an early paper on an informal approach to the complexity of scheduling problems by Livshits and Rublinetsky [1972].

BEYOND α|β|γ

The scheduling problems considered in Chapters 1–13 all fit in a three-field classification, with some minor exceptions. The reader will realize that the α|β|γ scheme only provides the skeleton of scheduling theory. Scheduling ‒ the field of allocating scarce resources to activities over time ‒ is much broader and allows for an unlimited number of variations of practical relevance and scientific interest. We present digressions into stochastic models and practical applications in Chapters 14 and 15. However, we do not cover nonmonotone and multiple criteria, communication delays, scheduling with fixed starting times and interval scheduling, additional resource constraints and project scheduling, timetabling, multi-operation models with parallel machines at each stage, online algorithms and competitive analysis, machine learning and connections to data science ‒ and much more.