Unit IV: Sequencing & Queuing Theory
What is a Sequencing Problem?
Sequencing means deciding the order in which jobs (tasks) should be processed on machines to optimize a goal—typically minimize total processing time, idle time, or makespan (total completion time).
Johnson’s Algorithm for n Jobs and 2 Machines
Used when n jobs need to be processed in the same order on 2 machines (say Machine A then Machine B).
Assumptions:
- Each job must be processed on Machine A first, then Machine B.
- No job can be processed on both machines at the same time.
- The sequence is same for both machines.
Steps to Apply Johnson’s Rule:
- List processing times of all jobs on both machines.
- Find the job with the smallest processing time among all remaining.
- If the smallest time is on Machine A, schedule that job as early as possible.
- If the smallest time is on Machine B, schedule it as late as possible.
- Remove that job from the list and repeat until all jobs are scheduled.
Johnson’s Algorithm for n Jobs and 3 Machines
Applicability:
This can be converted to a 2-machine problem using a transformation method,
only if:
min(Ai) ≥ max(Bi) or min(Ci) ≥ max(Bi)
Where:
- A = processing time on Machine 1
- B = processing time on Machine 2
- C = processing time on Machine 3
Steps: Check the above condition.
Define:
- G₁ = A + B (for Machine 1 and 2 combined)
- G₂ = B + C (for Machine 2 and 3 combined)
- Now apply Johnson’s 2-machine rule on G₁ and G₂.
- The resulting sequence is applied to the original 3-machine setup.
Note: If the condition is not met, Johnson’s rule cannot be applied,
and other methods like enumeration or heuristics are used.
Two Jobs and m Machines Problem
Used when only 2 jobs are to be processed in the same order on m machines.
Assumptions:
- Two jobs (say J1, J2) need to go through m machines in same sequence.
- No machine can handle more than one job at a time.
Steps to Solve:
- Draw a table of processing times for each job on each machine.
- Calculate the cumulative time taken by each job on all machines.
- Prepare a time chart (Gantt chart) to visually represent:
- Start and end time for each job on each machine.
- Idle time for machines.
Compute:
- Total processing time
- Idle time
- Makespan (completion time of last job)
What is Queuing Theory?
Queuing Theory is the mathematical study of waiting lines (queues). It
helps businesses and services manage customer flow, reduce waiting time,
and improve service efficiency.
Characteristics of M/M/1 Queue Model
- The M/M/1 model is one of the most common queuing systems. It refers to:
- M = Markovian (Poisson) arrival process
- M = Markovian (Exponential) service time
- 1 = Single server
Key Characteristics:
Important Notations:
Applications of Poisson and Exponential Distribution
These distributions are used to model random events in a queuing system:
📌 Poisson Distribution (for Arrivals)
Models the number of arrivals per unit time.
Formula:
Example: Number of people arriving at a bank counter per minute.
📌 Exponential Distribution (for Service Time)
Models the time between two events (like service completions).
Formula:
Example: Time taken to serve a customer at a billing counter.
Applications of Queue Model for Better Customer Service
Queuing models are widely used to optimize service systems and reduce waiting times.
