Key Production Scheduling Algorithms

Why This Matters

Production scheduling algorithms determine how, when, and in what order work gets done on the shop floor. They form the backbone of operational efficiency in any manufacturing or service environment.

You need to be able to match the right algorithm to the right production setting, understand the trade-offs each method creates, and calculate key metrics like makespan, average flow time, and tardiness. These concepts directly impact inventory costs, customer satisfaction, and resource utilization.

The algorithms 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 breaks down.

---

Single-Machine Priority Rules

These algorithms determine job sequence on a single resource by applying simple priority rules. Different objectives require different sequencing logic: minimizing wait time, meeting deadlines, and maximizing processing efficiency each call for a different approach.

Shortest Processing Time (SPT)

• Minimizes average flow time and average waiting time. This is mathematically proven optimal for these two objectives on a single machine.
• Reduces work-in-process inventory by clearing short jobs quickly, which keeps the queue moving.
• Trade-off: job starvation. Longer jobs can get pushed back indefinitely as shorter jobs keep arriving. SPT is a poor choice when all jobs carry similar priority or when long jobs have tight deadlines.

Earliest Due Date (EDD)

• Minimizes maximum tardiness ($L_{max}$). It's the optimal rule when your goal is preventing the worst-case late delivery.
• Prioritizes deadline urgency over processing efficiency, always scheduling the job 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 start while resources are available.
• Parallel machine applications are where LPT really shines. When you have multiple identical machines, assigning the longest jobs first helps balance the load across machines and reduces overall makespan.
• On a single machine, LPT is rarely optimal. Its main value is in multi-machine load balancing scenarios.

First-Come, First-Served (FCFS)

• Processes jobs in arrival order. It's the simplest rule, requiring no calculation or job information at all.
• Perceived fairness makes it common in service industries where customers can observe the queue.
• Poorest performance on most measurable metrics (flow time, tardiness, number of late jobs). Use it only when simplicity or equity outweighs efficiency.

Critical Ratio Scheduling

The critical ratio is calculated as:

$CR = \frac{\text{Time Remaining Until Due Date}}{\text{Processing Time Remaining}}$

• A $CR < 1$ means the job is already behind schedule. The job with the lowest CR gets the highest priority.
• A $CR = 1$ means the job is exactly on pace. A $CR > 1$ means the job has slack.
• Unlike static rules like SPT or EDD, Critical Ratio recalculates every time a scheduling decision is made, so it adapts as conditions change. This makes it superior in volatile environments where new jobs arrive or priorities shift.

---

Multi-Machine Flow Shop Algorithms

When jobs must flow through multiple machines in sequence, scheduling becomes exponentially more complex. The goal shifts to optimizing makespan, the total time to complete all jobs through all machines.

Johnson's Rule

Johnson's Rule provides the optimal solution for two-machine flow shops, guaranteeing minimum makespan when all jobs follow the same two-machine sequence.

How to apply Johnson's Rule (step by step):

1. List each job's processing time on Machine 1 and Machine 2.
2. Find the shortest processing time across all jobs and both machines.
3. If that shortest time is on Machine 1, schedule that job as early as possible (front of the sequence).
4. If that shortest time is on Machine 2, schedule that job as late as possible (back of the sequence).
5. Remove that job from the list and repeat until all jobs are scheduled.
6. Ties can be broken arbitrarily, though placing ties on Machine 1 early and Machine 2 late is a common convention.

This is one of the few scheduling problems with a proven optimal polynomial-time solution, which is why it shows up so frequently on exams.

---

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 longest path is the critical path, and it determines the minimum project duration.
• Float (slack) calculation reveals which activities can be delayed without affecting the project's completion date. Activities on the critical path have zero float, meaning any delay to them delays the whole project.
• CPM is a deterministic approach: it assumes activity durations are known with certainty. That makes it ideal for repetitive or well-understood projects like construction or routine maintenance.

Program Evaluation and Review Technique (PERT)

PERT handles situations where you don't know exact durations. It uses three time estimates for each activity:

• Optimistic ($a$): best-case duration if everything goes right
• Most likely ($m$): the duration you'd expect under normal conditions
• Pessimistic ($b$): worst-case duration if things go wrong

The expected time for each activity is:

$t_e = \frac{a + 4m + b}{6}$

This weighted average puts four times the weight on the most likely estimate. PERT then uses these expected times to find the critical path, just like CPM. The added benefit is probabilistic analysis: you can estimate the likelihood of meeting a target completion date by calculating the variance along the critical path.

---

Flexible Priority Systems

Some environments require scheduling rules that adapt to changing conditions or accommodate multiple competing objectives.

Priority-Based Scheduling

• Assigns priority levels (numeric or categorical) so that critical jobs can preempt less important work.
• Static vs. dynamic priorities: static priorities are set once when a job arrives; dynamic priorities adjust over time based on factors like waiting time, customer importance, or proximity to a due date.
• Weighted scoring can combine multiple factors into a single priority number. For example, you might weight due date urgency at 40%, customer value at 35%, and processing time at 25% to create a composite score for each job.

Gantt Charts

• A visual scheduling tool that displays tasks as horizontal bars along a timeline. Henry Gantt developed this format around 1910, and it remains one of the most widely used planning tools.
• Gantt charts show task durations, dependencies, and overlaps at a glance, making them valuable for communication and progress tracking across teams.
• They serve a dual purpose: planning (creating the initial schedule) and control (comparing actual progress against the plan).

---

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?