|
|
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.
|
|
|
|