Sequential Model, Queuing Theory and Related Problems
2.1 INTRODUCTION
Scheduling means deciding the order (sequence) and timing in which jobs are
processed on machines.
It involves planning for:
o Jobs
o Workers
o Materials
o Machines
o Other resources
Purpose of Scheduling
Minimize customer waiting time
Meet delivery deadlines
Reduce inventory (stock) levels
Ensure efficient use of machines
Provide better working conditions
General Sequential Problem
There are n jobs and m machines.
Each job must be processed on all machines in a given order.
Only one job at a time can be processed on a machine.
Objective
To find the best sequence of jobs (out of n! possible sequences) such that:
Total elapsed time is minimized
Notations
tijt_{ij}tij = Processing time of job i on machine j
TTT = Total elapsed time (including idle time)
III = Idle time of machine between jobs
2.2 BASIC TERMINOLOGY
(1) Number of Machines:
The number of machines refers to the number of service facilities through which a job must
pass before it is assumed to be completed.
(2) Processing Time:
This is the time required by a job on each machine.
(3) Processing Order:
This refers to the sequence in which machines are required for completing the job.
(4) Idle Time on a Machine:
This is the time during which a machine does not have a job to process, i.e., idle time from
the end of job (i–1) to the start of job i.
(5) Total Elapsed (Gone) Time:
This is the time interval between starting the first job and completing the last job, including
the idle time (if any), in a particular order/sequence by the given set of machines.
(6) No Passing Rule:
This rule maintains the order in which jobs are to be processed on given machines.
For example, if n jobs are to be processed on two machines M1 and M2 in the order M1 →
M2, then each job should first go to machine M1 and then to machine M2.
2.4 Processing of n Jobs through 2 Machines (Johnson’s Rule)
Concept
When n jobs are to be processed on 2 machines (M1 and M2) in the same order (first M1,
then M2), the objective is to:
👉 Minimize total elapsed time (makespan)
👉 Reduce idle time of machines
This problem is solved using Johnson’s Rule.
Assumptions
1. Each job is processed on M1 first, then M2.
2. Processing times are known and constant.
3. A machine can handle only one job at a time.
4. No passing rule is followed (same sequence on both machines).
5. Once processing starts, it cannot be interrupted.
Notation
nnn = number of jobs
t1it_{1i}t1i = processing time of job iii on Machine M1
t2it_{2i}t2i = processing time of job iii on Machine M2
Johnson’s Algorithm (Step-by-Step)
Step 1: List all jobs
Write processing times of all jobs on M1 and M2.
Step 2: Find smallest processing time
From all remaining jobs, find the minimum processing time.
Step 3: Apply rule
If the smallest time is on M1 →
👉 Place that job at the beginning of the sequence.
If the smallest time is on M2 →
👉 Place that job at the end of the sequence.
Step 4: Remove the job
Remove the selected job from the list.
Step 5: Repeat
Repeat Steps 2–4 until all jobs are scheduled.
Step 6: Final sequence
The obtained sequence is optimal (minimum total elapsed time).
Jobs with small M1 time → early position
Jobs with small M2 time → last position
2.6 QUEUE THEORY
Introduction
The objective of queuing analysis is to provide efficient service to waiting
customers.
It helps measure performance such as:
o Average waiting time
o Queue length
o Service efficiency
It is widely used in banks, hospitals, production lines, barber shops, etc.
Characteristics of Queue Model
Customers arrive at a service system (queue).
They wait in line if service is not immediately available.
One or more servers provide service.
After service, customers leave the system.
A queue system includes:
o Arrival of customers
o Waiting line
o Service facility
o Departure
1. Input Process (Arrival Pattern)
Customers (people, machines, etc.) enter the system.
Arrivals may be:
o Random
o Constant rate
Usually follows probability distribution (like Poisson distribution).
Customers join the queue and wait for service.
Arrival Behaviour of Customers
After arriving, customers may behave in the following ways:
1. Stay in the system until served
2. Wait for some time and leave if service is delayed
3. Join the queue and wait for service
4. Switch queues if multiple service facilities are available
2. Queue or Waiting Line
It includes customers waiting for service (excluding those being served).
(a) Waiting Time in Queue (Wq)
Time spent by a customer in the queue before service begins
(b) Waiting Time in System (Ws)
Total time spent in the system
👉 Ws = Waiting time + Service time
(c) Queue Length (Lq)
Number of customers waiting in the queue
(d) System Length (Ls)
Total number of customers in the system
👉 Includes:
Waiting customers
Customers being served
3. Service Facility (Servers)
These are the units that provide service (machines, clerks, etc.)
(a) Arrangement of Service
Service systems can be:
Single Queue – Single Server
Single Queue – Multiple Servers
Multiple Queues – Multiple Servers
Series, Parallel or Mixed arrangements
(b) Service Time
Time taken by server to serve a customer
May be:
o Constant
o Random
👉 Usually follows negative exponential distribution
👉 Denoted by μ (mu) (service rate)
(c) Service Discipline
Rule used to select next customer for service
Common Types:
FCFS (First Come First Serve)
FIFO (First In First Out)
Priority-based service
Random selection
Important Formula Concepts
Arrival Rate (λ) → Customers per unit time
Service Rate (μ) → Customers served per unit time
4. Departure
After completing service, the customer leaves the system.
Classification of Queuing Models
A queuing model is represented using Kendall’s Notation:
(a / b / c) : (d / e)
Where:
a → Arrival distribution (e.g., Poisson)
b → Service time distribution (e.g., Exponential)
c → Number of servers
d → Capacity of system
e → Service discipline
Common Models
(M/M/1) : (∞ / FCFS) → Single server
(M/M/C) : (∞ / FCFS) → Multiple servers
Meaning of Symbols
M (Markovian) → Poisson arrivals / Exponential service
C → Number of servers
∞ → Infinite population
FCFS → First Come First Serve
Single Server Queuing Model (M/M/1)
Model Form:
(M / M / 1) : (∞ / FCFS)
Assumptions
1. Arrival rate (λ) follows Poisson distribution
2. Service rate (μ) follows Exponential distribution
3. Only one queue and one server
4. Calling population is infinite
5. Queue discipline is FCFS (FIFO)
6. Waiting space is infinite
7. Mean arrival rate λ < μ (system must be stable)
Important Formulae
1. Probability that System is Idle , Also called traffic Intensity
Question:
Customers arrive at a one-window drive-in bank according to a Poisson distribution with a
mean of 10 customers per hour. The service time per customer follows an exponential
distribution with a mean of 5 minutes per customer.
Find:
1. What is the probability that an arriving customer can go directly to the service
window (i.e., no waiting)?
2. How long is an arriving customer expected to wait before starting service?
3. What is the probability that an arriving customer will have to wait?
Solution:
Given:
Question:
In a railway marshalling yard, goods trains arrive at a rate of 30 trains per day. The inter-
arrival time follows a Poisson distribution and the service time follows an exponential
distribution with an average of 36 minutes per train.
Find:
1. Mean queue size
2. Average time a train spends in the yard
3. Probability that queue size exceeds 10
4. Probability that an arriving train does not have to wait
Solution:
Given: