Consider the 1IILmax problem.

(a) How does one find the optimal solution to this problem?

(b) Define the slack time of an unprocessed job j at any time t as (dj - pj - t) where dj is the due date, and pj is the processing time of job j. Minimum slack first (MS) rule selects, at time t, when a machine is freed, among the remaining jobs, the job with the minimum slack. Show through a counter-example that this rule is not necessarily optimal

(c) Show thatMS rule maximizes the minimum job lateness (This has to be a formal proof).