Assignment:
A machine scheduling problem has ten jobs with given processing times of 3, 1, 4, 1, 5, 9, 2, 6, 5, and 3 h, respectively.
(a) Assume that the jobs are to be performed on a single machine and that the objective is to minimize mean flow time, find an optimal schedule and draw the corresponding Gantt chart.
(b) Assume that due dates for the ten jobs are given as 14, 4, 10, 19, 40, 32, 13, 31, 7, and 26 h, respectively. Use the earliest due date algorithm to find a schedule that minimizes the maximal lateness Lmax. Show the corresponding Gantt chart. What is the minimal value of Lmax, and for which job does it occur? Which jobs are late?
(c) Assume that there are two parallel machines to process the jobs. Trying to minimize the schedule length, schedule the jobs using the LPT algorithm. Display the corresponding Gantt chart. What is the performance ratio?
(d) Given two parallel machines as under (c), what is the schedule that minimizes the mean flow time? Display the corresponding Gantt chart.
(e) Reconsider questions (c) and (d) given that there are now three rather than two parallel machines.
Provide complete and step by step solution for the question and show calculations and use formulas.