Job Shop Dispatching Rules
Dispatching rules are used to determine the sequence of jobs in a job shop environment. Different rules optimize for different performance measures.
Common Dispatching Rules:
- SPT (Shortest Processing Time): Select job with shortest processing time
- EDD (Earliest Due Date): Select job with earliest due date
- CR (Critical Ratio): (Due Date - Current Time) / Processing Time
- S/O (Slack per Operation): (Due Date - Current Time - Remaining Processing Time) / Number of Remaining Operations
Key performance measures:
- Makespan: Total time to complete all jobs
- Average Flow Time: Average time jobs spend in the system
- Average Tardiness: Average amount of time jobs are late
- Number of Tardy Jobs: Count of jobs completed after their due date
Scheduling Results
SPT
EDD
Critical Ratio
Slack per Operation
Shortest Processing Time (SPT)
| Sequence | Job ID | Start Time | Completion Time | Flow Time | Tardiness |
|---|
Performance Metrics
Earliest Due Date (EDD)
| Sequence | Job ID | Start Time | Completion Time | Flow Time | Tardiness |
|---|
Performance Metrics
Critical Ratio (CR)
| Sequence | Job ID | Start Time | Completion Time | Flow Time | Tardiness |
|---|
Performance Metrics
Slack per Operation (S/O)
| Sequence | Job ID | Start Time | Completion Time | Flow Time | Tardiness |
|---|
Performance Metrics
Practical Examples
Example 1: Comparing Rules
Jobs: A (PT=5, DD=10), B (PT=3, DD=8), C (PT=8, DD=15)
SPT Sequence: B, A, C | Makespan: 16 | Avg Tardiness: 1.33
EDD Sequence: B, A, C | Makespan: 16 | Avg Tardiness: 1.33
CR Sequence (at t=0): B, A, C | Makespan: 16 | Avg Tardiness: 1.33
Example 2: Different Outcomes
Jobs: X (PT=4, DD=6), Y (PT=2, DD=12), Z (PT=6, DD=8)
SPT Sequence: Y, X, Z | Makespan: 12 | Avg Tardiness: 2.67
EDD Sequence: X, Z, Y | Makespan: 12 | Avg Tardiness: 2.0
CR Sequence (at t=0): X, Y, Z | Makespan: 12 | Avg Tardiness: 2.67
When to Use Each Rule
| Rule | Best For | Weakness |
|---|---|---|
| SPT | Minimizing average flow time | May cause long jobs to be excessively delayed |
| EDD | Meeting due dates, minimizing maximum tardiness | Doesn't consider processing times |
| CR | Dynamic scheduling, balancing urgency and processing time | Can be unstable when due dates are tight |
| S/O | Operations with multiple remaining steps | More complex to calculate |