Scheduling & Sequencing: Jobs, Queues, and Critical Paths

TAKEAWAYS:

• Learn how job sequencing prioritizes tasks to minimize idle time and meet deadlines.
• Understand critical path method (CPM) and program evaluation and review technique (PERT) for project scheduling.
• Apply Gantt charts to visualize project timelines and dependencies.
• Compare single-machine vs. multi-machine scheduling strategies.
• Solve queueing theory problems to optimize waiting lines in services.
• Use sequencing algorithms (e.g., shortest processing time first) for efficient task ordering.

1. Introduction to Scheduling and Sequencing

Scheduling and sequencing are core operations management techniques used to allocate resources, tasks, and time efficiently. While scheduling refers to assigning tasks to specific times or resources, sequencing determines the order in which tasks should be performed. Both are critical in manufacturing (e.g., assembly lines), logistics (e.g., delivery routes), and service industries (e.g., hospital patient flow).

2. Job Sequencing

Job sequencing determines the optimal order of jobs to minimize completion time or maximize efficiency. Common methods include:

A. Shortest Processing Time (SPT) Rule

The SPT rule prioritizes jobs with the shortest processing time first, reducing average waiting time.

Example: Suppose three jobs (A, B, C) with processing times:

• A: 5 units
• B: 3 units
• C: 4 units

Sequencing: B → C → A Total completion time: 12 units (vs. 14 if ordered A → B → C).

B. Earliest Due Date (EDD) Rule

The EDD rule prioritizes jobs with the earliest deadlines to minimize late deliveries.

Example:

Sequencing: Y → X → Z Late jobs: 0 (vs. 1 if ordered X → Y → Z).

Comparison Table: SPT vs. EDD

3. Project Scheduling: CPM and PERT

For complex projects, Critical Path Method (CPM) and Program Evaluation and Review Technique (PERT) help identify the longest path (critical path) that determines project duration.

A. Critical Path Method (CPM)

• Definition: A deterministic method where all task durations are known.
• Key Steps:
  1. Draw an activity-on-node (AON) diagram.
  2. Calculate earliest start (ES), earliest finish (EF), latest start (LS), and latest finish (LF).
  3. Identify the critical path (longest path with zero slack).

Example: Consider a project with activities:

• A → B → C
• A → D → C
• Durations: A=2, B=3, C=1, D=4

graph TD
    A["Start"] --> B["Task B: 3"]
    A --> D["Task D: 4"]
    B --> C["Task C: 1"]
    D --> C
    C --> E["End"]

Critical Path: A → D → C (Duration = 7)

B. Program Evaluation and Review Technique (PERT)

• Definition: A probabilistic method where task durations are estimated as optimistic (O), most likely (M), and pessimistic (P).
• Expected Time (TE): $$TE=\frac{O+4M+P}{6}$$
• Variance (σ²): $${\sigma }^2={\left(\frac{P-O}{6}\right)}^2$$

Example:

TE for X: $$\frac{2+4(4)+6}{6}=4$$ TE for Y: $$\frac{3+4(5)+7}{6}=5$$

4. Gantt Charts for Visual Scheduling

A Gantt chart is a bar chart that shows project tasks over time, including dependencies.

Example (Nepal’s Daraz Delivery Scheduling):

gantt
    title Daraz Order Fulfillment Schedule
    dateFormat  YYYY-MM-DD
    section Order Processing
    Pickup Order :a1, 2024-05-01, 1d
    Packaging    :after a1, 1d
    Dispatch     :after Packaging, 1d

5. Single-Machine vs. Multi-Machine Scheduling

A. Single-Machine Scheduling

• Problem: Assign jobs to a single machine to minimize completion time.
• Methods:
  • SPT (for minimizing average completion time).
  • EDD (for meeting deadlines).

B. Multi-Machine Scheduling

• Problem: Assign jobs to multiple machines with dependencies.
• Example: Assembly line scheduling in a car manufacturing plant.

Comparison:

6. Queueing Theory and Waiting Lines

Queueing theory models customer waiting times in services (e.g., banks, hospitals, eSewa transactions).

Key Terms:

• Arrival Rate (λ): Customers per unit time.
• Service Rate (μ): Customers served per unit time.
• Utilization (ρ): $$\rho =\frac{\lambda }{\mu }$$
• Average Waiting Time (Wq): $$Wq=\frac{\rho }{\mu (1-\rho )}$$

Example (NTC Customer Service Queue):

• λ = 10 customers/hour
• μ = 12 customers/hour
• ρ = 10/12 = 0.833
• Wq = (0.833)/(12(1-0.833)) ≈ 5.5 hours

7. Sequencing Algorithms for Multi-Task Systems

A. Johnson’s Rule (Two-Machine Flow Shop)

For two machines, minimize total completion time by sequencing jobs optimally.

Example:

Optimal Sequence: B → A → C (Total time = 10)

B. Moore’s Algorithm (General Flow Shop)

Extends Johnson’s rule for more than two machines.

In the Real World

1. eSewa Transaction Processing

   • Idea: Queueing theory is used to model customer transaction queues during peak hours (e.g., Diwali sales).
   • How: eSewa adjusts server capacity (μ) based on arrival rates (λ) to minimize waiting times.

2. Daraz Order Fulfillment

   • Idea: Job sequencing (SPT rule) prioritizes orders with shortest processing times (e.g., small, lightweight items) to reduce delivery delays.
   • How: Daraz uses AI to dynamically reorder warehouse tasks based on real-time demand.

3. NTC Customer Service Centers

   • Idea: Queueing theory predicts wait times during peak call volumes (e.g., during power outages).
   • How: NTC deploys additional agents (increases μ) during emergencies to reduce Wq.

Worked Example: Critical Path in a Construction Project

Project Tasks:

• Foundation (F): 5 days
• Framing (Fr): 7 days (depends on F)
• Roofing (R): 4 days (depends on Fr)
• Interior (I): 6 days (depends on Fr and R)

graph TD
    Start --> F["Foundation: 5"]
    F --> Fr["Framing: 7"]
    Fr --> R["Roofing: 4"]
    Fr --> I["Interior: 6"]
    R --> I
    I --> End

Critical Path: Start → F → Fr → R → I (Total = 22 days)

Advantages and Disadvantages

Exam Tip

• Focus on:
  • CPM/PERT diagrams (always draw them).
  • SPT vs. EDD (know when to use each).
  • Gantt charts (practice constructing them).
  • Queueing formulas (memorize Wq and ρ).
  • Johnson’s Rule (prioritize for two-machine scheduling).
• Common Pitfalls:
  • Mixing up ES/EF with LS/LF in CPM.
  • Forgetting to calculate critical path slack.
  • Misapplying SPT vs. EDD in sequencing problems.
• Real-World Link:
  • Always relate scheduling to Nepali examples (e.g., Pathao driver routes, Ncell network maintenance).
  • For global examples, use Amazon warehouse sequencing or Google data center task scheduling.

Final Note: Scheduling and sequencing are not just theoretical—they directly impact cost, efficiency, and customer satisfaction. In exams, expect numerical problems (CPM, PERT, queueing) and short-answer questions on sequencing rules. Practice drawing diagrams (Gantt, AON) to score full marks.