
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 wellstudied 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 NPhard and include setcover
as a special case. Thus we focus on approximation algorithms
and get tight, or almost tight approximation guarantees.



