#### Elements of Scheduling

collected and edited by Jan Karel Lenstra and David B. Shmoys

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 ﬁ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 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 most 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.

The help of Michael Guravage (Centrum Wiskunde & Informatica) and Shijiin Rajakrishnan (Cornell University) in formatting the chapters and realizing the website is gratefully acknowledged.

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.

7. **Nonmonotonic and multiple criteria**

This is another blank spot.

##### PARALLEL MACHINES

8. **Minsum criteria**

*Eugene L. Lawler*

Chapter 8 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.

9. **Minmax criteria, no preemption**

*David B. Shmoys, Jan Karel Lenstra*

Chapter 9 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.

10. **Minmax criteria with preemption**

*Eugene L. Lawler, Charles U. Martel*

Chapter 10 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.

11. **Precedence constraints**

This is the most glaring omission.

##### MULTI-OPERATION MODELS

12. **Open shops**

*Gerhard J. Woeginger*

Chapter 12 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 in nonpreemptive open shops. A pivotal role
is played by a vector sum theorem of Steinitz (1913). Many open
problems are listed. References are up to date until 2018.

13. **Flow shops**

*Jan Karel Lenstra, David B. Shmoys*

Chapter 13 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.

14. **Job shops**

*Johann L. Hurink, Jan Karel Lenstra, David B. Shmoys*

Chapter 14 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

15. **Stochastic scheduling models**

*Michael L. Pinedo*

Chapter 15 gives an overview of stochastic counterparts of the models
considered in Chapters 3–14. Notes and references are missing.

16. **Scheduling in practice**

*Michael L. Pinedo*

Chapter 16 describes a diversity of practical applications of machine
scheduling and discusses various aspects of scheduling
systems. Figures, notes and references are missing.

##### BIBLIOGRAPHY

The bibliography consists of the literature cited in the 1993 survey, supplemented with the references in Chapters 1–5, 8‒10, 12‒14. Citations are collected in bibliographic notes at the end of each chapter, with the exception of Chapters 12 and 14, where they occur in the main text.

The reader can download the surveys by Graham, Lawler, Lenstra, and Rinnooy Kan [1979] and Lawler, Lenstra, Rinnooy Kan, and Shmoys[1993], and a paper in memory of Gene Lawler by Lenstra [1998].