We need to determine a sequence for the following three jobs that minimizes total completion time. The job routings and processing times are as follows J1: M1 (6 min) M3 (8 min) M4 (5 min) J2: M3 (4 min) M5 (10 min) M6 (13 min) J3: M2 (2 min) M1 (4 min) M5 (9 min). The release times for jobs 1, 2 and 3 and respectively 3, -2, and 6.

a) Formulate the problem as an integer linear program (ILP).

b) The due dates for jobs 1, 2 and 3 are 15, 20 and 22 respectively. How would the objective function change if we were interested in (a) minimizing maximum lateness or (b) minimizing average tardiness?

c) By examining problem data, identify a good/reasonable initial schedule (not necessarily optimal) for the minimum completion time criterion. Compute the corresponding completion time. Discuss how you may be able to improve on this sequence.