Abstract
We consider unrelated parallel machine scheduling problems with the objective to minimize the schedule makespan. In addition to its machine-dependence, the processing time of any job is also dependent on the usage of a scarce renewable resource. An amount of k units of that resource, e.g. workers, can be distributed over the jobs in process, and the more of that resource is allocated to a job, the smaller its processing time. The model generalizes the classical unrelated machine scheduling problem, adding a resource-time tradeoff. It is also a natural variant of a generalized assignment problem studied previously by Shmoys and Tardos, the difference lying in the fact the resource is renewable and not a total budget constraint. We use a two-phased LP rounding technique to assign resources to jobs and jobs to machines. Combined with Graham's list scheduling, we thus prove the existence of a (4+2√2)-approximation algorithm. We show how our approach can be adapted to scheduling problems with dedicated machines as well, with an improvement of the performance bound to (3+2√2). Moreover, we derive a lower bound of 2 for the employed LP-based analysis, and we prove a (3/2)-inapproximability result.
Original language | English |
---|---|
Title of host publication | Integer Programming and Combinatorial Optimization |
Editors | Michael Jünger, Volker Kaibel |
Place of Publication | Berlin, Heidelberg |
Publisher | Springer |
Pages | 182-195 |
Number of pages | 14 |
ISBN (Electronic) | 978-3-540-32102-6 |
ISBN (Print) | 978-3-540-26199-5 |
DOIs | |
Publication status | Published - May 2006 |
Event | 11th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2005 - Berlin, Germany Duration: 8 Jun 2005 → 10 Jun 2005 Conference number: 11 |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
Publisher | Springer |
Volume | 3509 |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference
Conference | 11th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2005 |
---|---|
Abbreviated title | IPCO |
Country | Germany |
City | Berlin |
Period | 8/06/05 → 10/06/05 |
Keywords
- Schedule problem
- Integer linear programming
- Feasible schedule
- Idle period
- Fractional solution