Module 7. Sequencing problem

Lesson 15

SOLUTION OF A SEQUENCING PROBLEM

15.1  Introduction

When a number of jobs are given to be done and they require processing on two or more machines, the main concern of a manager is to find the order or sequence to perform these jobs. We shall consider the sequencing problems in respect of the jobs to be performed in a factory and study the method of their solution. Such sequencing problems can be broadly divided in two groups. In the first one, there are n jobs to be done, each of which requires processing on some or all of the k different machines. We can determine the effectiveness of each of the sequences that the technologically feasible (that is to say, those satisfying the restrictions on the order in which each job must be processed through the machines) and choose a sequence which optimizes the effectiveness. To illustrate, the timings of processing of each of the n jobs on each of the k machines, in a certain given order, may be given and the time for performing the jobs may be the measure of effectiveness. We shall select the sequences for which the total time taken in processing all the jobs on the machines would be the minimum.

In this unit we will look into solution of a sequencing problem. In this lesson the solutions of following cases will be discussed:

a) n jobs and two machines A and B, all jobs processed in the order AB.

b) n jobs and three machines A, B and C all jobs processed in the order ABC

c) Problems with n jobs and m machines.

15.1.1  Processing of n jobs through two machines

The simplest possible sequencing problem is that of n job two machine sequencing problem in which we want to determine the sequence in which n-job should be processed through two machines so as to minimize the total elapsed time T. The problem can be described as:

a) Only two machines A and B are involved;

b) Each job is processed in the order AB.

c) The exact or expected processing times A₁,A₂,A₃, --- , A_n ; B₁,B₂,B₃, --- , B_n are known and are provided in the following table

Machine	Job(s)
	1	2	3	--	-	i	- -	-	n
A	A1	A2	A3	--	-	Ai	--	-	An
B	B1	B2	B3	--	-	Bi	--	-	Bn

The problem is to find the sequence (or order) of jobs so as to minimize the total elapsed time T. The solution of the above problem is also known as Johnson’s procedure which involves the following steps:

Step 1. Select the smallest processing time occurring in the list A₁,A₂,A₃, --- , A_n ; B₁,B₂,B₃, --- , B_n if there is a tie, either of the smallest processing times can be selected.

Step 2. If the least processing time is A_r , select the r^th job first_. If it is B_s, do the s^th  job last  as the given order is AB

Step 3. There are now (n-1) jobs left to be ordered. Repeat steps I and II for the remaining set of processing times obtained by deleting the processing time for both the machines corresponding to the job already assigned.

Step 4. Continue in the same manner till the entire jobs have been ordered. The resulting ordering will minimize the total elapsed time T and is called the optimal sequence.

Step 5. After finding the optimal sequence as stated above find the total elapsed time and idle times on machines A and B as under:

Total elapsed time =	The time between starting the first job in the optimal sequence on machine A and completing the last job in the optimal machine B.
Idle time on machine A =	(Time when the last job in the optimal sequence on sequences is completed on machine B)- (Time when the last job in the optimal sequences is completed on machine A)
Idle time on machine B =	(Time when the first job in the optimal sequences is completed on machine A)+

The Johnson’s procedure can be illustrated by following examples:

Example 1

There are nine jobs, each of which must go through two machines P and Q in the order PQ, the processing times (in hours) are given below:

Machine	Job(s)
	A	B	C	D	E	F	G	H	I
P	2	5	4	9	6	8	7	5	4
Q	6	8	7	4	3	9	3	8	11

Find the sequence that minimizes the total elapsed time T. Also calculate the total idle time for the machines in this period.

Solution

The minimum processing time on two machines is 2 which correspond to task A on machine P. This shows that task A will be preceding first. After assigning task A, we are left with 8 tasks on two machines

Machine	B	C	D	E	F	G	H	I
P	5	4	9	6	8	7	5	4
Q	8	7	4	3	9	3	8	11

Minimum processing time in this reduced problem is 3 which correspond to jobs E and G (both on machine Q). Now since the corresponding processing time of task E on machine P is less than the corresponding processing time of task G on machine Q therefore task E will be processed in the last and task G next to last. The situation will be dealt as

A

G

E

The problem now reduces to following 6 tasks on two machines with processing time as follows:

Machine	B	C	D	F	H	I
P	5	4	9	8	5	4
Q	8	7	4	9	8	11

Here since the minimum processing time is 4 which occurs for tasks C and I on machine P and task D on machine Q. Therefore, the task C which has less processing time on P will be processed first and then task I and  task D will be placed at the last i.e., 7^th sequence cell.

The sequence will appear as follows:

A

C

I

D

E

G

The problem now reduces to the following 3 tasks on two machines

Machine	B	F	H
P	5	8	5
Q	8	9	8

In this reduced table the minimum processing time is 5 which occurs for tasks B and H both on machine P. Now since the corresponding time of tasks B and H on machine Q are same i.e. 8. Tasks B or H may be placed arbitrarily in the 4^th and 5^th sequence cells. The remaining task F can then be placed in the 6^th sequence cell. Thus the optimal sequences are represented as 

A

I

C

B

H

F

D

E

G

or

A

1

C

H

B

F

D

E

G

Further, it is also possible to calculate the minimum elapsed time corresponding to the optimal sequencing A → I → C → B → H → F → D → E → G.

Job Sequence	Machine A		Machine B
	Time In	Time Out	Time In	Time Out
A	0	2	2	8
I	2	6	8	19
C	6	10	19	26
B	10	15	26	34
H	15	20	34	42
F	20	28	42	51
D	28	37	51	55
E	37	43	55	58
G	43	50	58	61

Hence the total elapsed time for this proposed sequence  staring from job A to completion of job G is 61 hours .During this time machine P remains idle for 11 hours (from 50 hours to 61 hours)and the machine Q remains idle for 2 hours only (from 0 hour to 2 hour ).

15.2 Processing of n Jobs through Three Machines

The type of sequencing problem can be described as follows:

a) Only three machines A, B and C are involved;

b) Each job is processed in the prescribed order ABC

c) No passing of jobs is permitted i.e. the same order over each machine is maintained.

d) The exact or expected processing times A₁,A₂,A₃, --- , A_n ; B₁,B₂,B₃, --- , B_n and C₁,C₂,C₃, --- , C_n are known and are denoted by the following table

Machine	Job(s)
	1	2	3	--	-	i	- -	-	n
A	A1	A2	A3	--	-	Ai	--	-	An
B	B1	B2	B3	--	-	Bi	--	-	Bn
C	C1	C2	C3			Ci			Cn

Our objective will be to find the optimal sequence of jobs which minimizes the total elapsed time. No general procedure is available so far for obtaining an optimal sequence in such case. However, the Johnson’s procedure can be extended to cover the special cases where either one or both of the following conditions hold:

a) The minimum processing time on machine A ≥ the maximum processing time on machine B.

b) The minimum processing time on machine C ≥ the maximum processing time on machine B.

The method is to replace the problem by an equivalent problem involving n jobs and two machines. These two fictitious machines are denoted by G and H and the corresponding time G_i and H_i are defined by

G_i = A_i + B_i and B_i + C_i

Now this problem with prescribed ordering GH is solved by the method with n jobs through two machines, the resulting sequence will also be optimal for the original problem. The above methodology is illustrated by following example:

Example 2

There are five jobs (namely 1,2,3,4 and 5), each of which must go through machines A, B and C in the order ABC.  Processing Time (in hours) are given below:

Jobs	1	2	3	4	5
Machine A	5	7	6	9	5
Machine B	2	1	4	5	3
Machine C	3	7	5	6	7

Find the sequence that minimum the total elapsed time required to complete the jobs.

Solution

Here Min A_i = 5; B_i = 5 and C_i =3 since the condition of Min. A_i ≥ Max. B_i is satisfied the given problem can be converted into five jobs and two machines problem.

Jobs
1	7	5
2	8	8
3	10	9
4	14	11
5	8	10

The Optimal Sequence will be

2

5

4

3

1

Total elapsed Time will be

Jobs	Machine A		Machine B		Machine C
	In	Out	In	Out	In	Out
2	0	7	7	8	8	15
5	7	12	12	15	15	22
4	12	21	21	26	26	32
3	21	27	27	31	32	37
1	27	32	32	34	37	40

Min. total elapsed time is 40 hours.

Idle time for Machine A  is 8 hrs. (32-40)

Idle time for Machine B is 25 hours (0-7, 8-12, 15-21, 26-27, 31-32 and 34-40)

Idle time for Machine C is 12 hours (0-8, 22-26.)

15.3 Problems with n Jobs and m Machines

Let there be n jobs, each of which is to be processed through m machines, say M₁,M₂, --- , M_m in the order M₁,M₂,M₃, --- , M_m. Let T _ij be the time taken by the i^th machine to complete the j^th job.

The iterative procedure of obtaining an optimal sequence is as follows:

Step I: Find (i) min_j (T_1j) ii) min_j (T_mj)  iii) max_j (T_2j,T_3j,T_4j, --- , T_(m-1)j) for j=1,2,---, n

Step II: Check whether   

a. min_j(T_1j) ≥ max_j (T_ij) for i=2,3,----,m-1

                                    Or 

b. min_j(T_mj) ≥ max_j (T_ij) for i=2,3,---,m-1

Step III: If the inequalities in Step II are not satisfied, method fails, otherwise, go to next step.

Step IV: Convert the m machine problem into two machine problem by introducing two fictitious machines G and H, such that

T_Gj = T_1j + T_2j + --- +T_(m-1)j and T_Hj = T_2j + T_3j + --- +T_mj

Determine the optimal sequence of n jobs through 2 machines by using optimal sequence algorithm.

Step V: In addition to condition given in Step IV, if T_ij = T_2j + T_3j + --- +T_mj = C is a fixed positive constant for all i = 1, 2, 3, … , n then determine the optimal sequence of n jobs and two machines M₁ and M_m in the order M₁M_m by using the optimal sequence algorithm.

Example 3

Find an optimal sequence for the following sequencing problem of four jobs and five machines when passing is not allowed, of which processing time (in hours) is given below:

Job	Machine
	A	B	C	D	E
1	7	5	2	3	9
2	6	6	4	5	10
3	5	4	5	6	8
4	8	3	3	2	6

Also find the total elapsed time.

Solution

Here Min. A_i = 5, Min. E_i = 6

Max. (B_i, C_i, D_i) = 6, 5, 6 respectively

Since Min. E_i = Max. (B_i, D_i) and Min. A_i = Max. C_i satisfied therefore the problem can be converted into 4 jobs and 2 fictitious machines G and H as follows:

Job	Fictitious Machine
1	17	19
2	21	25
3	20	23
4	16	14

The above sequence will be:

1

3

2

4

Total Elapsed Time Corresponding to Optimal Sequence can be obtained as follows:

	Machine A		Machine B		Machine C		Machine D		Machine E
Job	In	Out	In	Out	In	Out	In	Out	In	Out
1	0	7	7	12	12	14	14	17	17	26
3	7	12	12	16	16	21	21	27	27	35
2	12	18	18	24	24	28	28	33	35	45
4	18	26	26	29	29	32	33	35	45	51

Thus the minimum elapsed time is 51 hours.

Idle time for machine A =	25 hours(26-51)
Idle time for machine B =	33 hours(0-7,16-18,24-26,29-51)
Idle time for machine C =	37 hours(0-12,14-16,21-24,28-29,32-51)
Idle time for machine D =	35 hours (0-14,17-21,27-28,35-51)
Idle time for machine E =	18 hours (0-17,26-27)