Abstract
We consider a scheduling problem on unrelated parallel machines with the objective to minimize the makespan. In addition to its machine dependence, the processing time of any job is dependent on the usage of a scarce renewable resource, e.g. workers. A given amount of that resource can be distributed over the jobs in process at any time. The more of the resource is allocated to a job, the smaller is its processing time. This model generalizes the classical unrelated parallel machine scheduling problem by adding a time-resource tradeoff. It is also a natural variant of a generalized assignment problem studied by Shmoys and Tardos. On the basis of an integer linear programming formulation for (a relaxation of) the problem, we adopt a randomized LP rounding technique from Kumar et al. (FOCS 2005) in order to obtain a deterministic, integral LP solution that is close to optimum. We show how this rounding procedure can be used to derive a deterministic 3.75-approximation algorithm for the scheduling problem. This improves upon previous results, namely a deterministic 6.83-approximation, and a randomized 4-approximation. The improvement is due to the better LP rounding and a new scheduling algorithm that can be viewed as a restricted version of the harmonic algorithm for bin packing.
Original language | English |
---|---|
Title of host publication | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques |
Subtitle of host publication | 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006, Barcelona, Spain, August 28-30 2006. Proceedings |
Editors | Josep Díaz, Klaus Jansen, José D.P. Rolim, Uri Zwick |
Publisher | Springer |
Pages | 140-151 |
Number of pages | 12 |
ISBN (Electronic) | 978-3-540-38045-0 |
ISBN (Print) | 978-3-540-38044-3 |
DOIs | |
Publication status | Published - 2006 |
Event | 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 - Barcelona, Spain Duration: 28 Aug 2006 → 30 Aug 2006 Conference number: 9 |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
Publisher | Springer |
Volume | 4110 |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference
Conference | 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 |
---|---|
Abbreviated title | APPROX |
Country | Spain |
City | Barcelona |
Period | 28/08/06 → 30/08/06 |