QUANTITATIVE TECHNIQUES FOR MANAGERS KMB-206
UNIT-IV
SEQUENCING PROBLEM & QUEUINGN THEORY
SEQUENCUNG PROBLEM-
The selection of an appropriate order in which to service waiting customers (jobs) is called
Sequencing.
In other words sequencing is the selection of appropriate order in which a no. Of job can be assign to
a finite no. of service facilities so as to optimize the output in terms of time, cost or profit. One of the
common problem in production process is allocation of jobs on machine so as to have optimum
utilization it is a function of the order in which a service of task are perform.
Terminology use in sequencing-
1) No. of machine
2) Processing order
3) Processing time
4) Idle Time
5) Total elapsed time
Sequencing problem can be solved in different cases.
PROCESSING n JOBS THROUGH TWO MACHINES
The sequencing problem with n jobs through two machines can be solved easily. S.M.
Johnson has developed solution procedure. The problem can be stated as follows.
1) Only two machines are involved, A and B.
2) Each job is processed in the order AB.
3) The exact or expected processing times A1, A2, ..., An, B1, B2, ..., Bn are known
A decision has tobe arrived to find the minimum elapsed time from the start of the first job tothe com
pletion of the last job. It has been established that the sequence that minimizes the elapsedtime are the
same for both machines. The algorithm for solving the problem is as follows and due to
S.M. Johnson.
1)
Select the smallest processing time occurring in the list, A1, ..., An, B1, ... , Bn. If there is
a tie, break the tie arbitrarily.
2)
If the minimum processing time is Ai, do the i th job first. If it is Bj does the jth job last.
This decision is applicable to both machines A and B.
3)
Having selected a job to be ordered, there are now n-1, jobs left to be ordered. Apply
the steps 1 and 2
to the reduced set of processing times obtained by deleting the twomachine processing times c
orresponding to the job that is already assigned.
4)
Continue in this manner until all jobs have been ordered. The resulting ordering will
minimize the elapsed time, T.
Sequencing Problem
1) Two Machine, Many job
2) Three Machine, Many job
3) Many Machine, Many job
Example 1: Six jobs go first over machine I and then over II. The order of the completion of jobs has
no significance. The following table gives the machine times in hours for six jobs on the two
machines:
Job 1 2 3 4 5 6
M1 5 9 4 7 8 6
M2 7 4 8 3 9 5
Find the sequence of the jobs that minimize the total elapsed time to complete the jobs.
Solution 1: Sequence order-
Process time 3 1 5 6 2 4
M2
M1 1 2 3 4 5 6
Minimum elapsed Time-
M1 M2
Job
S.N. Pro. Time Idle Time Idle
order Pro.T.
T. in- out time in-out time
1 3 4 0-4 0 8 4-12 4
2 1 5 4-9 0 7 12-19 0
3 5 8 9-17 0 9 19-28 0
4 6 6 17-23 0 5 28-33 0
5 2 9 23-32 0 4 33-37 0
6 4 7 32-39 0 3 39-42 2
0 6
Idle time M1= 0, M2 =6, Total elapsed time = 42 hours.
n Jobs and Three Machines
n Jobs and Three Machines
This case is similar to the previous case except that instead of two machines, there are three
machines. Problems falling under this category can be solved by the method developed by Johnson.
Following are the two conditions of this approach:
The smallest processing time on machine A is greater than or equal to the greatest processing time on
machine B, i.e.,
Min. (Ai) ≥ Max. (Bi)
The smallest processing time on machine C is greater than or equal to the greatest processing time on
machine B, i.e.,
Max. (Bi) ≤ Min. (Ci)
At least one of the above two conditions must be satisfied.
If either or both of the above conditions are satisfied, then we replace the three machines by two
fictitious machines G & H with corresponding processing times given by
Gi =Ai +Bi
Hi = Bi + Ci
Where Gi & Hi are the processing times for ith job on machine G and H respectively.
After calculating the new processing times, we determine the optimal sequence of jobs for the
machines G & H in the usual manner.
Example 2: Processing n Jobs Through 3 Machines
The MDH Masala company has to process five items on three machines:- A, B & C. Processing times
are given in the following table:
Item Ai Bi Ci
1 4 4 6
2 9 5 9
3 8 3 11
4 6 2 8
5 3 6 7
Find the sequence that minimizes the total elapsed time.
Solution.2:
Here, Min. (Ai) = 3, Max. (Bi) = 6 and Min. (Ci) = 6. Since the condition of Max. (Bi) ≤ Min. (Ci) is
satisfied, the problem can be solved by the above procedure. The processing times for the new
problem are given below.
Item Gi = Ai + Bi Hi = Bi + Ci
1 8 10
2 14 14
3 11 14
4 8 10
5 9 13
The optimal sequence is
1 4 5 3 2
Item Machine A Machine B Machine C
Time in Time out Time in Time out Time in Time out
1 0 4 4 8 8 14
4 4 10 10 12 14 22
5 10 13 13 19 22 29
3 13 21 21 24 29 40
2 21 30 30 35 40 49
Total elapsed time = 49
Idle time for machine
A=49–30=19hours
Idle time for machine B = 4 + (10 – 8) + (13 – 12) + (21 – 19)+ (30 – 24) + (49 – 35) = 29 hours
Idle time for machine C = 8 + (14 – 14) + (22 – 22) + (29 – 29)+ (40 – 40) = 8 hours
Example-3:
Shahi Export House has to process five items through three stages of production, viz, cutting, sewing
& pressing. Processing times are given in the following table:
Cutting Sewing Pressing
Item
(Ai) (Bi) (Ci)
1 3 3 5
2 8 4 8
3 7 2 10
4 5 1 7
5 2 5 6
Determing an order in which these items should be processed so as to minimize the total processing
time.
Solution-3:
The processing times for the new problem are given below.
Item Gi = Ai + Bi Hi = Bi + Ci
1 6 8
2 12 12
3 9 12
4 6 8
5 7 11
Thus, the optimal sequence may be formed in any of the two ways.
1 4 5 3 2
4 1 5 3 2
Item Cutting Sewing Pressing
Time
Time in Time out Time in Time out Time in
out
1 0 3 3 6 6 11
4 3 8 8 9 11 18
5 8 10 10 15 18 24
3 10 17 17 19 24 34
2 17 25 25 29 34 42
Total elapsed time = 42
Idle time for cutting process = 42 – 25 = 17 hours
Idle time for sewing process = 3 + (8 – 6) + (10 – 9) + (17 – 15)+ (25 – 19) + (42 – 29) = 27 hours.
Idle time for pressing process = 6 + (11 – 11) + (18 – 18) + (24 – 24)+ (34 – 34) = 6 hours.
Example 4: A book binder has one printing press, one binding machine and manuscripts of a number
of different books. Times required to perform the printing and binding operation for each book are
known.
Determine the order in which the books should be processed in order to minimize the total time
required to process all the books.
Processing time (in minutes)
Book
1 2 3 4 5
Printing time 40 90 80 60 50
Binding time 50 60 20 30 40
Suppose that an additional operation is added to the process described above, as finishing. The times
required for operations are given below:
Finishing time (in minutes)
Book
1 2 3 4 5
Finishing time 80 100 60 70 100
What is the order in which the books should be processed and find also the total elapsed time.
Solution 4: Optimum sequence order as follows-
Books
1 2 3 4 5
P+B(M1) 90 150 100 90 90
B+F(M2) 130 160 80 100 140
Sequence Order-
Processing time 5 1 4 2 3
M2
M1 1 2 3 4 5
Minimum Elapsed time-
M1 [Printing] M2 [Binding] M3 [Finishing]
Job Time Time Time
S.N. Pro.
order in- Pro.T. in- Pro.T. in-
T.
out Idle time out Idle time out Idle time
50- 90-
1 5 50 0-50 0 40 90 50 100 190 90
90- 190-
2 1 40 50-90 0 50 140 0 80 270 0
90- 150- 270-
3 4 60 150 0 30 180 10 70 340 0
150- 240- 340-
4 2 90 240 0 60 300 60 100 440 0
240- 320- 440-
5 3 80 320 0 20 340 20 60 500 0
0 140 90
Total elapsed time= 500 minutes
Idle time of M1 = Elapsed time-[time out of last worker in M1+ sum of idle time of M1]
= 500-320+0 = 180 minutes
Idle time of M2 = Elapsed time-[time out of last worker in M2+ sum of idle time of M2]
= 500-340+140 = 300 minutes
Idle time of M3 = Elapsed time-[time out of last worker in M3+ sum of idle time of M3]
= 500-500+90 = 90 minutes
Queuing theory
It is a common phenomenon in everyday life to see a large number of persons waiting in front of a
booking counter, in a railway station or in a theatre or in a ration shop to have some service carried
out. This waiting problem leads the Danish engineer A.K. (Agner Krarup) Erlang, who worked for
the Copenhagen Telephone Exchange to find a solution. He developed in 1903 the Queuing theory.
Queuing theory is the mathematical study of waiting lines, or queues.
In queueing theory a model is constructed so that queue lengths and waiting time can be
predicted. Queueing theory is generally considered a branch of operations research because the results
are often used when making business decisions about the resources needed to provide a service.
Waiting customer
Input Arrival processQueuing Service
queue discipline Departure(system output)
source process mechanism
The basic queuing process
Elements of Queuing system are-
The basic queuing process consist of-
a) Input source- Its belongs to its size and pattern of arrival
b) Queue- Define as maximum no. of customers
c) Service discipline- Various scheduling policies can be used at queuing nodes:
First in first out -This principle states that customers are served one at a time and that the customer
that has been waiting the longest is served first
Last in first out - This principle also serves customers one at a time, but the customer with the
shortest waiting time will be served first. Also known as a stack.
d) Service mechanism- Service Mechanism Consists of one or more service facilities, each of
which contains one or more parallel service channels, called servers. At a given facility, the
customer enters one of the parallel service channels and is served by that server. Most
elementary models assume one service facility with either one or a finite number of servers.
Service time is usually defined by a probability distribution
e) System output- It refers to the rate at which customers are rendered service.
The average no. of customers that can be served per unit time is called service rate. It is denoted by μ,
and the reciprocal of service rate is called service time = 1/μ
Model-1: Single server Poisson Arrivals with exponential service infinite population model
(M/M/1): (FCFS/ /∞/∞)-
Assumption-
1) Both the arrivals and service rates are independent of the no. of customers in the waiting line.
2) The arrivals occur completely at random according to Poisson distribution.
3) There is only one queue and one service facility.
4) The arrivals are handled on FCFS (first come first served) bases.
5) The mean service rate is higher than the mean arrival rate. (μ >λ).
Important Formula-
1) Probability that there is no one in the system (No. one in the queue and no one being served)-
P0 = 1-[ λ/μ]
2) Probability that the customer will have to wait in queue (service facility is busy).
Pb = [ λ/μ]
3) Average expected no. of customers in the queue (queue length)-
Lq = λ2 /μ (μ/ λ)
4) Average expected no. of customers in the queue system (system length)
Ls = λ / (μ-λ)
5) Average waiting time in the queue-
Wq = λ /μ (μ/ λ)
6) Average time in the queue system ( waiting time + service time)-
Ws = 1 / (μ-λ)
λ= Arrival rate
μ= Service time
Jockeying in Queuing Theory
What is jockeying?
If you’ve ever been stuck in traffic, you’re already acquainted with a perfect analogy for jockeying in
queuing theory. Annoyed drivers zip back and forth between lanes in a desperate attempt to crawl
faster than the cars next to them.
And often, they choose wrong.
In the same vein, consumer habits dictate that customers want to get to the register fast. If we see
another lane moving quicker than our own, we rationalize that it’s faster to jump ship and try your
luck on the next lane.
This line-jumping is called jockeying behavior.
