Job Scheduling Lab.
Seven jobs are waiting for one machine, and each one has a due date. Every time the machine switches to a different type of job, it loses an hour to setup. Try a few simple rules, like running whatever is due soonest, and see which jobs finish late. Then compare them with the very best order, which the lab finds by checking all 5,040 possible orders. You can also build your own order and see where it ranks.
What order should the jobs run in?
job type X / Y / Z (tall / mid / low) 1 h setup when the type changes due date hours lateone row per job, sorted by due date · the strip along the time axis is the machine
Due date first (EDD) always runs the job that’s due soonest. Without setups, that keeps the worst lateness of any one job as small as it can be. Here it switches job type after every job, adding 6 h of setup and pushing the finish to 27 h. Jobs end up 18 h late in total: score 104.7, rank 183 of 5,040. Try Best possible to see what you gain by grouping jobs of the same type.
Choose an order
Earliest due date first: the job due soonest always runs next.
Run order
- #1BY · 0–2 hdue 7
- #2Aafter a 1 h setup,X · 3–7 hdue 8
- #3Dafter a 1 h setup,Z · 8–11 hdue 11
- #4Gafter a 1 h setup,X · 12–13 h+1 h late
- #5Eafter a 1 h setup,Y · 14–16 h+2 h late
- #6Cafter a 1 h setup,X · 17–22 h+7 h late
- #7Fafter a 1 h setup,Z · 23–27 h+8 h late
Score by order · lower is better
| Order | Score | vs best | Rank | Standing | Late | Setups | Finish |
|---|---|---|---|---|---|---|---|
| 179.7 | +108.4 | 2,731 | bottom 45.8% | 33 h | 6 | 27 h | |
| 104.7 | +33.4 | 183 | top 3.7% | 18 h | 6 | 27 h | |
| 107.6 | +36.3 | 219 | top 4.6% | 19 h | 5 | 26 h | |
| 71.3 | 0 | 1 | top 0.04% | 13 h | 2 | 23 h | |
| not built yet | |||||||
Score = 5 × hours late + 2 × setups + 0.1 × finish time, so lateness counts the most. Rank is one more than the number of orders that score lower, so tied orders share a rank. Standing: “top x%” means x% of all 5,040 orders score the same or lower. Past the middle (the median), it flips to “bottom x%”, the share that score the same or higher.
All 5,040 possible orders, each one scored
Across: the score (lower is better), grouped in 5-point bins. Up: how many orders land in each bin. Any bin with orders is drawn at least 2 px tall, so you can see it. Best 71.3, median 174.7, worst 289.7.
How the model works, how it’s checked and what it leaves out
How it works
One machine and seven jobs, all ready at hour 0. The jobs run back to back. Once a job starts it isn’t interrupted, and the machine never sits idle. Whenever the next job is a different type (a different “family”), a one-hour setup goes in between. The first job needs none.
Each job’s finish time Cj adds up all the work and setup hours so far. Its lateness (tardiness) is Tj = max(0, Cj − dj), where dj is its due date. So a job that finishes early counts as 0 hours late, not less. The score (the “objective”) is 5 × ΣTj + 2 × setups + 0.1 × makespan. ΣTj is the total hours late, and the makespan is when the last job finishes. Scores are stored in whole tenths, so ties and ranks are exact.
FIFO uses the listed order. EDD sorts by due date and SPT by job length, with ties kept in listed order. EXACT scores all 7! = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5,040 orders and keeps the lowest. When several tie, the one that comes first in alphabetical order wins (2 orders tie here). In Build your own, the best way to finish your order is found by searching that same full list.
How it’s checked
EXACT’s score equals the lowest of all 5,040 scored orders, and no rule or order of yours can beat it. Every schedule has each job exactly once, starts at hour 0 and only has a setup gap when the job type changes. So the finish time is always 21 h of work plus the setup hours. The bars in the chart add up to 5,040 orders.
Once you’ve placed the first k jobs, there are (7 − k)! ways to finish. The best score still in reach can only stay the same or rise as you add jobs, and it ends at your order’s own score. FIFO, EDD and SPT score 179.7, 104.7 and 107.6, against the best possible 71.3. You can check FIFO by hand: the listed order switches job type at every step, so it has 6 setups and finishes at 27 h. Late jobs: D 6 h, E 6 h, F 6 h and G 15 h, 33 h in all. Score: 5 × 33 + 2 × 6 + 0.1 × 27 = 179.7.
What it leaves out
Real jobs don’t all arrive at the start, and some can’t begin until another job is done. Machines break down, and a shop may have more than one machine. Setup times can depend on which two job types you switch between, and job lengths are rarely known exactly. This lab leaves all of that out.
Checking every order also blows up fast: 10 jobs means 3.6 million orders, and 15 jobs means 1.3 trillion. Bigger problems need smarter solvers, like CP-SAT or mixed-integer programming. They can rule out huge batches of bad orders without checking each one. Another option is a tested shortcut (a heuristic) paired with a bound that shows how far from the best it could be.