Chapte r 20

Sequencing Problems
“When everything seems to be going against you, remember that the airplane takes
off against the wind, not with it.”
– Henry Ford

PREVIEW
The sequencing techniques deals with the problem of preparing optimal timetable for jobs, equipment,
people, materials, facilities and all other resources that are needed to support the production schedule.
The objective is the minimization of the total elapsed time between the completion of first and last job in a
particular order.

LEARNING OBJECTIVES
After studying this chapter you should be able to
⌘ appreciate the aims to study sequencing techniques.
⌘ use Johnson’s rule of sequencing or scheduling.
⌘ solve some specific problems of scheduling jobs on one, two or three machines. ⌘
see how to extend Johnson’s rule to more complicated problems.

CHAPTER OUTLINE
• Hints and Answers
20.1 Introduction 20.5 Processing n Jobs Through m Machines 20.6
20.2 Notations, Terminology and Assumptions 20.3 Processing Two Jobs Through m Machines •
Processing n Jobs Through Two Machines • Conceptual Questions B
Conceptual Questions A • Self Practice Problems B
• Self Practice Problems A • Hints and Answers
• Hints and Answers ⑨ Chapter Summary
20.4 Processing n Jobs Through Three Machines • ⑨ Chapter Concepts Quiz
Self Practice Problems B
Sequencing Problem 709

20.1 INTRODUCTION
The optimal order (sequence) shows the minimum time in which jobs, equipment, people, materials,
facilities and all other resources are arranged to support the production schedules to give low costs and high
utilizations. Other objectives of calculating optimal production schedule are minimizing customers waiting
time for a product or service, meeting promised delivery dates, keeping stock levels low providing
preferred working pattern, and so on.
If n jobs are to be performed, one at a time, on each of m machines, where sequence (order) of the
machines in which each job should be performed, and the actual (or expected) time required by the jobs on
each of the machines are given, then the general sequencing problem is to find a sequence out of (n!)m
possible sequences, which minimize the total elapsed time between the start of the job on first machine and
the completion of the last job on the last machine.
In particular, if there are n = 3 jobs to be performed and m = 3 machines are to be used, then the total
number of possible sequences will be (3!)3 = 216. Theoretically, it may be possible to find the optimum
sequence but this would require a lot of computational time. Thus, one should adopt the sequencing
technique.
To find the optimum sequence, we first need to calculate the total elapsed time for each of the possible
sequences. As stated earlier, even if the values of m and n are very small, it is difficult to get the desired
sequence with the total minimum elapsed time. However, due to certain rules designed by Johnson, the task
of determining an optimum sequence has become quite easy.

20.2 NOTATIONS, TERMINOLOGY AND ASSUMPTIONS

Notations
order M1M2, then each job should go first to machine M1 and
tij = Processing time (time required) for job i on machine j.
T = Total elapsed time for processing all the jobs. This includes then to M2.
idle time, if any. Iij = Idle time on machine j from the end of job Assumptions
(i – 1) to the start of job i.
1. The processing time on different machines are exactly known
Terminology and are independent of the order of the jobs in which they are to
be processed.
⌘ Number of Machines The number of machines refer to the
2. The time taken by the job in moving from one machine to
number of service facilities through which a job must pass
another is negligible. 3. Once a job has begun on a machine, it
before it is assumed to be completed.
must be completed before another job can begin on the same
⌘ Processing Time This is the time required by a job on each
machine.
machine.
4. All jobs are known and are ready for processing before the
⌘ Processing Order This refers to the order (sequence) in which
period under consideration begins. 5. Only one job can be
machines are required for completing the job.
processed on a given machine at a time.
⌘ 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 6. Machines to be used are of different types.
end of job (i – 1) to the start of job i. 7. The order of completion of jobs are independent of the
⌘ Total Elapsed Time This is the time interval between starting
sequence of jobs.
Sequencing
the first job and completing the last job, including the idle time problem is the
(if any), in a particular order by the given set of machines. ⌘ No problem of finding an optimal sequence of completing certain number of
Passing Rule This refers to the rule of maintaining the order in jobs so as to minimize the total elapsed time between completion of first
which jobs are to be processed on given machines. For example, and last job.
if n jobs are to be processed on two machines, M1 and M2 in the
710 Operations Research: Theory and Applications

20.3 PROCESSING n JOBS THROUGH TWO MACHINES

Let there be n jobs, each of which is to be processed through two machines, M1 and M2 in the order M1M2,
i.e. each job has to pass through the same sequence of operations. In other words, a job is assigned on
machine M1 first and once processing is over on machine M1, it is assigned to machine M2. If the machine
M2 is not free for processing the same job, then the job is placed in waiting line for its turn on machine M2,
i.e. passing is not allowed.
will remain busy in processing all the n jobs one
Since passing is not allowed, therefore, machine M1
by-one, while machine M2 may remain idle waiting for the jobs to come from M1. The idle time for both M1
and M2 may be reduced by determining an optimal sequence of n jobs to be processed on two machines M1
and M2. The procedure suggested by Johnson for determining the optimal sequence is summarized as
follows:

20.3.1 Johnson’s Procedure

Step 1: List the jobs along with their processing times on each machine in a table, as shown below:
 Processing Time Job Number
on Machine
1 2 3 ... n

M1 t11 t12 t13 ... t1n

M2 t21 t22 t23 ... t2n

Step 2: Examine the processing times on machines M1 and M2, in each column of the table and find the
shortest processing time, i.e. find out, min. (t1j, t2j) for all j.
Step 3(a): If the shortest processing time is on machine M1, then place the job in the first available
position in the sequence. If the processing time is on machine M2, then place the job in the last available
position in the sequence.
(b) If there is a tie in selecting the minimum of all the processing times, then the following three situations
may arise:
(i) If minimum processing time is same on both machines, i.e. min (t1j, t2j) = t1k = t2r, then process the
kth job first and the rth job last.
(ii) If minimum processing times, t1j on machine M1 are same for more than two jobs, then select the
job corresponding to the smallest job subscript, j first.
(iii) If minimum processing times, t2j on machine M2 are same for more than two jobs, then select the
job corresponding to the largest job subscript, j last.
Step 4: Cross off assigned jobs from the table. If no job remains to be assigned, then stop the procedure
and go to Step 5. Otherwise, go to Step 2.

Step 5: Calculate the idle time for machines M1 and M2:

(a) Idle time for machine M1 = (Total elapsed time) – (Time when the last job in a sequence finishes
on machine M1)
(b) Idle time for machine M2 = Time when first job in a sequence finishes on machine M1
n
sequence starts on machine M2)
+∑ j=
2 {(Time when the jth job in a
– (Time when the ( j –1)th job in a sequence finishes on machine M2)}.
Step 6: The total elapsed time to process all jobs through two machines is given by: Total elapsed
time = Time when the nth job in a sequence finishes on machine M2.
n n
= ∑ +∑
j
MI 11
22
j
j
j==

where M2j = Time required for processing jth job on machine M2.
I2j = Idle time for machine M2 after processing (j – 1)th job and before the start of jth job
processing.
Sequencing Problem 711

Example 20.1 A book binder has one printing press, one binding machine and manuscripts of 7 different
books. The times required for performing printing and binding operations for different books are shown
below:

Book : 1234567
Printing time (hours) : 20 90 80 20 120 15 65
Binding time (hours) : 25 60 75 30 90 35 50
 Decide the optimum sequence of processing of books in order to minimize the total time required to
bring out all the books.
Solution Examine both printing and binding operations time columnwise. The smallest value is 15
printing hours for book 6. The book 6 is placed first in the sequence and cross off column 6 of the table.
Repeat the procedure of finding smallest processing time columnwise. Books 1 and 4 are placed in the
sequence as shown below:

614

Cross off columns 1, 4 and 6 of the table. For the remaining columns 2, 3, 5 and 7 the smallest time is
50 binding hours for book 7, so it should be sequenced in the last as shown below:

614 7

After this sequence, remaining set of printing and binding times gets reduced as follows:

Book : 2 3 5
Printing time : 90 80 120
Binding time : 60 75 90

The smallest time in this reduced data is 60, which corresponds to binding. So book 2 is placed in the
second cell from right. Proceeding in the same manner, the optimal sequence so obtained is shown below:

6145327

The total minimum elapsed time for printing and binding is given in Table 20.1.

Printing Binding
Book Time In Time Out Time In Time Out Idle Time
6 0 0 + 15 = 15 15 15 + 35 = 50 15
1 15 15 + 20 = 35 50 50 + 25 = 75 —
4 35 35 + 20 = 55 75 75 + 30 = 105 —
5 55 55 + 120 = 175 175 175 + 90 = 265 70
3 175 175 + 80 = 255 265 265 + 75 = 340 — 2 255 255 + 90 = 345 345 jobs on two machines A and B. Number of units of each job and
345 + 60 = 405 5 7 345 345 + 65 = 410 410 410 + 50 = 460 5 its processing times on A and B are given in the following table.
Find the optimum sequence, the total minimum elapsed time and
In Table 20.1, the minimum elapsed time, i.e. time from start of idle time for each machine.
printing book 6 to binding the last book 7 is 460 hours. During Table 20.1
this time the printing machine remains idle for 460 – 410 = 50 Minimum Elapsed Time
hours. The idle time for binding machine is shown in Table 20.1.
Example 20.2 A manufacturing company processes 6 different
712 Operations Research: Theory and Applications

Job Number No. of Units Processing Time (hours)

of Each Job
Machine A Machine B
1358
2 4 16 7
3 2 6 11
4535
5 2 9 7.5
6 3 614
 Solution Examine processing time of machines A and B. The smallest value is 3 minutes for job 4 on
machine A. Thus job 4 is scheduled first in the sequence as shown below:

Repeating this procedure, the optimal sequence so obtained is shown below. The calculations for total
elapsed time is shown in Table 20.2.

413652

342523 ← Number of units of each job.

Job Unit Number Machine A Machine B

Number of the Job
Time In Time Out Time In Time Out

4 1 0 3 38
2 3 6 8 12
3 6 9 13 18
4 9 12 18 23
5 12 15 23 28
1 1 15 20 28 36
2 20 25 36 44
3 25 30 44 52
3 1 30 36 52 63
2 36 42 63 74
6 1 42 48 74 88
2 48 54 88 102
3 54 60 102 116
5 1 60 69 116 123.5
2 69 78 123.5 131
2 1 78 94 131 138
Table 20.2 through the machines A and B in the order AB. Processing times
Total Minimum Elapsed Time in hours are as follows:
2 94 110 138 145 Job : 1 2 3 4 5 6 7
3 110 126 145 152
4 126 142 152 159 Machine A : 3 12 15 6 10 11 9
Machine B : 8 10 10 6 12 1 3
The total elapsed time for all the jobs including the number of Determine a sequence of these jobs that will minimize the total
units is 159 minutes. However, machine A remained idle for 17 elapsed time T. Also find T and idle time for machines A and B.
(= 159 – 142) minutes and machine B remained idle for 3 (3 + [Karn. Univ., BE (Mech.) 2000, G.J. Univ., BE 2001] Solution The
152 – 152) minutes. smallest processing time is 1 hour for job 6 on machine B. Thus
job 6 will be processed last on machine A as shown below:
Example 20.3 There are seven jobs, each of which has to go
Sequencing Problem 713

The reduced set of processing times becomes

Job : 1 2 3 4 5 7
Machine A : 3 12 15 6 10 9
Machine B : 8 10 10 6 12 3

There are two equal minimal values: processing time of 3 hours for job 1 on machine A and processing
time of 3 hours for job 7 on machine B. According to Johnson’s rules, job 1 is scheduled first and job 7 next
to 6 as shown below:
 176

The reduced set of processing times becomes

Job : 2 3 4 5
Machine A : 12 15 6 10
Machine B : 10 10 6 12
Again there are two equal minimal values: processing time of 6 hours for job 4 on machine A as well
as on machine B. We may choose arbitrarily to process (schedule) job 4 next to job 1 or next to job 7 as
shown below:

1476

or 1 476

The reduced set of processing times becomes

Job : 2 3 5
Machine A : 12 15 10
Machine B : 10 10 12
There are three equal minimal values: processing time of 10 hours for job 5 on machine A and for jobs
2 and 3 on machine B. According to rules: job 5 is scheduled next to job 4 in the first schedule or next to
job 1 in the second schedule. Job 2 then is scheduled next to job 7 in the first schedule or next to job 4 in
the second schedule. The optimal sequences are shown below:

1453276

or 1 5 3 2 4 7 6

The calculations for total elapsed time and idle times for machines A and B are shown in Table 20.3.

Machine A Machine B Idle for

Job Time in Time out Time in Time out Machine B

1 0 3 3 11 3
4 3 9 11 17 0
5 9 19 19 31 2
3 19 34 34 44 3
2 34 46 46 56 2 7 46 55 56 59 0 6 55 66 66 67 7 Table 20.3 Total Elapsed and Idle Time
714 Operations Research: Theory and Applications

The minimum elapsed time is 67 hours. Idle time for machine A is 1 hours (66th–67th hour) and for
machine B is 17 hours.
Example 20.4 A manufacturing company processes 6 different jobs on two machines A and B. Number
of units of each job and its processing times on A and B are given below. Find the optimal sequence, the
total minimum elapsed time and idle time for either machine.

Job Number Number of Units Processing Time (in Minutes)

of Each Job
Machine A Machine B

1 35 8
2 4 16 7
3 2 6 11
4 53 5
 5 2 9 7.5
6 36 14

[Punjab Univ., BCom 2004; Karn. Univ., BE (Mech.) 2001]

Solution The smallest processing time is 3 minutes for job 4 on machine A. Thus job 4 is scheduled first
on machine A as shown below:

(i) 4

Repeating the procedure as discussed in earlier examples, we get the following sequence of job scheduling

(ii) 4 1

(iii) 4136

(iv) 413652
532324 ← Number of units of each job
The optimal sequence as well as the number of units of each job are shown in (iv). The optimal
sequence is:
First : 5 units of job 4, Fourth : 3 units of job 6,
Second : 3 units of job 1, Fifth : 2 units of job 5,
Third : 2 units of job 3, Sixth : 4 units of job 2.
The calculations for total elapsed time are shown in Table 20.4

Job Unit Number of Machine A (in Minutes) Machine B (in Minutes) Idle Time
Number the Job
Time In Time Out Time In Time Out of Machine
(in minutes)

41 0 3 3 8 3
2 3 6 813 —
3 6 9 13 18 —
4 9 12 18 23 —
5 12 15 23 28 —

1 1 15 20 28 36 —
2 20 25 36 44 —
3 25 30 44 52 —

3 1 30 36 52 63 —
2 36 42 63 74 —
Table 20.4 Total Elapsed Time 6 1 42 48 74 88 — 2 48 54 88 102 — 3 54 60 102 116 —
Sequencing Problem 715

Job Unit Number of Machine A (in Minutes) Machine B (in Minutes) Idle Time
Number the Job
Time In Time Out Time In Time Out of Machine
(in minutes)

5 1 60 69 116 123.5 —
2 69 78 123.5 131 —

2 1 78 94 131 138 —
2 94 110 138 145 —
3 110 126 145 152 —
4 126 142 152 159 —

Thus, the total minimum elapsed time is 159 minutes, idle time for machine A is 17 minutes and for
machine B is 3 minutes.
 CONCEPTUAL QUESTIONS A
7. Give a mathematical formulation of the optimal assignment and
travelling salesman problems. In what ways do the feasible
1. Explain the four elements that characterize a sequencing problem.
solution matrices in the two cases differ?
2. Explain the principal assumptions made while dealing with
sequencing problems. 8. Explain briefly, the solution procedure of processing two jobs
through the machines when the technological ordering of each of
3. Give Johnson’s procedure for determining an optimal sequence for
the jobs through the machines is prescribed in advance. Establish
processing n items on two machines. Give justification of the rule
the following rule: If machine A precedes machine B for job 1 and
used in the procedure.
machine B precedes machine A for job 2, then no programme
4. What is no passing rule in a sequencing algorithm? Explain the that contains both the decisions: (a) job 2 before job 1, and (b) job
principal assumptions made while dealing with sequencing 1 before job 2 on machine B, is technologically feasible.
problems. [Meerut, MSc (Maths), 2002]
9. What do you understand by the problem of sequencing? Discuss
5. Give three different examples of sequencing problems from your the various aspects of data required to formulate the problem of
daily life. sequencing two jobs on m machines.
6. Write a short note on the ‘sequencing decision problem for n jobs
on two machines’.

SELF PRACTICE PROBLEMS A

processing time in hours required to complete the following jobs:

1. We have five jobs, each of which must be processed on the two Job : 123456
machines A and B, in the order AB. Processing times in hours are Machine A : 4 383 6 7 5 Machine B : 6 33 7 2 8 4 6. Six jobs
given in the table below: go over machine I first and then over II. The order of the completion
Job : 12345 of jobs has no significance. The following table gives the machine
times in hours for six jobs and the two machines.
Machine A : 5 1 9 3 10 Machine B :2 6 7 8 14
Job : 123456
Determine a sequence for the five jobs that will minimize the
Machine I :5 9 4 7 8 6 Machine II :7 4 8 3 9 5
elapsed time T.
2. A book binder has one printing press, one binding machine, and Find the sequence of the jobs that minimizes the total elapsed
manuscripts of a number of books. The time required to perform time for completing the jobs. Find the minimum time by using
the printing and binding operations on each book are shown Gantt Chart or by any other method.
below. The binder wishes to determine the order in which the 716 Operations Research: Theory and Applications
books should be processed, so that the total time required to
process all books is minimized. 7. We have five jobs, each of which must go through two machines
in the order AB. Their processing times are given below:
Book : 123456
Job : 12345
Printing time (Hours) : 30 120 50 20 90 110 Binding time
(Hours) : 80 100 90 60 30 110 [Delhi, MCom, 2000] Machine A : 10 12 18 16 20
3. Five jobs are performed, first on machine X and then on machine Machine B : 14 12 14 16 18
Y. The time taken, in hours by each job on each machine is given 8. A machine operator has to perform two operations, turning and
below: threading, on a number of different jobs. The time required to
perform these operations (in minutes) for each job is known.
Job : ABCDE
Time on machine X : 12 14 20 14 22 Time on machine
Y : 16 14 16 18 10
Determine the optimum sequence of jobs that minimizes the total Job Time of Turning Time of Threading (minutes)
elapsed time to complete the jobs. Also compute the minimum (minutes)
time. 13 8
4. The following table shows the machine time (in hours) for 5 jobs to 2 12 10
be processed on two different machines: 35 9
Job : 12345 42 6
59 3
Machine A :3 7 4 5 7 Machine B :6 2 7 3 4 6 11 1
Passing is not allowed. Find the optimal sequence in which jobs Determine the order in which the jobs should be processed in
should be processed. order to minimize the total time required to turn out all the jobs.
5. Find the sequence that minimizes the total elapsed time and

HINTS AND ANSWERS

= 40 hours.
3. Optimal sequence: B – D – C – E – A; Elapsed time = 48 hours.
1. Optimal sequence: 2 – 4 – 3 – 5 – 1; Elapsed time = 30 hours.
Idle time is 12 hours for machines X and Y each. 4. Optimal
Idle time for machine A = 2 hours, and for machine B = 3 hours. 2.
sequence: 1 – 3 – 5 – 4 – 2; Elapsed time = 28 hours. Idle time for
Optimal sequence: 4 – 1 – 3 – 2 – 5 – 6; Elapsed time = 430 hours.
machine A = 2 hours, and for machine B = 3 hours.
Idle time for printing machine = 10 hours, and for binding machine
 5. Optimal sequence: 3 – 1 – 5 – 6 – 2 – 4; Elapsed time = 35 hours. Optimal sequence: 4 – 1 – 3 – 2 – 5 – 6; Elapsed time = 43 minutes.
6. Optimal sequence: 3 – 1 – 5 – 6 – 2 – 4; Elapsed time = 35 hours. Idle time for turning operation = 1 minute, and for threading
7. Optimal sequence: 2 – 4 – 3 – 5 –1; Elapsed time = 60 hours. 8. operation = 6 minutes.

20.4 PROCESSING n JOBS THROUGH THREE MACHINES

An extension of Johnson’s procedure for scheduling jobs on two machines M1 and M2 in the order M1 M2
has been discussed in this section. The list of jobs with their processing times on three machines M1, M2
and M3 is given below. An optimal solution to this problem can be obtained if either or both of the
following conditions hold good:

Processing Time Job Number

on Machine 1 2 3 ... n

M1 t11 t12 t13 ... t1n

M2 t21 t22 t23 ... t2n
M3 t31 t32 t33 ... t3n

1. The minimum processing time on machine M1 is at least as great as the maximum processing time on
machine M2, that is, min t1j ≥ max t2j, for j = 1, 2, . . ., n
2. The minimum processing time on machine M3 is at least as great as the maximum processing time on
machine M2, that is, min t3j ≥ max t2j, for j = 1, 2, . . ., n
If either or both the above conditions hold good, then the steps of the algorithm can be
summarized in the following steps:

20.4.1 The Procedure

Step 1: Examine the processing times of the given jobs on all three machines and if either one or both the
above conditions hold, then go to Step 2, otherwise the algorithm fails.
Step 2: Introduce two fictitious machines, say G and H with corresponding processing times given by:

(i) tGj = t1j + t2j, j = 1, 2, . . ., n

that is, the processing time on machine G is the sum of the processing times on machines M1 and
M2, and
(ii) tHj = t2j + t3j, j = 1, 2, . . ., n
that is, processing time on machine H is the sum of the processing times on machines M2 and M3.
Sequencing Problem 717

Step 3: Determine the optimal sequence of jobs for this n-job, two machine equivalent sequencing
problem with the prescribed ordering GH in the same way as discussed earlier.
Example 20.5 Find the sequence that minimizes the total time required in performing the following jobs
on three machines in the order ABC. Processing times (in hours) are given in the following table:
Job : 12345

Machine A : 8 10 6 7 11
Machine B : 5 162 3 14
Machine C : 4 198 6 15
[IAS 1995; Anantpur Univ., MSc (Maths), 2000]

Solution From data of the problem, we know that min (tAj) = 6; min (tCj) = 4; max (tBj) = 6. Since min
(tAj) ≥ (tBj) for all j is satisfied, the given problem can be converted into a problem of 5 jobs and two
machines. The processing time on two dummy machines G and H can be determined by the following
relationships:
 tGj = tAj + tBj ; and tHj = tBj + tCj ; j = 1, 2, . . ., n
The processing times for the new problem are given below:
Job : 12345
Machine G : 8 + 5 = 13 10 + 6 = 16 6 + 2 = 18 7 + 3 = 10 11 + 4 = 15
Machine H : 5 + 4 = 19 16 + 9 = 15 2 + 8 = 10 3 + 6 = 19 4 + 5 = 9
When the procedure described for n jobs on two machines is applied to this problem, the optimal
sequence, so obtained, is given by:

32514

The total minimum elapsed time is given in Table 20.5.

Job Machine A Machine B Machine C

Sequence
Time In Time Out Time In Time Out Time In Time Out

3 0 6 6 8 8 16
2 6 16 16 22 22 31 process 7 items through two stages of production, viz., cutting
5 16 27 27 31 31 36 and sewing. The time taken for each of these items at the
1 27 35 35 40 40 44 different stages are given below in appropriate units:
4 35 42 42 45 45 51 Item : 1 2 3 4 5 6 7

Table 20.5 indicates that the minimum total elapsed time is 51 Process time Cutting : 5 7 3 4 6 7 12
hours. The idle time for machines A, B and C is 9(= 51 – 42)
Table 20.5
hours, 6(= 51 – 45) hours and 9{= (8 – 0) + (45 – 44)} hours,
Minimum Elapsed Time
respectively.
Example 20.6 A readymade garments manufacturer has to



Sewing : 2 6 7 5 9 58
(a) Find an order in which these items are to be processed through these stages so as to minimize the total
processing time.
(b) Suppose a third stage of production is added, viz. pressing and packing, with processing time for these
items as follows:
Item : 1 2 3 4 5 6 7 Processing time
(Pressing and Packing) : 10 12 11 13 12 10 11
Find an order in which these seven items are to be processed so as to minimize the time taken to
process all the items through all the three stages.
Solution Using Johnson’s optimal sequencing procedure, the optimal sequence so obtained is shown
below. The calculations for total elapsed time is shown in Table 20.6.
718 Operations Research: Theory and Applications

3457261

Item Cutting Sewing Idle Time for Time In Time Out Time In Time Out Sewing

3 0 3 3 10 3
4 3 7 10 15 —
 5 7 3 15 24 —
7 13 25 25 33 1
Table 20.6 algorithm, the optimal sequence so obtained is as follows:
Total Minimum Elapsed Time
1436257

The total elapsed time for three processes is given in Table 20.7.

Item Cutting Sewing Printing and Packing Time In Time Out Time In
Time Out Time In Time Out

1 0 5 5 7 7 17 4 5 9 9 14 17 30 3 9 12 14 21 30 41 6 12 19 21 26 41 51 2
19 26 26 32 51 63 5 26 32 32 41 63 75 7 32 44 44 52 75 86
The minimum total elapsed time is 86 hours with idle time of 42
hours for cutting, 44 hours for sewing and 7 hours for pressing
and packing.

SELF PRACTICE PROBLEMS B

1. We have six jobs, each of which must go through machines A, B

and C in the order ABC. Processing time (in hours) are given in the
following table:
Job : 1 2 3 4 56
Machine A :8 3 7 2 15 1 Machine B :3 4 5 2 11 6 Machine C : 8
7 6 9 10 9

Determine a sequence for the five jobs that will minimize the
elapsed time t.
2. Determine the optimal sequence of jobs that minimize the total
elapsed time, based on the following information. Processing time
on machines is given in hours and passing is not allowed.

Table 20.7 Job : ABCDEFG

Minimum Elapsed Time Machine (M1): 3 8 7 149 8 17 Machine (M2): 4 3 2 151 4 13
2 25 32 33 39 — 6 32 39 39 44 — 1 39 44 44 46 — Machine (M3) : 6 7 5 11 5 6 12
3. We have five jobs, each of which must go through the machines A,
The total elapsed time is 46 hours. Idle item on cutting machine B and C in the order ABC. Processing times (in hours) is as
is 2 (= 46 – 44) hours and on sewing machine 4 hours. follows:
(b) When the third stage of production (viz., pressing and
Job : 1 2 3 4 5
packing) is added, the problem is that of seven jobs on three
machines with processing time (in hours) given below: Machine A : 57695 Machine B : 21453 Machine C : 37567
Determine the sequence for the jobs that will minimize the total
Item : 1234567 elapsed time.
Cutting, Ci : 5 7 3 4 6 7 12 4. Find the sequence that minimizes the total elapsed time required to
Sewing, Si :2 6 7 5 9 5 8 complete the following tasks. Each job is processed in the order
ABC.
Pressing, Pi : 10 12 11 13 12 10 11
Sequencing Problem 719
Given that min (Ci) = 3, min (Pi) = 10 and max (Si) = 9. Since
the condition min (Pi) ≥ max (Si) for all i is satisfied, the Job : 1234567
problem can be converted into that of 7 jobs and 2 machines. If Machine A : 12 6 5 11 5 7 6 Machine B : 178 9 147 8 3
G and H are two fictitious machines such that Gi = Ci + Si and Hi Machine C : 134 1 152 3 4

= Si + Pi for all i, then the given problem can be re-written as the 5. A machine operator has to perform three operations, turning,
threading and knurling on a number of different jobs. The time
problem of two machines and 7 items with their processing times required to perform these operations (in minutes) for each job is
given below: known and is give below:

Item : 1234567 Gi : 5+2= 17 7 + 6 = 13 3 + 7 = 10 4 + 5 = 19 6 + 9 = 15

Job Time for Time for Time for Turning Threading Knurling
7 + 5 = 12 12 + 8 = 20 Hi : 2 + 10 = 12 6 + 12 = 18 7 + 11 = 18 5 + 13 = (minutes) (minutes) (minutes)
18 9 + 12 = 21 5 + 10 = 15 8 + 11 = 19 Using the optimal sequence 1 3 8 13 2 12 6 14 35 4 9 4 2 6 12 59 3 8 6 11 1 13
 order to minimize the total time required to turn out all the jobs.
Determine the order in which the jobs should be processed in

HINTS AND ANSWERS

for machine C.
1. Optimal sequences: (i) 4 – 5 – 2 – 6 – 1 – 3, (ii) 4 – 5 – 2 – 6 – 1 4. Optimal sequences: (i) 3 – 5 – 2 – 6 – 2 – 4 – 7, (ii) 3 – 5 – 6 – 2
– 3; Elapsed time = 53 hours. Idle time is 27 hours for machine – 1 – 4 – 7; Elapsed time = 59 hours; Idle time is 7 hours for
A; 32 hours for machine B and 4 hours for machine C. machine A; 13 hours for machine B and 37 hours for machine
C.
2. Optimal sequences: D – G – F – B – C – E; Elapsed time = 59
5. Optimal sequences: (i) 4 – 3 – 1 – 6 – 2 – 5; Elapsed time = 77
hours. Idle time is 13 hours for machine M1; 37 hours for
minutes; Idle time is 35 minutes for turning operation; 49
machine M2 and 7 hours for machine M3. minutes for threading operation and 8 minutes for knurling
3. Optimal sequences: (i) 2 – 5 – 4 – 3 – 1, (ii) 5 – 4 – 3 – 2 – 1, (iii) operation.
5 – 2 – 4 – 3 – 1; Elapsed time = 40 hours; Idle time
is 8 hours for machine A; 25 hours for machine B and 12 hours

20.5 PROCESSING n JOBS THROUGH m MACHINES

Let there be n jobs, each of which is to be processed through m machines, say M1, M2, . . ., Mm in the order
M1 M2 . . . Mm. The optimal solution to this problem can be obtained if either or both of the following
conditions hold good.

(a) Min {t1j} ≥ Max {tij} ; j = 2, 3, . . ., m – 1

and/or (b) Min {tmj} ≥ Max {tij} ; j = 2, 3, . . ., m – 1
that is, the minimum processing time on machines M1 and Mm is as great as the maximum processing time
on any of the remaining (m – 1) machines.
If either or both these conditions hold good, then the steps of the algorithm can be summarized in the
following steps:

Step 1: Find, Min {t1j}, Min {tmj} and Max {tij} and verify the above conditions. If either or both the
conditions mentioned above hold, then go to Step 2. Otherwise the algorithm fails.

Step 2: Convert m-machine problem into 2-machine problem by introducing two fictitious machines, say
G and H with corresponding processing times given by:
i(i) tGj = t1j + t2j + . . . + tm – 1j ; j = 1, 2, . . ., n
i.e. processing time of n-jobs on machine G is the sum of the processing times on machines M1, M2, . . .,
Mm–1, j
720 Operations Research: Theory and Applications

(ii) tHj = t2j + t3j + . . . + tmj ; j = 1, 2, . . ., n

i.e. processing time of n-jobs on machine H is the sum of the processing times on machines M2, M3, . . .,
Mm. Step 3: The new processing times, so obtained, can now be used for solving n-job, two-machine
equivalent sequencing problem with the prescribed ordering HG in the same way as discussed earlier.
Remarks 1. In addition to the conditions given in Step 2, if:
t2j + t3j + . . . + tm – 1, j = k (constant)
for all j = 1, 2, . . ., m – 1, then the optimal sequence can be obtained for n-jobs and two machines M1
and Mm in the order M1Mm as usual.
2. If t1j = tmj and tGj = tHj, for all j = 1, 2, . . ., n, then the total number of optimal sequences will be n and
total minimum elapsed time in these cases would also be the same.
3. The method described above for solving n-jobs and m-machines sequencing problem is not a general
 method. It is applicable only to certain problems where the minimum cost (or time) of processing the
jobs through first and/or last machine is more than or equal to the cost (or time) of processing the jobs
through the remaining machines.
Example 20.7 Find an optimal sequence for the following sequencing problems of four jobs and five
machines, when passing is not allowed. Its processing time (in hours) is given below:

Job Machine

M1 M2 M3 M4 M5
A 7523 19
B 6 6 4 5 10
C 5456 18
D 8332 16

Also find the total elapsed time.

Solution Here, Min ( ) , t M j 1 = 5 = t M C1 , ; Min ( ) , t M j 5 = 6 = t M D5 ,

and Max {, , } ,, , ttt Mj Mj M j 234 = {6, 5, 6} respectively.

Since the condition of Min ( ) , t M j 5 ≥ Max ttt Mj Mj Mj 234 ,,, ot

, , is satisfied, therefore the given
problem can be converted into a four jobs and two machines problem as G and H. The processing times of
four jobs denoted by tGj and tHj on G and H, respectively are as follows:
Job : ABCD
Machine G : 17 21 20 16
Machine H : 19 25 23 14
m − 1 m

ij = ==
=Σ Σ
Gj
where t t tt i and .

ij Hj
i1

2
optimal sequence can be obtained ACBD

The total elapsed time, corresponding to the optimal sequence

can be calculated as shown in Table 20.8, using the individual
processing times given in the original problem.
Table 20.8 shows that the minimum total elapsed time is 51
hours. The idle time for machines M1, M2, M3, M4 and M5 is 25,
33, 37 and 18 hrs, respectively.
Job Sequence Machine

M1 M2 M3 M4 M5
A 0–7 7–12 12–14 14–17 17–26
Table 20.8
C 7–12 12–16 16–21 21–27 27–35
Minimum Elapsed Time
B 12–18 18–24 24–28 28–33 35–45
Now, using the optimal sequence algorithm, the following
D 18–26 26–29 29–32 33–35 45–51
Sequencing Problem 721

Example 20.8 Solve the following sequencing problem, giving an optimal solution when passing is not
allowed.

Machine Job

A B C DE
 M1 11 13 9 16 17
M2 4 3 5 26
M3 6 7 5 84
M4 15 8 13 9 11
[Meerut, MSc (Maths), 2001]
Solution From the data of the problem it is observed that
Min Min ( ) ; ( ) t t t tMB 9 8
, , , , Mj MC Mj 1 1 4 4 == ==

and Max Max { } ; {} ,, ,, t t tt M j ME 2 2 33 == == 6 8 M j MD

Since both the conditions
Min Max { (} ; } , , , t tt M j Mj Mj 1 2 3 ≥
Min Max ( } { ; } ; , ,..., , ,, t tt j M j Mj Mj 4 2 3
≥ = 12 5
are satisfied, therefore the given problem can be converted into a 5-jobs and 2-machine problem as G and
H. Further, it may be noted that, t t Mj Mj 2 3 , , + = 10 (a fixed constant) for all j ( j = 1, 2, . . ., 5). Thus, the
given problem is reduced to a problem of solving 5-jobs through 2-machines M1 and M4 in the order M1M4.
This means machines M2 and M4 will have no effect on the optimality of the sequences.
The processing times of 5 jobs on machine M1 and M4 is as follows:
Job : AB C D E

Machine M1 : 11 13 19 16 17
Machine M4 : 15 18 13 19 11
Now, using the algorithm described earlier, the optimal sequence so obtained is as follows:

CAEDB

The total elapsed time corresponding to the optimal sequence is 83 hours as shown in Table 20.9, using
the individual processing times given in the original problem:

Job Machine

M1 M2 M3 M4
C 0–9 9–14 14–19 19–32
A 9–20 20–24 24–30 32–45
E 29–36 36–42 42–46 46–57 through m machines is known in advance. Such ordering may
D 36–52 52–54 54–62 62–71 not be same for both the jobs. The exact or expected
B 52–65 65–68 68–75 75–83 processing times on the given machines are known. Each
machine can perform only one job at a time. The objective is
to determine an optimal sequence of processing the jobs so as
20.6 PROCESSING TWO JOBS THROUGH m to minimize total elapsed time.
MACHINES The optimal sequence in this case can be obtained by using a
Let there be two jobs A and B, each of which is to be graph. The procedure can be illustrated by taking examples.
processed on m machines say M1, M2, . . ., Mm, in two differentTable 20.9
Minimum Total Elapsed Time
orders. The technological ordering of each of the two jobs
722 Operations Research: Theory and Applications

Example 20.9 Use the graphical method to minimize the time needed to process the following jobs on the
machines shown, i.e. for each machine find the job that should be done first. Also, calculate the total
elapsed time to complete both jobs.
Machine

RS
T
 Job 1 Sequence: A B C D E
Time (hrs) 34262
Machine

RS
T
2. Mark the processing times for jobs 1 and 2 on x-axis and
y-axis, respectively, according to the given order of machines as
shown in Fig. 20.1.

For example, machine A takes 3 hours for job 1 and 3 hours for
job 2. Construct the rectangle for machine A, as shown in Fig.
20.1. Similarly, construct other rectangles for machines B, C, D
and E.
3. Construct various blocks starting from the origin by pairing
the same machines until a point marked ‘finished’ is obtained.
4. Draw a line starting from the origin to the point marked
‘finish’ by moving horizontally, vertically and diagonally along
a line that makes an angle of 45º with the horizontal axis.
Moving horizontally along this line indicates that the first job is
under process while the second job is idle. Similarly, moving
vertically along this line indicates that the second job is under
process while the first job is idle. The diagonal movement along
Fig. 20.1 this line shows that both the jobs are simultaneously under
Graphical process.
Solution of 2-Jobs and m-Machines Sequencing Since simultaneous processing of both jobs on a machine is not
Problem possible, therefore, a diagonal movement is not allowed. In other
words, diagonal movement through rectangle areas is not
Job 2 Sequence: B C A D E
Time (hrs) 54326 allowed.
5. An optimal path is one that minimizes the idle time for both
the jobs. Thus, we must choose the path on which diagonal
[Karnataka Univ., BE, 2000; Meerut Univ., MSc (Maths), 2002] movement is maximum as shown in Fig. 20.1.
Solution The solution procedure for solving the above problem 6. Total elapsed time is obtained by adding the idle time for
can be summarized in the following steps: either job to the processing time for that job. In this example, the
1. Draw a set of axes at right angle to each other where x-axis idle time for the chosen path is found to be 5 hrs and 2 hrs for
represents the processing time of job 1 on different machines jobs 1 and 2, respectively. The total elapsed time is calculated as
while job 2 remains idle and y-axis represents processing time of follows:
job 2 while job 1 remains idle.
Sequencing Problem 723

Elapsed time, Job 1 = Processing time of job 1 + Idle time for job 1
= 17 + (2 + 3) = 22 hours
Elapsed time, Job 2 = Processing time of job 2 + Idle time for job 2
= 20 + (17 – 15) = 20 hours.
Example 20.10 Using the graphical method, calculate the minimum time needed to process jobs 1 and 2
on five machines A, B, C, D and E, i.e. for each machine find the job that should be done first. Also,
calculate the total time needed to complete both jobs.
Machines
RSTRS
T
 Job 1 Sequence : ABCDE
Time (hrs) : 6 8 4 12 4

Job 2 Sequence : BCADE

Time (hrs) : 10 8 6 4 12
[Punjab Univ., BE (E&CE), 2006]
Solution Draw two axes at right angle to each other where x-axis represents the processing time of job 1
on different machines while job 2 remains idle and y-axis represents the processing time of job 2 on
different machines while job 1 remains idle.

Fig. 20.2
Graphical
Solution of
2 Jobs and m
Machines
Sequencing
Problem

Mark the processing times for both the jobs 1 and 2 on x-axis and y-axis, respectively according to the
given order of machines, as shown in Fig. 20.2. For example, machine A takes 6 hours for job 1 as well as
for job 2. Construct the rectangle for machine A as shown in Fig. 20.2. Similarly, construct other rectangles
for machines B, C, D and E.
Draw a line starting from the origin to the point marked ‘finished’ by moving horizontally, vertically
and diagonally along a line which makes an angle of 45º with the horizontal axis. A horizontal move
represents processing of job 1 while job 2 remains idle; a vertical move represents processing of job 2 while
job 1 remains idle. The diagonal movement (i.e. a 45º line) shows that both the jobs are under process
simultaneously. Since simultaneous processing of both the jobs on a machine is not possible, therefore,
diagonal movement is not allowed.
An optimal path is one that minimizes idle time for both jobs 1 and 2. This means that this path should
coincide with 45º line to the maximum extent. Thus, we must choose the path on which diagonal movement
is maximum, as shown in Fig. 20.2. The total elapsed time is obtained by adding idle time for either job to
the processing time for that job.
The idle time for the chosen path is found to be 10 (= 4 + 6) hours for job 1 and 4 hours for job 2. The
total elapsed time is calculated as follows:
Elapsed time, Job 1 = Processing time + Idle time = 34 + (4 + 6) = 44 hours.
Elapsed time, Job 2 = Processing time + Idle time = 40 + (32 – 28) = 44 hours.
724 Operations Research: Theory and Applications

CONCEPTUAL QUESTIONS B
sequence of jobs:
v(i) Job arrival pattern
1. A job consists of N steps. Step i takes time ti. If these jobs are (ii) Number of machines
grouped somehow into station systems, then twice as many units (iii) The flow pattern in the shop
can be produced each day. Also two set-ups in parallel can (iv) The criteria of evaluating the performance of a schedule 3. By
double the production rate. Critically examine the advantages of using appropriate notion, obtain formulae for the following: ii(i)
these two approaches. Waiting time of a job (ii) Completion time of a job (iii) Mean flow time
2. What do you understand by the following terms in the context of (iv) Mean lateness
 problem

SELF PRACTICE PROBLEMS B

Machines
1. Find an optimal sequence for the following sequencing
of four jobs and five machines (when passing is not allowed) of
which processing time (in hrs) is as follows. Job 1 Sequence : ABCDE Time (hrs): 2 3 4 6 2
Job : 1234 Job 2 Sequence : CADEB Time (hrs): 4 5 3 2 6
Machine M1 :6 5 4 7 Machine M2 :4 5 3 2 Machine M3 :1 4. Two jobs are to be processed on four machines A, B, C and D.
The technological order for these jobs on machines is as follows:
3 4 2 Machine M4 :2 4 5 1 Machine M5 :8 9 7 5 Also find the
total elapsed time. Job 1 :A B C D
Job 2 :D B A C
2. Five jobs have to be processed on the same machine. The set up
time for each job depends on the job processed earlier. A table of Processing times are given in the following table
the set-up time is shown below. Find a sequence for processing Machines
all jobs that minimizes the total set-up costs. ABCD
Job 1 :4 6 7 3 Job 2 :4 7 5 8 Find the optimal sequence of jobs on
Predecessor Follower Job
each of the machines. 5. A machine shop has four machines, A, B, C
Job ABCDE
and D. Two jobs must be processed through each of these machines.
A 0 29 20 18 24 B 0 0 14 19 16 C 0 35 0 37 26 D 0 The time (in hrs) taken on each of the machines and the necessary
15 10 0 10 E 0 18 16 40 0
sequence of jobs through the shop are given below: Job 1 Sequence
:A B C D E Time (hrs): 2 4 5 1 2
3. Use the graphical method to find the minimum elapsed total time
sequence of 2 jobs and 5 machines, when we are given the
Job 2 Sequence :D E A C B Time (hrs): 6 4 2 3 6
following information:
Use the graphic method to obtain the total minimum elapsed
RSTRS time.
T

HINTS AND ANSWERS

time for job 1 is 17 + 3 = 20 hours.
4. Idle time is 4 hours for job 1 and zero hour for job 2; Elapsed
1. Optimal sequence: 1 – 3 – 2 – 4; Minimum total elapsed time =
time for job 1 is 20 + 4 = 24.
43 hours.
5. Total elapsed time is 15 hours.
3. Idle time is 3 hours for job 1 and zero hour for job 2; Elapsed

CHAPTER SUMMARY

The short-term schedules show an optimal order (sequence) and time in which jobs are processed. They also show timetables for
jobs, equipment, people, materials, facilities and all other resources that are needed to support the production plan. The schedules
should use the resources efficiently to give low costs and high utilizations. Other purpose of scheduling are, minimizing
customers waiting time, meeting promised delivery dates, keeping stock levels low, giving preferred working pattern, minimizing
waiting time of patients in a hospital for different types of tests, and so on.
Sequencing Problem 725

If there are n jobs to be performed, one at a time, on each of m machines and the actual or expected time required by the jobs
on each of the machines is also given, then the general sequencing problem is to find the sequence out of (n!)m possible sequences,
which minimize the total elapsed time between the start of the job in the first machine and the completion of the last job on the
last machine.

CHAPTER CONCEPTS QUIZ

given by
1. If there are in jobs to be performed, one at a time, on each of m (a) Min t1j = Max t2j (b) Min t1j ≤ Max t2j (c) Min t1j ≥ Max t2j (d) Min
machines, the possible sequences would be t2j ≥ Max t1j 4. You would like to assign operators to the equipment
(a) (n !)m (b) (m !)n that has (a) most jobs waiting to be processed
(c) (n)m (d) (m)n (b) job with the earliest due date
(c) job which has been waiting longest
2. Total elapsed time to process all jobs through two machines is
nn MM nn
 (d) all of the above
∑ ∑ + (b) 2 1
(a) 1 2 MI
11
jj (c) 1 1 ==
jj
11
MM
∑∑+ 5. Unforeseen factors that prevent the plans
==
from actually happen ing are
jj
( ) nj j jj
∑ + (d) none of the above (a) equipment may develop a fault
j 1 to schedules
=
(b) additional order may arrive to be added
3. The minimum processing time on machine M1 and M2
are related as

Answers to Quiz
1. (a) 2. (b) 3. (c) 4. (d) 5. (d)
(c) specifications may be changed (d) all of the above