Scheduling Theory

Contents

The textbook was worse than useless, so I wrote these very concise notes for a course I taught as a grad student. I never did get around to writing part 2.

• 1 Machine Scheduling
• 1.1 Definitions
• 1.1.1 Given Parameters
• 1.1.2 Schedule Values
• 1.1.3 Flowshops and Jobshops
• 1.1.4 Idle Time
• 1.1.5 Preemption
• 1.1.6 Processor Sharing
• 1.1.7 Permutation Schedules
• 1.2 Finding Optimal Schedules
• 1.2.1 Adjacent Interchange Proof, Example
• 1.2.2 Regular Functions
• 1.3 Due Dates
• 1.3.1 Minimizing Mean Lateness
• 1.3.2 Minimizing Maximum Lateness (and Tardiness)
• 1.3.3 Maximizing Minimum Lateness
• 1.3.4 Secondary Measures of Performance
• 1.3.5 Minimizing the Number of Tardy Jobs
• 1.4 Ready Dates
• 1.4.1 Dispatching Rules
• 1.4.2 Minimizing Mean Lateness
• 1.4.3 Minimizing Maximum Lateness
• 1.5 Precedence Constraints
• 1.5.1 Strings
• 1.5.2 Minimizing Maximum Lateness
• 1.5.3 Minimizing Mean Weighted Flow Time
• 1.6 Setup Times
• 1.6.1 Heuristic Solution
• 1.6.2 Branch and Bound Method
• 1.6.3 Branch and Bound Solution
• 1.7 Parallel Machines
• 1.7.1 Minimizing Makespan
• 1.7.2 Minimizing Mean Flowtime
• 1.7.3 Minimizing Makespan with Precedence Constraints
• 1.8 Serial Machines (Flowshops)
• 1.8.1 Dominance Conditions
• 1.8.2 Two Machine Flowshops
• 1.8.3 Special Models