Question

Find the sequence that minimizes the total elapsed time required to complete the following task. The table below gives the processing time in hours. Also, find the minimum elapsed time and idle times for both machines.

Jobs	1	2	3	4	5
M1	3	7	4	5	7
M2	6	2	7	3	4

Answer 1

Using optimal sequence algorithm, the following optimal sequence can be obtained.

Jobs	1	2	3	4	5
M1	3	7	4	5	7
M2	6	2	7	3	4

Here, min{ M₁, M₂ } = 2
Which corresponds to Job 2 of Machine 2.
∴ Job 2 is processed last

2

Now, the remaining Jobs are 1, 3, 4, and 5 
Here, Min{ M₁, M₂ } = 3 
Which corresponds to Job 1 of Machine 1 and Job 4 of machine 2.
∴ Job 1 is processed first and Job 4 is processed fourth before Job 2. i.e;

1

4

2

Again, the remaining Jobs are 3 and 4
Here, Min {M₁, M₂ } = 4 
Which corresponds to Job 3 of machine 1 and Job 5 of machine 2.
∴ Job 3 is processed second after Job 1 and Job 5 is processed third before Job 4
i.e. 

1

3

5

4

2

This is the optimal sequence for completing a table.
Now we find the total elapsed times as follows:

Jobs	Machine M1		Machine M2		Idle time for M2
	Time in	Time out	Time in	Time out
1	0	3	3	9	3
3	3	7	9	16	0
5	7	14	16	20	0
4	14	19	20	23	0
2	19	25	26	28	3

Total elaspsed time = 28 Hrs.
Idle time for M₁ = 2 Hrs.
Idle time for M₂ =6 Hrs.