Dispatch Rule Comparator

How this works

Once a WIP cap sets how many jobs are allowed in process, the queue still has to be sequenced. Shortest Processing Time (SPT) first is the textbook default because it minimizes average flow time, but that is not the same objective as minimizing how many jobs miss their due date. This engine compares SPT against Earliest Due Date (EDD) first on whichever objective is selected, average flow time or on-time delivery, because the two rules can and do disagree on which is better.

Key terms

• SPT (Shortest Processing Time): run the job that takes the least time next. Provably minimizes average flow time on a single machine.
• EDD (Earliest Due Date): run the job due soonest next. Tends to minimize the count of tardy jobs, because it will not strand a near-term-due long job behind several short jobs with distant due dates.
• Flow time: how long a job sits in the system from the start of the queue until it completes.
• Lateness: completion time minus due time. Positive lateness means the job is tardy.

Assumptions

• Single resource, non-preemptive, one job runs at a time to completion
• All four jobs are available at time zero, no staggered arrivals

Limitations

• Fixed four-job queue, not an open-ended N-job scheduler
• Does not model setup times, multi-machine resource contention, or job priority weighting beyond the two named objectives

Sources

Conway, Maxwell, and Miller, Theory of Scheduling, and Pinedo, Scheduling: Theory, Algorithms, and Systems, standard single-machine dispatch-rule results.

Worked example

Four jobs: a 3-hour job due in 4 hours, a 7-hour job due in 15, a 2-hour job due in 18, and a 5-hour job due in 9. SPT runs the 2, 3, 5, then 7-hour job, finishing at 2, 5, 10, and 17 hours, an 8.5-hour average flow time, but the 5-hour job (due at 9) and the 7-hour job (due at 15) both end up late, three jobs tardy in total. EDD runs the 3, 5, 7, then 2-hour job in due-date order, finishing at 3, 8, 15, and 17 hours, a worse 10.75-hour average flow time, but every job lands on or before its due date, zero jobs tardy. SPT wins on throughput, EDD wins on the promise date, whichever matters more decides the rule.

Common use cases

• Choosing a dispatch rule for a queue once a WIP cap is set
• Checking whether the default "shortest job first" habit is actually costing on-time delivery
• Screening SPT against EDD before committing to a forward or backward schedule
• Continuing from WIP Limit Decision's cap into a sequencing decision