Question

4 machines and 9 jobs

Jobj	1	2	3	4	5	6	7	8	9
Pj	4	9	3	3	6	8	8	12	6

Determine a schedule that minimizes the makespan of the following jobs on 3 machines.

a) Compute C_max(LPT)

b) Pair the jobs 1-5, 2-6, 4-5, 7-8-9

• What is C_max?

• Is this C_max(OPT)? Why?

c) What is C_max(LPT)/C_max(OPT) ?

Answer 1

Answer: (a) Cmax(LPT) = 21

(b) Cmax = 26, Cmax OPT = 20

(C) Cmax LPT/Cmax OPT = 21/20

Explanation:

a). When computing Cmax LPT, Assign the jobs with Longest Processing Time to the machines first. This is how the assignment looks like in this case

8 Start Time Sj 0 0 м3 LPT Machine (M) Job assigned M1 M2 2 6 M3 7 M2 M1 M2 M3 3 M1 4 Process Time pij Completion Time (CJ) 12 12 9 9 8 8 8 16 6 15 6 18 4 19 3 19 3 21 0 8 9 12 15 16 18 9 1

The Cmax would be the Max of the processing time that any Machine is taking, which is

Cmax Process Time 6 3 M1 M2 МЗ 21 Job 8 Job 2 Job 6 Job 9 Job 5 Job 7 Job 4 Job 1 Job 3 Total 21 19 12 9 6 4 3 8 8 19

21

(b) As per given information assignment of jobs:

Process Time Cmax 26 4 0 0 M1 M2 МЗ Job 1 Job 2 Job 5 Job 7 Job 5 Job 6 Job 4 9 8 3 12 0 0 6 0 0 6 8 Total 10 17 9 26 M4 Job 8 Job 9 0

Cmax is coming out to be 26

Is this Cmax OPT? Let's compute that to comment on this.

OPT 59 Total Process Time Total Machines 3 Load Per Machine 19.66666667 20

Total Processing time is the sum of process times of all jobs.

Load per machine = Total Process Time / Total Machines = 20 ( Rounded up)

Assigning jobs keeping in mind the load per machine

Process Time Cmax 20 0 M1 M2 МЗ Job 8 Job 2 Job 5 Job 6 Job 7 Job 9 12 9 6 Total 20 20 19 ON 0000 Job 3 Job 1 3 0 Job 4 4 3

Cmax OPT = 20

Which is the optimal assignment of jobs, and it is line with loads per machine.

(c). Ratio Cmax LPT/Cmax OPT = 21/20