A Book on Scheduling
This is a project page, the files found here are preliniary versions of chapters of a textbook I am currently writing. It is one more book about scheduling theory.
The book is an introductory text intended for undergraduate
students. It originates from a series of lecture notes I have
prepared over the last few years for my two-semester courses on
combinatorial optimization and queueing theory.
It will consist of two parts:
- Deterministic Scheduling
- Stochastic Scheduling
For Part I no special prerequisites are needed, Part II expects from
students a basic education in calculus and probability theory.
Part I - Deterministic Scheduling
Chapter 1: Managing Time and Resources
Basic ideas of deterministic scheduling are introduced, using as running example the famous bicylce problem of Ronald Graham.
This chapter has not been finished so far.
Chapter 2: Basic Manoeuvers: Scheduling a Single Server
Overview:
- The model and its assumptions
- The schedule and its outcome
- Performance measures
- Total completion time
The WSPT-rule - complexity and ties - variability of completion
times and waiting times
- Lateness
Due dates and delivery times - total weighted lateness - maximum
lateness - Lawler's Algorithm
- Tardiness - A first glimpse
Maximum tardiness - the number of tardy job - a graphical
device - Moore-Hodgeson Algorithm
- Secondary measures of performance
Current version:
Chapter 3: Elements of Graph Theory
Overview:
- A basic vocabulary
Graphs as binary relations - some examples - a useful mapping
- Some important graphs
Complete graphs - bipartite graphs - interval
graphs
- Basic operations on graphs
Deleting nodes and edges - union, difference and
complement
- Subgraphs, cliques and co
Subgraphs - cliques - stable sets - matchings - modules
- Chains, paths, cycles and connectivity
- Acyclic graphs, trees
- Data structures for graphs
Adjacency matrix and adjacency list - numerical
attributes
- Exploring a graph
Depth-first search -- finding cycles
- Precedence graphs
Partial orders - linear extensions and topological
ordering
- SP-Graphs
Series and parallel composition - the decomposition tree
- Vertex coloring
A greedy algorithm - coloring of interval graphs
- Bibliographic Notes
Current version:
Chapter 4: Three Work horses: DP, B&B and IP
Chapter 5: It's order that matters - dependent jobs
Chapter 6: More on tardiness
Chapter 7: Not too late and not too early - E/T-scheduling
Chapter 8: One after the other - release dates and online scheduling
Comments are always welcome!