Discrete Mathematics and Optimization Seminar
Friday, Mar. 26th, 2010
2:00 PM, McConnell 320
Unrelated Machine Selection and Scheduling
Lisa Fleischer
Darmouth University
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.