Question

Determine the optimal sequence of jobs that minimizes the total elapsed time for the data given below (processing time on machines is given in hours). Also find the total elapsed time and the idle time for three machines.

Jobs	I	II	III	IV	V	VI	VII
Machine A	3	8	7	4	9	8	7
Machine B	4	3	2	5	1	4	3
Machine C	6	7	5	11	5	6	12

Solution:

Here min A = 3, min C = 5, Max B = 5. Since Min C ≥ max B is satisfied, the problem can be converted into a two-machine problem.

Let G and H be two fictitious machines

∴ G = A + B, H = B + C

The above problem can be written as:

Jobs	I	II	III	IV	V	VI	VII
Machine G	7	11	9	9	10	12	10
Machine H	10	10	7	16	6	10	15

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

VI

II

Work table:

Jobs	Machine A		Machine B		Machine C
	In	Out	In	Out	In	Out
I	0	3	3	7	7	13
IV	3	7	7	12	13	24
`square`	7	14	14	17	24	36
VI	14	22	22	26	36	42
II	22	30	30	33	`square`	49
`square`	30	37	37	39	49	54
V	37	46	46	47	54	59

∴ Total elapsed time is = 59 hrs.

Idle time for machine A = `square` hrs

Idle time for machine B = `square` hrs

Idle time for machine C = 7 hrs.

Answer 1

Here min A = 3, min C = 5, Max B = 5. Since Min C ≥ max B is satisfied, the problem can be converted into a two-machine problem.

Let G and H be two fictitious machines

∴ G = A + B, H = B + C

The above problem can be written as:

Jobs	I	II	III	IV	V	VI	VII
Machine G	7	11	9	9	10	12	10
Machine H	10	10	7	16	6	10	15

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

I

IV

VII

VI

II

III

V

Work table:

Jobs	Machine A		Machine B		Machine C
	In	Out	In	Out	In	Out
I	0	3	3	7	7	13
IV	3	7	7	12	13	24
\[\boxed{VII}\]	7	14	14	17	24	36
VI	14	22	22	26	36	42
II	22	30	30	33	\[\boxed{42}\]	49
\[\boxed{III}\]	30	37	37	39	49	54
V	37	46	46	47	54	59

∴ Total elapsed time is = 59 hrs.

Idle time for machine A = \[\boxed{13}\] hrs

Idle time for machine B = \[\boxed{37}\] hrs

Idle time for machine C = 7 hrs.