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.

PRELIMINARIES

Chapter 1 Deterministic machine scheduling problems
Chapter 2 Tools from algorithms and complexity theory

THE SINGLE MACHINE

Chapter 3 Minmax criteria
Chapter 4 Weighted sum of completion times
Chapter 5 Weighted number of late jobs

PARALLEL MACHINES

Chapter 8 Minsum criteria
Chapter 9 Minmax criteria, no preemption
Chapter 10 Minmax criteria with preemption

MULTI-OPERATION MODELS

Chapter 12 Open shops
Chapter 13 Flow shops
Chapter 14 Job shops

MORE SCHEDULING

Chapter 15 Stochastic scheduling models
Chapter 16 Scheduling in practice

BIBLIOGRAPHY

Bibliography

SURVEY PAPERS

Graham, Lawler, Lenstra, and Rinnooy Kan [1979]
Lawler, Lenstra, Rinnooy Kan, and Shmoys [1993]
Lenstra [1998]