Unrelated Machine Selection and Scheduling

ACO Seminar
Thursday, March 11, 2010 - 4:30pm for 1 hour (actually 50 minutes)
Skiles 255
Lisa Fleischer – Professor, Dartmouth College
Prasad Tetali
We look at problems of scheduling jobs to machines when the processing time of a job is machine dependent. Common objectives in this framework are to minimize the maximum load on a machine, or to minimize the average completion time of jobs. These are well-studied problems. We consider the related problem of trying to select a subset of machines to use to minimize machine costs subject to bounds on the maximum load or average completion time of the corresponding schedule. These problems are NP-hard and include set-cover as a special case. Thus we focus on approximation algorithms and get tight, or almost tight approximation guarantees. A key part of our results depends on showing the submodularity of the objective of a related optimization problem.