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 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 7 Minsum criteria
Chapter 8 Minmax criteria without preemption
Chapter 9 Minmax criteria with preemption

MULTI-OPERATION MODELS

Chapter 11 Open shops
Chapter 12 Flow shops
Chapter 13 Job shops

MORE SCHEDULING

Chapter 14 Stochastic scheduling models
Chapter 15 Scheduling in practice

BIBLIOGRAPHY

Bibliography

SURVEY PAPERS

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

MORE PAPERS

Livshits and Rublinetsky [1972]
Lenstra [1998]