Scheduling: Rules of Thumb vs Checking Every Order

The problem

Picture one machine with seven jobs waiting for it. Each job takes a known number of hours and has a due date. The jobs come in three types. Switching the machine from one type to another costs an hour of setup. The order I pick decides which jobs finish late, and how many hours go to setup instead of real work.

Lots of shops pick the order with a rule of thumb, called a dispatch rule. First in, first out (FIFO) runs jobs in the order they showed up. Earliest due date (EDD) runs whichever job is due soonest. Shortest processing time (SPT) runs the quickest job first. The other option is to score every possible order and keep the best one. Seven jobs can be lined up in 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5,040 ways. That’s written 7! (say “seven factorial”). It’s few enough that a browser can check them all.

On this small problem, the rules of thumb fall well short. The lab gives each order one score, and lower is better. The score mostly counts hours late, plus a smaller charge for each setup. First in, first out leaves 33 hours of lateness. The best order leaves just 13. It groups jobs of the same type, so the machine gets set up twice instead of five or six times. The hours saved also let later jobs finish sooner.

Three kinds of answers

A dispatch rule picks the next job with one simple rule, like earliest due date or shortest job first. A heuristic is a smarter shortcut. It builds an order that works while weighing extra details, like setups. But it can’t prove that nothing better exists. An exact search checks every possible order against the goal. So its answer is provably the best one for that goal.

Those labels mean different things, so they shouldn’t be swapped. The lab compares three dispatch rules (FIFO, EDD and SPT) with an exact search that lists every order. It has no heuristic, because those are for problems too big to list out. With seven jobs, the lab can honestly call its answer the best, because 7! = 5,040 orders is few enough to check every one.

The goal and the rules

A schedule is only good or bad compared with a goal and a set of rules. In the lab, seven jobs run back to back on one machine, starting at time zero (t = 0). Whenever two jobs in a row are different types, a one-hour setup goes between them. The score is 5 × total tardiness + 2 × setups + 0.1 × makespan. Total tardiness is the hours late, added up over all jobs. Makespan is the time the last job finishes. No job has to come before another, and every job is ready from the start. EDD and SPT ignore setups. That’s why they score well above the best order here: 104.7 and 107.6, against 71.3. And an order that’s best for one goal might not be best for another.

What the lab shows

The lab draws the order you pick on a timeline. Each job gets its own lane, with a post at its due date. Lateness is marked from the due date to when the job actually finishes. The lab compares FIFO, EDD and SPT with a check of all 5,040 orders. A histogram, a bar chart of how many orders get each score, shows where each rule ranks. You can also build an order by hand. As you lock in each job, the lab tells you how many orders are still possible. It also shows the best score you can still reach. The point is to see how far each rule lands from the true best. This problem is small enough that the true best can actually be found. So you can measure the gap instead of just assuming a shortcut found the best answer.

When there are too many orders to check

Checking every order stops working fast. Each extra job multiplies the number of possible orders, so the count grows factorially. Real factory scheduling usually needs stronger tools. Some of them search smartly and skip orders that can’t win, instead of checking every one. CP-SAT, mixed-integer programming and constraint programming all work this way. Other options are splitting the problem into smaller pieces, or carefully tested heuristics. My separate CP-SAT writing explains how those bigger models are set up.

How I check it

The exact answer must score no worse than every order it checked, using the same score. Every schedule the lab shows must include each job exactly once and follow all the rules. And renaming jobs, or listing them in a different order, must never quietly change how the score is worked out.