Skip to content
Tutorials Center
My learning

Topics

Lesson 28 of 38 ยท Scheduling and Queueing

Scheduling Basics and Dispatch Rules

Learn scheduling vocabulary and optimal dispatch rules: SPT, EDD, weighted SPT, Moore-Hodgson and Johnson's rule for two-machine flow shops, checked with brute force in Python.

Scheduling is the art of deciding who does what, when, and on which resource. Factories schedule jobs on machines, hospitals schedule operations in theaters, cloud systems schedule tasks on servers, and teachers schedule exams in rooms. The goal is some measure of performance: finish early, meet due dates, keep machines busy.

Scheduling problems are classified by a short notation, but the basic ideas are simple. This lesson covers the vocabulary and a set of famous dispatch rules: simple sorting recipes that are provably optimal for particular objectives. Later lessons deal with harder cases using a critical path analysis and MILP models.

Vocabulary

For job j:

  • p_j processing time, r_j release time (when it becomes available), d_j due date, w_j weight (importance).
  • C_j completion time, the moment the job finishes.
  • F_j = C_j - r_j flow time, the total time in the system.
  • L_j = C_j - d_j lateness (may be negative), T_j = max(0, L_j) tardiness.

Common objectives:

Objective Meaning
Makespan C_max Time when the last job finishes
Total (or mean) completion time sum C_j Average waiting plus processing
Total weighted completion sum w_j C_j Same with priorities
Maximum lateness L_max Worst violation of a due date
Total tardiness sum T_j Total lateness penalty
Number of tardy jobs sum U_j How many jobs miss their date

In the single-machine model, one machine processes one job at a time without interruption. For this model, a schedule is just an ordering of the jobs, so there are n! possibilities. Despite that, the best order is easy to find for many objectives.

flowchart TD
    Q{"Objective?"} -->|"min average completion"| SPT["SPT: shortest processing time first"]
    Q -->|"min weighted completion"| WSPT["Smith: sort by p/w ascending"]
    Q -->|"min maximum lateness"| EDD["EDD: earliest due date first"]
    Q -->|"min number of tardy jobs"| MH["Moore-Hodgson algorithm"]
    Q -->|"two-machine flow shop makespan"| J["Johnson's rule"]

SPT, Smith's rule and EDD

  • SPT (shortest processing time first) minimizes the mean completion time sum C_j. Reason: a job's processing time delays every job after it, so short jobs should go first.
  • Smith's rule (WSPT) orders jobs by increasing p_j / w_j, which minimizes sum w_j C_j. SPT is the special case of equal weights.
  • EDD (earliest due date first) minimizes L_max (and also T_max).

Each can be proved with an exchange argument: if two adjacent jobs are in the wrong order, swapping them cannot make things worse, so a sorted order cannot be beaten.

Python Checking dispatch rules against all orderings

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For each objective the rule matches the minimum found by trying all 120 orders, but the rule needs only a sort: O(n log n).

Number of tardy jobs: Moore-Hodgson

Minimizing how many jobs miss their due date is solved by the Moore-Hodgson algorithm:

  1. Sort jobs by EDD and add them to the schedule one at a time.
  2. If adding job j makes it late, remove the longest job so far from the schedule (it becomes tardy), which shortens the sequence.
  3. At the end, the jobs kept form an on-time set; the removed ones are scheduled last, and they are late.
Python Moore-Hodgson: fewest late jobs

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Two machines in series: Johnson's rule

In a flow shop, every job visits machine 1 and then machine 2. We want the smallest makespan. Johnson's rule for two machines gives the optimum:

  1. List jobs with p1 <= p2 (faster on machine 1), sorted by increasing p1, first.
  2. Then list jobs with p1 > p2, sorted by decreasing p2, last.

The idea is to feed machine 2 early (short first-machine times at the front) and to finish with jobs that leave machine 2 busy only briefly.

Python Johnson's rule and a text Gantt chart

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Digits in the chart mark which job is running; blanks are idle time. Johnson's order finishes at the same time as the best of all 120 permutations.

Where the easy rules end

The nice results above are for special cases. Adding almost anything makes problems NP-hard: release times with total completion time, total tardiness sum T_j, three machines in a flow shop, or job-shop routing. For those you need integer programming, branch and bound, or heuristics such as local search. Real-time systems also use priority dispatching (rate-monotonic, earliest deadline first) that follows the same logic.

Before building a big model, check whether a classical rule gives the exact answer. A sort beats a solver in speed and in clarity.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which rule minimizes the average completion time on a single machine?

    Each job's processing time delays all later jobs, so putting short jobs first minimizes total completion time.
  2. 2. Smith's rule orders jobs by increasing which ratio?

    Sorting by p/w (equivalently decreasing w/p) minimizes the weighted sum of completion times.
  3. 3. What does EDD minimize on one machine?

    EDD is optimal for L_max. Makespan is the same for every order on one machine with no idle time.
  4. 4. In Johnson's rule, where do jobs with p1 <= p2 go?

    Short first operations start machine 2 early; jobs that are longer on machine 1 go last, sorted by decreasing p2.

Summary

  • Scheduling assigns jobs to resources over time; common measures are makespan, completion time, lateness, tardiness and tardy-job count.
  • On one machine, SPT, Smith's rule and EDD are optimal for total completion, weighted completion and maximum lateness; Moore-Hodgson minimizes tardy jobs.
  • Johnson's rule gives optimal two-machine flow-shop schedules.
  • Exchange arguments prove these rules; brute force on small instances is a good check.
  • More general problems are NP-hard and need integer programming or heuristics.

Next: Critical Path Method