In an unrelated m-machine parallel scheduling problem, set M is a set of machines and set N is a set of jobs. |M| = m and |N| = n. For each job j N and each machine i M, there is a processing time, pij which is the amount of time that job j must execute if it is assigned to machine i. Each job is a single operation (i.e., no precedence constraints) and each job can execute on any machine. The goal is to schedule jobs on machines to minimize the makespan. For this problem, we have the following additional restrictions: Let S be a set of sets of jobs. Each element, s S, is a set of jobs, s N, that are all required to execute on the same resource. The jobs in s can still execute on any resource but they all must be assigned to the same one. Let D be a set of sets of jobs. Each element, d D, is a set of jobs, d N, that cannot all execute on the same resource. At least one element of d must be on a different resource from the rest of the elements in d. They could all be on different resources but cannot all be on the same one.

(a) Prove that if, in addition to the problem data, you are only given the assignment of jobs to machines, you could easily calculate the makespan of the corresponding schedule. Write a closed-form expression for the makespan given the above information. Define all your notation. [5]

(b) Using the hint from part (a), create a complete MILP model for the problem with the only decision variables being Cmax representing the makespan and xij = {0, 1} which is assigned 1 if and only if job j is assigned to resource i. [10]