Sequencing Models

Single Machine Scheduling & Priority Rules

By: Sothearith Min

Institute of Technology of Cambodia

Introduction

What is Sequencing?

πŸ“‹ Definition

  • Determining the order in which jobs are processed
  • Jobs arrive at a machine/workstation
  • Must decide: which job goes first?
  • Goal: optimize performance measures

✨ Key Questions

  • Which job to process next?
  • How to minimize waiting time?
  • How to meet deadlines?
  • How to keep customers happy?

Why Sequencing Matters

🎯 Real-World Impact

Poor sequencing leads to:

  • Long customer wait times ⏰
  • Missed deadlines πŸ“…
  • Inefficient resource use 🏭
  • Lost revenue πŸ’°
  • Unhappy customers 😞

Good sequencing provides:

  • Reduced costs βœ“
  • Better customer service βœ“
  • Improved efficiency βœ“

Real-World Applications

🏭 Manufacturing

Order parts through machines β†’ Minimize completion time

πŸ₯ Healthcare

Schedule surgeries in operating room β†’ Minimize waiting

πŸ’» Computer Systems

Process jobs in CPU β†’ Optimize throughput

πŸ• Service Industry

Prepare food orders β†’ Meet delivery promises

Types of Sequencing Problems

Single Machine

  • One workstation
  • Multiple jobs
  • Simplest case
  • Foundation for complex problems

Multiple Machines

  • Parallel machines
  • Flow shop (same sequence)
  • Job shop (different routes)
  • Much more complex

Single Machine Sequencing

🎯 The Setup

  • One machine (or workstation)
  • n jobs waiting to be processed
  • Each job has:
    • Processing time \(p_i\)
    • Due date \(d_i\)
    • Weight/priority \(w_i\) (optional)
  • All jobs available at time 0

The Question

In what order should we process these jobs?

Performance Measures

Key Terminology

πŸ“– Important Definitions

Processing time (\(p_i\)): Time to complete job \(i\)

Completion time (\(C_i\)): Time when job \(i\) finishes

Flow time (\(F_i\)): Total time job \(i\) spends in system \[F_i = C_i\]

Due date (\(d_i\)): Deadline for job \(i\)

Lateness (\(L_i\)): How late (or early) job finishes \[L_i = C_i - d_i\]

More Terminology

πŸ“– Additional Measures

Tardiness (\(T_i\)): Amount of time past due date \[T_i = \max(0, L_i) = \max(0, C_i - d_i)\]

Earliness (\(E_i\)): Amount of time before due date \[E_i = \max(0, d_i - C_i)\]

Number of tardy jobs (\(n_T\)): Count of late jobs

Common Objective Functions

🎯 What We Want to Minimize

  1. Mean Flow Time: \(\bar{F} = \frac{1}{n}\sum_{i=1}^{n} F_i\)

  2. Makespan: \(C_{\max} = \max(C_i)\)

  3. Mean Tardiness: \(\bar{T} = \frac{1}{n}\sum_{i=1}^{n} T_i\)

  4. Maximum Tardiness: \(T_{\max} = \max(T_i)\)

  5. Number of Tardy Jobs: \(n_T\)

  6. Weighted measures: \(\sum w_i F_i\), \(\sum w_i T_i\)

Simple Example - Setup

🏭 Print Shop Problem

3 jobs arrive at a printing machine

Job Processing Time (\(p_i\)) Due Date (\(d_i\))
A 5 hours 8 hours
B 3 hours 6 hours
C 4 hours 10 hours

Tip

Question: What sequence minimizes mean flow time?

Example - Sequence A-B-C

Processing order: A β†’ B β†’ C

Job \(p_i\) Start \(C_i\) \(F_i\) \(d_i\) \(L_i\) \(T_i\)
A 5 0 5 5 8 -3 0
B 3 5 8 8 6 2 2
C 4 8 12 12 10 2 2

Results

  • Mean Flow Time: \(\bar{F} = \frac{5+8+12}{3} = 8.33\) hours
  • Mean Tardiness: \(\bar{T} = \frac{0+2+2}{3} = 1.33\) hours
  • Number of Tardy Jobs: \(n_T = 2\)

Example - Sequence B-A-C

Processing order: B β†’ A β†’ C

Job \(p_i\) Start \(C_i\) \(F_i\) \(d_i\) \(L_i\) \(T_i\)
B 3 0 3 3 6 -3 0
A 5 3 8 8 8 0 0
C 4 8 12 12 10 2 2

Results

  • Mean Flow Time: \(\bar{F} = \frac{3+8+12}{3} = 7.67\) hours βœ“ Better!
  • Mean Tardiness: \(\bar{T} = \frac{0+0+2}{3} = 0.67\) hours βœ“
  • Number of Tardy Jobs: \(n_T = 1\) βœ“

Example - Sequence B-C-A

Processing order: B β†’ C β†’ A

Job \(p_i\) Start \(C_i\) \(F_i\) \(d_i\) \(L_i\) \(T_i\)
B 3 0 3 3 6 -3 0
C 4 3 7 7 10 -3 0
A 5 7 12 12 8 4 4

Results

  • Mean Flow Time: \(\bar{F} = \frac{3+7+12}{3} = 7.33\) hours βœ“ Best so far!
  • Mean Tardiness: \(\bar{T} = \frac{0+0+4}{3} = 1.33\) hours
  • Number of Tardy Jobs: \(n_T = 1\)

Comparison of All Sequences

πŸ“Š Performance Comparison

Sequence Mean Flow Time Mean Tardiness Tardy Jobs
A-B-C 8.33 1.33 2
A-C-B 8.67 2.00 2
B-C-A 7.33 βœ“ 1.33 1
B-A-C 7.67 0.67 1
C-A-B 9.00 2.00 2
C-B-A 9.33 2.67 2

Important

Best for flow time: B-C-A (shortest jobs first!)

Priority Rules

What Are Priority Rules?

πŸ“‹ Definition

Priority rules (or dispatching rules) are simple heuristics that determine the order in which jobs are processed.

How they work:

  1. Look at all waiting jobs
  2. Calculate priority based on job characteristics
  3. Select job with highest priority
  4. Process it
  5. Repeat

Tip

Easy to understand and implement! πŸš€

The Three Main Rules

🎯 FCFS - First Come First Served

Process jobs in order of arrival

⚑ SPT - Shortest Processing Time

Process shortest job first

πŸ“… EDD - Earliest Due Date

Process job with earliest deadline first

FCFS Rule

First Come First Served (FCFS)

πŸ“‹ The Rule

Process jobs in the order they arrive

  • Also called FIFO (First In First Out)
  • Like waiting in line at a store
  • Arrival time determines priority
  • Fair and intuitive

πŸ‘ Advantages

  • Very simple
  • Fair to customers
  • Easy to explain
  • No complex calculations

FCFS - When to Use

βœ… Good For

  • Service industries (banks, restaurants)
  • When fairness is important
  • Simple operations
  • Similar processing times
  • When due dates don’t matter much

❌ Not Good For

  • Minimizing flow time
  • Meeting tight deadlines
  • When job times vary greatly
  • Emergency situations

FCFS Example 1 - Setup

πŸ₯ Medical Lab Problem

A medical lab processes 5 blood samples

Job Arrival Order Processing Time (\(p_i\)) Due Date (\(d_i\))
1 1st 6 10
2 2nd 3 8
3 3rd 8 15
4 4th 2 7
5 5th 5 12

Tip

FCFS Rule: Process in order 1-2-3-4-5

FCFS Example 1 - Solution

Sequence: 1 β†’ 2 β†’ 3 β†’ 4 β†’ 5

Job \(p_i\) Start \(C_i\) \(F_i\) \(d_i\) \(L_i\) \(T_i\)
1 6 0 6 6 10 -4 0
2 3 6 9 9 8 1 1
3 8 9 17 17 15 2 2
4 2 17 19 19 7 12 12
5 5 19 24 24 12 12 12
Ξ£=24 Ξ£=75 Ξ£=27

FCFS Example 1 - Results

πŸ“Š Performance Metrics

  • Mean Flow Time: \(\bar{F} = \frac{75}{5} = 15.0\) hours
  • Mean Tardiness: \(\bar{T} = \frac{27}{5} = 5.4\) hours
  • Maximum Tardiness: \(T_{\max} = 12\) hours
  • Number of Tardy Jobs: \(n_T = 4\) out of 5
  • Makespan: \(C_{\max} = 24\) hours

Warning

Notice: Job 4 (shortest, earliest due date) waited until last! Not ideal for minimizing tardiness.

FCFS Coffee Shop - Solution

FCFS Sequence: A β†’ B β†’ C β†’ D

Order Time (min) Ready At Promised Lateness Tardy?
A 5 8:05 8:12 -7 min No
B 2 8:07 8:10 -3 min No
C 7 8:14 8:18 -4 min No
D 3 8:17 8:15 +2 min Yes

Summary

  • Mean completion time: 10.75 minutes
  • 1 late order (Dan’s coffee)
  • Total lateness: 2 minutes

FCFS - Key Observations

πŸ” Important Points

  1. Simple but not optimal for most objectives
  2. Long jobs early β†’ everyone waits longer
  3. Fair but not necessarily efficient
  4. Good when processing times are similar
  5. Best for maintaining customer relations

⚠️ Problem

If a short urgent job arrives late, it still waits for all earlier jobs!

SPT Rule

Shortest Processing Time (SPT)

⚑ The Rule

Always process the job with the shortest processing time next

  • Focus on job duration
  • Ignore arrival order
  • Ignore due dates
  • Just pick the quickest job

πŸ† Famous Result

SPT minimizes mean flow time!

This is a proven optimal result for single machine scheduling.

Why SPT Works

πŸ’‘ The Logic

Example: Jobs of 10 min and 2 min

Order 10-2:

  • Job 1 waits: 0, completes: 10
  • Job 2 waits: 10, completes: 12
  • Total flow time: 10 + 12 = 22

Order 2-10:

  • Job 1 waits: 0, completes: 2
  • Job 2 waits: 2, completes: 12
  • Total flow time: 2 + 12 = 14 βœ“

Shorter jobs first β†’ Fewer jobs waiting!

SPT - Advantages

βœ… Benefits

  • Optimal for mean flow time
  • Minimizes mean waiting time
  • Minimizes work in process (WIP)
  • Reduces number of jobs in system

πŸ“Š Performance

  • Best rule for flow time
  • Often good for mean tardiness too
  • Maximizes number of jobs completed

SPT Example 1 - Same Data as FCFS

πŸ₯ Medical Lab - Revisited

Using the same 5 blood samples:

Job Arrival Order Processing Time (\(p_i\)) Due Date (\(d_i\))
1 1st 6 10
2 2nd 3 8
3 3rd 8 15
4 4th 2 7
5 5th 5 12

Tip

SPT Rule: Order by processing time: 4-2-5-1-3

SPT Example 1 - Solution

Sequence: 4 β†’ 2 β†’ 5 β†’ 1 β†’ 3

Job \(p_i\) Start \(C_i\) \(F_i\) \(d_i\) \(L_i\) \(T_i\)
4 2 0 2 2 7 -5 0
2 3 2 5 5 8 -3 0
5 5 5 10 10 12 -2 0
1 6 10 16 16 10 6 6
3 8 16 24 24 15 9 9
Ξ£=24 Ξ£=57 Ξ£=15

SPT vs FCFS Comparison

πŸ“Š Performance Comparison

Metric FCFS SPT Improvement
Mean Flow Time 15.0 11.4 24% better βœ“
Mean Tardiness 5.4 3.0 44% better βœ“
Max Tardiness 12 9 25% better βœ“
Tardy Jobs 4 2 50% better βœ“
Makespan 24 24 Same

Tip

SPT is clearly better for this example!

SPT Example 2 - Computer Jobs

πŸ’» Server Processing Problem

A server must process 6 jobs

Job Processing Time (sec) Due Time (sec)
A 15 25
B 8 18
C 12 30
D 5 15
E 20 40
F 10 22

Tip

SPT Order: D(5) β†’ B(8) β†’ F(10) β†’ C(12) β†’ A(15) β†’ E(20)

SPT Computer Jobs - Solution

Sequence: D β†’ B β†’ F β†’ C β†’ A β†’ E

Job \(p_i\) Start \(C_i\) \(d_i\) \(L_i\) \(T_i\)
D 5 0 5 15 -10 0
B 8 5 13 18 -5 0
F 10 13 23 22 1 1
C 12 23 35 30 5 5
A 15 35 50 25 25 25
E 20 50 70 40 30 30
Ξ£=70 Ξ£=196 Ξ£=61

SPT Computer Jobs - Results

πŸ“Š Results

  • Mean Flow Time: \(\bar{F} = \frac{196}{6} = 32.67\) seconds
  • Mean Tardiness: \(\bar{T} = \frac{61}{6} = 10.17\) seconds
  • Maximum Tardiness: \(T_{\max} = 30\) seconds
  • Number of Tardy Jobs: \(n_T = 4\) out of 6

Warning

Problem: Jobs A and E are very late because they’re long jobs! This is the β€œstarvation” issue.

SPT Example 3 - Restaurant Orders

🍽️ Kitchen Problem

5 food orders to prepare

Order Dish Prep Time (min) Customer Waiting
1 Steak 18 Table 5
2 Salad 5 Table 2
3 Pasta 12 Table 7
4 Soup 7 Table 3
5 Sandwich 10 Table 1

Restaurant - SPT Sequence

SPT Order: 2(Salad) β†’ 4(Soup) β†’ 5(Sandwich) β†’ 3(Pasta) β†’ 1(Steak)

Order Time Ready At Cumulative Wait
2 5 5 min 5
4 7 12 min 12
5 10 22 min 22
3 12 34 min 34
1 18 52 min 52
Total: 52 Sum: 125

Important

Mean waiting time: 125/5 = 25 minutes

EDD Rule

Earliest Due Date (EDD)

πŸ“… The Rule

Always process the job with the earliest (soonest) due date next

  • Focus on deadlines
  • Ignore arrival order
  • Ignore processing time
  • Pick most urgent job

πŸ† Famous Result

EDD minimizes maximum lateness (\(L_{\max}\))!

Proven optimal for this specific objective.

Why EDD Works

πŸ’‘ The Logic

Goal: Avoid being very late on any job

Strategy: Do urgent jobs first

Result:

  • May have many slightly late jobs
  • But avoid any extremely late jobs
  • Maximum lateness is minimized
  • Good for customer satisfaction

Important: Doesn’t minimize mean tardiness, just maximum!

EDD - When to Use

Important

βœ… Good For

  • When deadlines are critical
  • Customer commitments matter
  • Contracts with penalties
  • Time-sensitive deliveries
  • Minimizing worst-case lateness
  • Fair deadline-based system

❌ Not Good For

  • Minimizing average flow time
  • Minimizing average tardiness
  • When all due dates are similar
  • Throughput optimization

EDD Example 1 - Same Medical Lab

πŸ₯ Medical Lab - Third Approach

Same 5 blood samples again:

Job Processing Time (\(p_i\)) Due Date (\(d_i\))
1 6 10
2 3 8
3 8 15
4 2 7
5 5 12

Tip

EDD Rule: Order by due date: 4(7) β†’ 2(8) β†’ 1(10) β†’ 5(12) β†’ 3(15)

EDD Example 1 - Solution

Sequence: 4 β†’ 2 β†’ 1 β†’ 5 β†’ 3

Job \(p_i\) Start \(C_i\) \(F_i\) \(d_i\) \(L_i\) \(T_i\)
4 2 0 2 2 7 -5 0
2 3 2 5 5 8 -3 0
1 6 5 11 11 10 1 1
5 5 11 16 16 12 4 4
3 8 16 24 24 15 9 9
Ξ£=24 Ξ£=58 Max=9 Ξ£=14

Three-Way Comparison

πŸ“Š FCFS vs SPT vs EDD

Metric FCFS SPT EDD
Mean Flow Time 15.0 11.4 βœ“ 11.6
Mean Tardiness 5.4 3.0 2.8
Max Tardiness 12 9 9 βœ“
Max Lateness 12 9 9 βœ“
Tardy Jobs 4 2 3
Makespan 24 24 24

Note

  • SPT best for flow time
  • EDD best for maximum lateness
  • EDD good for mean tardiness too

EDD Example 2 - Package Delivery

πŸ“¦ Delivery Service Problem

Driver has 6 packages to deliver

Package Delivery Time (min) Promised By
A 10 9:30 AM
B 15 9:45 AM
C 8 9:20 AM
D 12 9:40 AM
E 20 10:00 AM
F 6 9:25 AM

Current time: 9:00 AM

Package Delivery - Due Date Calculation

Convert to Minutes from Now

Package Time (min) Promised Due in (min)
A 10 9:30 30
B 15 9:45 45
C 8 9:20 20
D 12 9:40 40
E 20 10:00 60
F 6 9:25 25

EDD Order: C(20) β†’ F(25) β†’ A(30) β†’ D(40) β†’ B(45) β†’ E(60)

Package Delivery - EDD Solution

Sequence: C β†’ F β†’ A β†’ D β†’ B β†’ E

Pkg Time Done Clock Due Lateness Tardy?
C 8 8 9:08 9:20 -12 No
F 6 14 9:14 9:25 -11 No
A 10 24 9:24 9:30 -6 No
D 12 36 9:36 9:40 -4 No
B 15 51 9:51 9:45 +6 Yes
E 20 71 10:11 10:00 +11 Yes

Important

Max Lateness: 11 minutes (Package E)

EDD vs SPT Trade-offs

🎯 Key Differences

SPT (Shortest Processing Time):

  • Minimizes mean flow time
  • Maximizes throughput
  • May create very late long jobs
  • Good for efficiency

EDD (Earliest Due Date):

  • Minimizes maximum lateness
  • Balances all deadlines
  • May have longer average wait
  • Good for reliability

EDD Practice Problem

🎯 Hospital Emergency Room

5 patients need treatment (non-life threatening)

Patient Treatment Time (min) Triage Priority (due)
1 20 50 min
2 15 30 min
3 10 40 min
4 25 60 min
5 12 35 min

Questions: 1. What is the EDD sequence? 2. What is maximum lateness? 3. How many patients wait past their triage time?

EDD Practice Solution

βœ… Answer

EDD Sequence: 2(30) β†’ 5(35) β†’ 3(40) β†’ 1(50) β†’ 4(60)

Patient Time \(C_i\) \(d_i\) \(L_i\) Tardy?
2 15 15 30 -15 No
5 12 27 35 -8 No
3 10 37 40 -3 No
1 20 57 50 +7 Yes
4 25 82 60 +22 Yes
  • Maximum lateness: 22 minutes
  • Tardy patients: 2 out of 5

Comparing the Three Rules

Summary Table

πŸ“Š Quick Reference

Rule Based On Optimal For Good For Bad For
FCFS Arrival order Fairness Service industry, similar jobs Efficiency, deadlines
SPT Processing time Mean flow time Throughput, many short jobs Long jobs, fairness
EDD Due date Max lateness Critical deadlines Flow time

Rule Selection Guidelines

🎯 How to Choose?

Choose FCFS when:

  • Fairness is critical
  • Service industry setting
  • Customer expectations matter
  • Processing times similar

Choose SPT when:

  • Need high throughput
  • Want to minimize WIP
  • Flow time is key metric
  • Many short jobs exist

Rule Selection Guidelines (continued)

🎯 How to Choose? (continued)

Choose EDD when:

  • Deadlines are critical
  • Penalties for lateness
  • Customer commitments
  • Want to minimize worst case

Advanced Concepts

Weighted Jobs

βš–οΈ When Jobs Have Different Importance

Some jobs are more important than others!

Weight \(w_i\) represents:

  • Customer priority
  • Revenue value
  • Strategic importance
  • Penalty cost

New Objective

Minimize weighted flow time: \(\sum w_i F_i\)

Or weighted tardiness: \(\sum w_i T_i\)

Weighted Shortest Processing Time (WSPT)

πŸ“Š Modified SPT Rule

WSPT Rule: Process jobs in order of highest weight-to-time ratio

\(\text{Priority} = \frac{w_i}{p_i}\)

  • High weight, short time β†’ Process first
  • Low weight, long time β†’ Process last

Property: WSPT minimizes weighted mean flow time!

WSPT Example

πŸ’Ž Jewelry Repair Shop

4 repair jobs with different values

Job Time (hrs) Weight (value) \(w_i/p_i\)
A 3 6 2.0
B 5 15 3.0 βœ“
C 2 4 2.0
D 4 8 2.0

WSPT Sequence: B(3.0) β†’ A=C=D(2.0, break ties by SPT) Final: B β†’ C β†’ A β†’ D

Slack Time

πŸ“ Another Important Concept

Slack = How much β€œbreathing room” a job has

\(\text{Slack}_i = d_i - p_i - t\)

Where:

  • \(d_i\) = due date
  • \(p_i\) = processing time
  • \(t\) = current time

Interpretation:

  • Large slack β†’ Job can wait
  • Small/negative slack β†’ Job is urgent!

Minimum Slack (MS) Rule

⏰ Dynamic Priority Rule

MS Rule: Always process job with smallest slack

Initial Calculation (t=0):

Job \(p_i\) \(d_i\) Slack = \(d_i - p_i - 0\)
1 4 12 12 - 4 = 8
2 3 8 8 - 3 = 5 βœ“
3 5 15 15 - 5 = 10

Process job 2 first (smallest slack = 5)

Warning

Note: Slack changes as time passes! Must recalculate.

MS Rule - Complete Example

🏭 Manufacturing Shop

4 parts need machining at a CNC center

Part Processing Time (\(p_i\)) Due Date (\(d_i\))
A 6 20
B 4 12
C 8 25
D 5 15

Apply Minimum Slack rule starting at t = 0

MS Rule - Step-by-Step Solution

Step 1: Calculate initial slack at t = 0

Part \(p_i\) \(d_i\) Slack = \(d_i - p_i - 0\) Rank
A 6 20 20 - 6 - 0 = 14 3rd
B 4 12 12 - 4 - 0 = 8 1st βœ“
C 8 25 25 - 8 - 0 = 17 4th
D 5 15 15 - 5 - 0 = 10 2nd

Select Part B (minimum slack = 8)

Process B from t=0 to t=4

MS Rule - Continue After First Job

Step 2: Recalculate slack at t = 4 (after B completes)

Part \(p_i\) \(d_i\) Slack = \(d_i - p_i - 4\) Rank
A 6 20 20 - 6 - 4 = 10 2nd
C 8 25 25 - 8 - 4 = 13 3rd
D 5 15 15 - 5 - 4 = 6 1st βœ“

Select Part D (minimum slack = 6)

Process D from t=4 to t=9

MS Rule - Final Steps

Step 3: Recalculate slack at t = 9

Part \(p_i\) \(d_i\) Slack = \(d_i - p_i - 9\) Rank
A 6 20 20 - 6 - 9 = 5 1st βœ“
C 8 25 25 - 8 - 9 = 8 2nd

Select Part A, then Part C

Final MS Sequence: B β†’ D β†’ A β†’ C

MS Rule - Performance Results

Complete Schedule:

Part \(p_i\) Start \(C_i\) \(F_i\) \(d_i\) \(L_i\) \(T_i\)
B 4 0 4 4 12 -8 0
D 5 4 9 9 15 -6 0
A 6 9 15 15 20 -5 0
C 8 15 23 23 25 -2 0

Results

  • Mean Flow Time: (4+9+15+23)/4 = 12.75 hours
  • All jobs on time! (0 tardy jobs)
  • MS rule is good for balancing urgency