Mei Mei, a system administrator, would like to run five jobs J1, J2, J3, J4, J5...

 

Transcribed Image Text:

Mei Mei, a system administrator, would like to run five jobs J1, J2, J3, J4, J5 on three computing servers S1, S2, S3. The time taken (in hours) by a server to complete a job is listed in the table below. Ain row Sk and column Je of the table indicates that server Sk does not have the software needed to run the job J. J1 J2 J3 J4 J5 - 2 3 1 3 12 - 24 3 1 555 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 S2 takes 12 hours, and S3 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 J1, J2, J3, J4, J5 on three computing servers S1, S2, S3. The time taken (in hours) by a server to complete a job is listed in the table below. Ain row Sk and column Je of the table indicates that server Sk does not have the software needed to run the job J. J1 J2 J3 J4 J5 - 2 3 1 3 12 - 24 3 1 555 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 S2 takes 12 hours, and S3 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.