Dispatching Rules and Job Sequencing

Dispatching Rules and Job Sequencing: A Comprehensive CPIM Exam Guide

Introduction: Why Dispatching Rules and Job Sequencing Matter

In any manufacturing or service environment, multiple jobs compete for limited resources. When several jobs are waiting in a queue at a work center, someone—or some system—must decide which job to process next. This is where dispatching rules (also called sequencing rules or priority rules) come into play. They provide a systematic method for determining the order in which jobs are processed, directly impacting delivery performance, work-in-process (WIP) inventory, throughput time, and customer satisfaction.

For the CPIM (Certified in Planning and Inventory Management) exam, particularly the Detailed Scheduling and Planning (DSP) module, dispatching rules and job sequencing are core topics. You must understand the rules, know how to apply them mathematically, and be able to evaluate their outcomes against key performance metrics.

---

1. What Are Dispatching Rules?

Dispatching rules are heuristic methods used to prioritize jobs waiting in a queue at a work center. They are applied locally (at each work center) and dynamically (each time a machine becomes available). Unlike optimization algorithms, dispatching rules do not guarantee the best possible solution, but they are simple, fast, and practical for real-world shop floor control.

Key characteristics:
- They are local decision rules—applied one work center at a time
- They are myopic—they don't consider the entire shop floor simultaneously
- They are easy to implement in ERP/MES systems
- They can be static (based on fixed job data) or dynamic (based on data that changes over time, like slack)

---

2. Common Dispatching Rules

Below are the most important dispatching rules you need to know for the CPIM exam:

a) First Come, First Served (FCFS)
Jobs are processed in the order they arrive at the work center.
- Advantage: Simple, perceived as fair
- Disadvantage: Ignores due dates, processing times, and urgency
- Best for: Service environments where fairness perception matters

b) Shortest Processing Time (SPT)
The job with the shortest processing time at the current work center is processed first.
- Advantage: Minimizes average flow time, minimizes average number of jobs in the system, minimizes average lateness (in many cases)
- Disadvantage: Long jobs may be perpetually delayed (job starvation)
- Key fact for exam: SPT is mathematically proven to minimize mean flow time and average WIP for a single machine

c) Longest Processing Time (LPT)
The job with the longest processing time is processed first.
- Advantage: Useful in some parallel machine scheduling scenarios to balance load
- Disadvantage: Generally increases average flow time

d) Earliest Due Date (EDD)
The job with the earliest due date is processed first.
- Advantage: Minimizes maximum lateness (maximum tardiness) for a single machine
- Disadvantage: Does not consider processing time; may increase average flow time
- Key fact for exam: EDD minimizes the worst-case tardiness

e) Critical Ratio (CR)
The job with the smallest critical ratio is processed first.

Formula:
CR = (Due Date − Current Date) / Remaining Processing Time

Or equivalently:
CR = Time Remaining Until Due Date / Work Remaining

Interpretation:
- CR < 1: Job is behind schedule (critical!)
- CR = 1: Job is exactly on schedule
- CR > 1: Job is ahead of schedule
- CR ≤ 0: Job is already past due

- Advantage: Dynamic rule; considers both time remaining and work remaining
- Disadvantage: More complex to compute; can shift priorities frequently
- Key fact for exam: CR is a dynamic priority rule that integrates due date urgency with workload

f) Slack Time (ST) / Least Slack
The job with the least slack is processed first.

Formula:
Slack = (Due Date − Current Date) − Remaining Processing Time

- Advantage: Focuses on jobs most at risk of being late
- Disadvantage: Does not account for the number of remaining operations

g) Slack Per Remaining Operation (S/RO)

Formula:
S/RO = [(Due Date − Current Date) − Remaining Processing Time] / Number of Remaining Operations

- Advantage: Accounts for both urgency and complexity of remaining work
- Disadvantage: More complex to calculate

h) Weighted Shortest Processing Time (WSPT)
Jobs are sequenced by the ratio of processing time to weight (importance): process the job with the smallest p_j/w_j first (or equivalently, largest w_j/p_j).
- Advantage: Minimizes weighted average flow time; incorporates job priority

---

3. How to Apply Dispatching Rules: Step-by-Step Process

When you encounter an exam question, follow this process:

Step 1: Identify the data given. Typically you will see a table with:
- Job names (A, B, C, etc.)
- Processing times at the work center
- Due dates
- Arrival times (sometimes)
- Weights or priorities (sometimes)
- Number of remaining operations (sometimes)

Step 2: Identify which dispatching rule to apply. The question will specify the rule or ask you to compare rules.

Step 3: Sequence the jobs according to the rule.

Step 4: Build a Gantt-chart-style table calculating for each job:
- Start time
- Processing time
- Completion time (flow time) = Start time + Processing time (assuming jobs start as soon as the machine is free)
- Due date
- Lateness = Completion time − Due date (can be negative, meaning early)
- Tardiness = max(0, Lateness) — tardiness is never negative

Step 5: Calculate performance metrics:
- Average flow time = Sum of all completion times / Number of jobs
- Average tardiness = Sum of all tardiness values / Number of jobs
- Maximum tardiness = Largest tardiness value
- Number of tardy jobs = Count of jobs where tardiness > 0
- Average number of jobs in system = Sum of flow times / Makespan
- Utilization = Total processing time / Makespan

---

4. Worked Example

Suppose today is Day 0 and you have the following jobs:

| Job | Processing Time | Due Date |
|-----|----------------|----------|
| A | 5 | 10 |
| B | 3 | 8 |
| C | 7 | 12 |
| D | 2 | 6 |
| E | 4 | 15 |

Applying SPT (Shortest Processing Time):
Sequence: D(2), B(3), E(4), A(5), C(7)

| Job | Processing Time | Completion Time | Due Date | Lateness | Tardiness |
|-----|----------------|-----------------|----------|----------|-----------|
| D | 2 | 2 | 6 | −4 | 0 |
| B | 3 | 5 | 8 | −3 | 0 |
| E | 4 | 9 | 15 | −6 | 0 |
| A | 5 | 14 | 10 | 4 | 4 |
| C | 7 | 21 | 12 | 9 | 9 |

Average Flow Time = (2+5+9+14+21)/5 = 51/5 = 10.2 days
Average Tardiness = (0+0+0+4+9)/5 = 13/5 = 2.6 days
Maximum Tardiness = 9 days
Number of Tardy Jobs = 2

Applying EDD (Earliest Due Date):
Sequence: D(due 6), B(due 8), A(due 10), C(due 12), E(due 15)

| Job | Processing Time | Completion Time | Due Date | Lateness | Tardiness |
|-----|----------------|-----------------|----------|----------|-----------|
| D | 2 | 2 | 6 | −4 | 0 |
| B | 3 | 5 | 8 | −3 | 0 |
| A | 5 | 10 | 10 | 0 | 0 |
| C | 7 | 17 | 12 | 5 | 5 |
| E | 4 | 21 | 15 | 6 | 6 |

Average Flow Time = (2+5+10+17+21)/5 = 55/5 = 11.0 days
Average Tardiness = (0+0+0+5+6)/5 = 11/5 = 2.2 days
Maximum Tardiness = 6 days
Number of Tardy Jobs = 2

Comparison:
- SPT gave a lower average flow time (10.2 vs. 11.0) — as expected
- EDD gave a lower maximum tardiness (6 vs. 9) — as expected
- EDD also happened to give slightly lower average tardiness in this case

This demonstrates why no single rule dominates on all criteria.

---

5. Johnson's Rule: Special Case for Two-Machine Flow Shop

When all jobs must pass through exactly two machines in the same order (Machine 1 then Machine 2), Johnson's Rule provides an optimal sequence that minimizes makespan (total time to complete all jobs).

Johnson's Rule Algorithm:
1. List all jobs with their processing times on Machine 1 and Machine 2.
2. Find the job with the smallest processing time across both machines.
3. If that smallest time is on Machine 1, place the job as early as possible in the sequence.
4. If that smallest time is on Machine 2, place the job as late as possible in the sequence.
5. Remove the job from the list and repeat until all jobs are sequenced.
6. Tie-breaking: If there is a tie, either position works; if the tie is between a Machine 1 and Machine 2 time, prioritize placing the Machine 1 job first.

Key fact for exam: Johnson's Rule is an optimization method (not a heuristic) for the two-machine flow shop problem. It minimizes makespan.

---

6. Key Concepts and Definitions for the Exam

Flow Time: The total time a job spends in the system (from arrival or release to completion). Sometimes called throughput time or manufacturing lead time.

Makespan: The total time to complete all jobs (from start of the first job to completion of the last job).

Lateness: Completion time minus due date. Can be positive (late) or negative (early).

Tardiness: max(0, Lateness). Tardiness is always ≥ 0. It measures how late a job is, ignoring early jobs.

Utilization: Total processing time divided by makespan. Measures how busy the machine is.

WIP (Work in Process): Related to average flow time via Little's Law: WIP = Throughput Rate × Flow Time

---

7. Comparing Rules: Summary Table

| Rule | Minimizes | Key Characteristic |
|------|-----------|-------------------|
| SPT | Mean flow time, mean WIP, mean lateness | May starve long jobs |
| EDD | Maximum tardiness | Focuses on due dates |
| CR | Dynamic priority based on urgency | Adapts as time passes |
| FCFS | Nothing specific | Perceived fairness |
| Slack/S/RO | Focuses on at-risk jobs | More complex calculation |
| Johnson's | Makespan (2-machine flow shop) | Optimal algorithm |

---

8. Exam Tips: Answering Questions on Dispatching Rules and Job Sequencing

Tip 1: Memorize what each rule optimizes.
The exam loves to test whether you know that SPT minimizes mean flow time and EDD minimizes maximum tardiness. These are the two most frequently tested facts.

Tip 2: Know the Critical Ratio formula cold.
CR = (Due Date − Current Date) / Remaining Processing Time. Understand the interpretation: CR < 1 means behind schedule, CR = 1 means on schedule, CR > 1 means ahead. A job with the lowest CR gets highest priority.

Tip 3: Be careful with lateness vs. tardiness.
Lateness can be negative (early); tardiness is always zero or positive. The exam may try to trick you with this distinction.

Tip 4: Practice the math.
Be comfortable building the completion-time table quickly. On the exam, you may need to sequence 4–6 jobs and compute metrics. Practice doing this in under 5 minutes.

Tip 5: Remember Johnson's Rule conditions.
Johnson's Rule applies ONLY when: (a) there are exactly two machines, (b) all jobs follow the same sequence (Machine 1 → Machine 2), and (c) you want to minimize makespan. If the question describes a different scenario, Johnson's Rule does not apply.

Tip 6: Understand that no single rule is best for all objectives.
If a question asks which rule is universally best, the answer is none. The best rule depends on the performance objective. This is a common conceptual question.

Tip 7: Know the difference between static and dynamic rules.
- Static rules (SPT, EDD, FCFS, LPT) use fixed job attributes
- Dynamic rules (CR, Slack, S/RO) change priority as time passes
The exam may ask you to classify rules.

Tip 8: Watch for "truncated SPT" or hybrid rules.
Some questions describe modified SPT rules where a maximum wait time is imposed to prevent starvation of long jobs. Understand the concept even if you don't need to calculate it.

Tip 9: Read questions carefully for what metric is being asked.
"Which rule minimizes the average time jobs spend in the system?" → SPT
"Which rule minimizes the worst-case delay?" → EDD
"Which rule dynamically adjusts priorities?" → Critical Ratio
"Which rule minimizes makespan on a two-machine flow shop?" → Johnson's Rule

Tip 10: Use process of elimination.
If you are unsure, eliminate obviously wrong answers. For example, FCFS never optimizes any standard performance metric, so it's rarely the "best" answer unless the question is about fairness or simplicity.

Tip 11: Understand input/output control context.
Dispatching rules are part of shop floor control (Production Activity Control / PAC). They work alongside input/output control, which manages the flow of work to and from work centers. The exam may place dispatching rules within the broader PAC framework.

Tip 12: For Critical Ratio questions, always check for negative or zero values.
A CR of 0 or less means the job is already past due. These jobs should receive the highest priority (processed first). If multiple jobs have CR ≤ 0, use a secondary rule (like EDD or SPT) to break the tie.

---

9. Summary

Dispatching rules are essential tools for shop floor scheduling. For the CPIM exam, focus on:

1. Knowing the rules: FCFS, SPT, LPT, EDD, CR, Slack, S/RO, Johnson's Rule
2. Knowing what each optimizes: SPT → mean flow time; EDD → max tardiness; Johnson's → makespan
3. Being able to calculate: Flow times, lateness, tardiness, CR values, and performance metrics
4. Understanding trade-offs: No single rule is universally best
5. Classifying rules: Static vs. dynamic, heuristic vs. optimal

Master these concepts and practice the calculations, and you will be well-prepared for dispatching rule questions on the CPIM exam.