#### 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 oﬀered by the ﬁeld. 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 ﬁnite 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 eﬀort 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 ﬁles.

##### PRELIMINARIES

1. **Deterministic machine scheduling problems**

*Eugene L. Lawler, Jan Karel Lenstra, Alexander H.G. Rinnooy Kan,
David B. Shmoys*

Chapter 1 deﬁnes the class of scheduling
problems under consideration and introduces the three-ﬁeld
classiﬁcation. 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 ﬂows, 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 ﬂow shop algorithm
and the vector sum theorem, and brieﬂy reviews the empirical
performance of heuristics. The literature on branch-and-bound and on
ﬂow 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-ﬁeld classiﬁcation, 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.