Unrelated Machine Selection and Scheduling

ACO Seminar
Thursday, March 11, 2010 - 16:30
1 hour (actually 50 minutes)
Skiles 255
Professor, Dartmouth College
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.