Consider the following scheduling problem of parallel machines: A set {J1,,Jn} of n jobs need to be scheduled onto m(m>1) parallel machines M1,,Mm. The time requirements for processing these jobs are, respectively, p1,,pn>0. Each of these n jobs needs to be processed without interruption on one (and only one) of these m machines. Unless specified otherwise, all machines are continuously available from time 0 . The objective is to assign all the jobs to the machines so as to minimize the makespan, i.e., the time point at which all jobs are finished. Question 1 [40\%] Suppose that all m machines are identical. (a) Formulate the problem as a binary integer linear program (ILP). Provide all the details of your formulation, including clear definition of your variables, explanations of the objective function and of each constraint. 3/4 (b) Let m=10 and the processing requirements of n=100 jobs be given in the attached Excel file, "Scheduling_Instance.xlsx". Solve the LP relaxation of your binary ILP formulated in part (a) and present your optimal LP solution. Based on the optimal LP solution, suggest at least five feasible solutions to the original ILP. Explain the reasons behind your suggestion. What are your suggested five feasible job assignments? What are the corresponding makespans of the five schedules? (It is recommended to present your answers to the last two questions in a tabular form.)