combination optimization

Mei Mei, a system administrator, would like to run five jobs J, J2, J3, JA, Js on three computing servers S, S2, S3. The time taken (in hours) by a server to complete a job is listed in the table below. A - in row Sk and column J. of the table indicates that server Se does not have the software needed to run the job J. 3 Kividuals S 31 S2 2 1 3 2 Sg 2 4 The servers are currently idle, and can start running any jobs assigned to them without delay. A server can run only one job at a time. The jobs given to a server can be run in any order, and a server can start a new job as soon as it completes a job it is running. Mei Mei would like to determine the earliest time within which all the jobs can be completed by the three servers. That is, she would like to determine to which server each job should be given, so that the jobs are completed within the least amount of time. (To understand the notion of completion time, suppose that with a different set of jobs, server S takes a total of 7 hours, server S, takes 12 hours, and S, takes 10 hours. Then all the jobs are completed within 12 hours.) (a) Rephrase Mei Mei's goal in the language of graphs. (i) For the graph you construct, describe what the vertices and edges denote, as also any other associated parameters that you need. (ii) Describe the function that Mei Mei would like to optimize in terms of the graph. (iii) Draw the graph (b) Formulate Mei Mei's optimization problem as an IP. Mei Mei, a system administrator, would like to run five jobs J, J2, J3, JA, Js on three computing servers S, S2, S3. The time taken (in hours) by a server to complete a job is listed in the table below. A - in row Sk and column J. of the table indicates that server Se does not have the software needed to run the job J. 3 Kividuals S 31 S2 2 1 3 2 Sg 2 4 The servers are currently idle, and can start running any jobs assigned to them without delay. A server can run only one job at a time. The jobs given to a server can be run in any order, and a server can start a new job as soon as it completes a job it is running. Mei Mei would like to determine the earliest time within which all the jobs can be completed by the three servers. That is, she would like to determine to which server each job should be given, so that the jobs are completed within the least amount of time. (To understand the notion of completion time, suppose that with a different set of jobs, server S takes a total of 7 hours, server S, takes 12 hours, and S, takes 10 hours. Then all the jobs are completed within 12 hours.) (a) Rephrase Mei Mei's goal in the language of graphs. (i) For the graph you construct, describe what the vertices and edges denote, as also any other associated parameters that you need. (ii) Describe the function that Mei Mei would like to optimize in terms of the graph. (iii) Draw the graph (b) Formulate Mei Mei's optimization problem as an IP