Key Production Scheduling Algorithms

Why This Matters

Production scheduling algorithms form the backbone of operational efficiency—they determine how, when, and in what order work gets done. You're being tested on your ability to match the right algorithm to the right production environment, understand the trade-offs each method creates, and calculate key metrics like makespan, average flow time, and tardiness. These aren't just theoretical concepts; they directly impact inventory costs, customer satisfaction, and resource utilization in real manufacturing and service settings.

The algorithms you'll encounter fall into distinct categories based on what they optimize: minimizing total completion time, meeting due dates, managing project complexity, or balancing competing priorities. Don't just memorize the rules—know what problem each algorithm solves best and when it fails. Exam questions will ask you to compare methods, identify which rule fits a scenario, and calculate outcomes using specific techniques.

---

Single-Machine Priority Rules

These algorithms determine job sequence on a single resource by applying simple priority rules. The key insight is that different objectives—minimizing wait time, meeting deadlines, or processing efficiency—require different sequencing logic.

Shortest Processing Time (SPT)

• Minimizes average flow time and average waiting time—mathematically proven optimal for these objectives on a single machine
• Reduces work-in-process inventory by clearing short jobs quickly, keeping the queue moving
• Trade-off: job starvation—longer jobs may wait indefinitely, making SPT unsuitable when all jobs have similar priority

Earliest Due Date (EDD)

• Minimizes maximum tardiness ($L_{max}$)—optimal when your goal is preventing the worst-case late delivery
• Prioritizes deadline urgency over processing efficiency, scheduling jobs with the nearest due date first
• Best for contract-driven environments where late penalties or customer commitments make on-time delivery non-negotiable

Longest Processing Time (LPT)

• Front-loads large jobs to ensure they complete while resources are available and fresh
• Reduces number of tardy jobs in specific scenarios—particularly when due dates cluster together
• Parallel machine applications—commonly used for load balancing across multiple machines by assigning longest jobs first

First-Come, First-Served (FCFS)

• Processes jobs in arrival order—the simplest rule requiring no calculation or job information
• Perceived fairness makes it common in service industries where customers observe the queue
• Poorest performance on most metrics (flow time, tardiness)—use only when simplicity or equity outweighs efficiency

Critical Ratio Scheduling

• Dynamic priority calculation: $CR = \frac{\text{Time Remaining Until Due Date}}{\text{Processing Time Remaining}}$
• Jobs with $CR < 1$ are already behind schedule—lowest CR gets highest priority, balancing urgency against workload
• Adapts in real-time as conditions change, making it superior to static rules in volatile environments

---

Multi-Machine Flow Shop Algorithms

When jobs must flow through multiple machines in sequence, scheduling becomes exponentially more complex. These algorithms optimize the overall makespan—total time to complete all jobs through all machines.

Johnson's Rule

• Optimal for two-machine flow shops—guarantees minimum makespan when all jobs follow the same machine sequence
• Algorithm logic: compare each job's time on Machine 1 vs. Machine 2; if Machine 1 is shorter, schedule early; if Machine 2 is shorter, schedule late
• Mathematical elegance—one of the few scheduling problems with a proven optimal polynomial-time solution

---

Project Scheduling Techniques

Project scheduling differs from job scheduling because tasks have precedence relationships—some activities cannot start until others finish. These methods map dependencies and identify which delays will impact the entire project.

Critical Path Method (CPM)

• Identifies the longest path through the project network—this critical path determines minimum project duration
• Float/slack calculation reveals which activities can be delayed without affecting completion; critical activities have zero float
• Deterministic approach—assumes activity durations are known with certainty, making it ideal for repetitive or well-understood projects

Program Evaluation and Review Technique (PERT)

• Incorporates uncertainty using three time estimates: optimistic ($a$), most likely ($m$), and pessimistic ($b$)
• Expected time formula: $t_e = \frac{a + 4m + b}{6}$—a weighted average emphasizing the most likely estimate
• Probabilistic analysis allows managers to estimate the likelihood of meeting target completion dates

---

Flexible Priority Systems

Some environments require scheduling rules that adapt to changing conditions or accommodate multiple competing objectives. These methods allow customization based on organizational priorities.

Priority-Based Scheduling

• Assigns priority levels (numeric or categorical) allowing critical jobs to preempt less important work
• Static vs. dynamic priorities—static priorities are set once; dynamic priorities adjust based on waiting time, customer importance, or other factors
• Weighted criteria can combine multiple factors (due date, customer value, processing time) into a single priority score

Gantt Charts

• Visual scheduling tool displaying tasks as horizontal bars along a timeline—invented by Henry Gantt circa 1910
• Shows dependencies and overlaps at a glance, making it invaluable for communication and progress tracking
• Planning vs. control—used both to create initial schedules and to monitor actual vs. planned progress

---

Quick Reference Table

---

Self-Check Questions

1. A manager wants to minimize average customer waiting time at a single service station. Which algorithm should they use, and why would EDD be the wrong choice?

2. Compare Johnson's Rule and SPT: what production environment does each optimize, and what metric does each minimize?

3. You're scheduling a construction project with uncertain activity durations. Would you choose CPM or PERT? What three time estimates would you need for each activity?

4. A job has 5 days until its due date and requires 10 days of processing time. Calculate its critical ratio and explain what this value indicates about the job's status.

5. An FRQ describes a manufacturing cell where some jobs are contractually time-sensitive while others are routine. Which scheduling approach would you recommend over FCFS, and how would you structure the priority system?