LP rounding and an almost harmonic algorithm for scheduling with resource dependent processing times

Alexander Grigoriev; Maxim Sviridenko; Marc Uetz

doi:10.1007/11830924_15

LP rounding and an almost harmonic algorithm for scheduling with resource dependent processing times

Alexander Grigoriev, Maxim Sviridenko, Marc Uetz

Discrete Mathematics and Mathematical Programming

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

7 Citations (Scopus)

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	https://doi.org/10.1007/11830924_15
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

Access to Document

10.1007/11830924_15

Cite this

Grigoriev, A., Sviridenko, M., & Uetz, M. (2006). LP rounding and an almost harmonic algorithm for scheduling with resource dependent processing times. In J. Díaz, K. Jansen, J. D. P. Rolim, & U. Zwick (Eds.), Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques: 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 (pp. 140-151). (Lecture Notes in Computer Science; Vol. 4110). Springer. https://doi.org/10.1007/11830924_15

Grigoriev, Alexander ; Sviridenko, Maxim ; Uetz, Marc. / LP rounding and an almost harmonic algorithm for scheduling with resource dependent processing times. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques: 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. editor / Josep Díaz ; Klaus Jansen ; José D.P. Rolim ; Uri Zwick. Springer, 2006. pp. 140-151 (Lecture Notes in Computer Science).

@inproceedings{2643e81e112149b399061cbf0c760c57,

title = "LP rounding and an almost harmonic algorithm for scheduling with resource dependent processing times",

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

author = "Alexander Grigoriev and Maxim Sviridenko and Marc Uetz",

year = "2006",

doi = "10.1007/11830924_15",

language = "English",

isbn = "978-3-540-38044-3",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "140--151",

editor = "Josep D{\'i}az and Klaus Jansen and Rolim, {Jos{\'e} D.P.} and Uri Zwick",

booktitle = "Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques",

address = "Netherlands",

note = "9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006, APPROX ; Conference date: 28-08-2006 Through 30-08-2006",

}

Grigoriev, A, Sviridenko, M & Uetz, M 2006, LP rounding and an almost harmonic algorithm for scheduling with resource dependent processing times. in J Díaz, K Jansen, JDP Rolim & U Zwick (eds), Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques: 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. Lecture Notes in Computer Science, vol. 4110, Springer, pp. 140-151, 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006, Barcelona, Spain, 28/08/06. https://doi.org/10.1007/11830924_15

LP rounding and an almost harmonic algorithm for scheduling with resource dependent processing times. / Grigoriev, Alexander; Sviridenko, Maxim; Uetz, Marc.

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques: 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. ed. / Josep Díaz; Klaus Jansen; José D.P. Rolim; Uri Zwick. Springer, 2006. p. 140-151 (Lecture Notes in Computer Science; Vol. 4110).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - LP rounding and an almost harmonic algorithm for scheduling with resource dependent processing times

AU - Grigoriev, Alexander

AU - Sviridenko, Maxim

AU - Uetz, Marc

N1 - Conference code: 9

PY - 2006

Y1 - 2006

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

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

U2 - 10.1007/11830924_15

DO - 10.1007/11830924_15

M3 - Conference contribution

SN - 978-3-540-38044-3

T3 - Lecture Notes in Computer Science

SP - 140

EP - 151

BT - Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

A2 - Díaz, Josep

A2 - Jansen, Klaus

A2 - Rolim, José D.P.

A2 - Zwick, Uri

PB - Springer

T2 - 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006

Y2 - 28 August 2006 through 30 August 2006

ER -

Grigoriev A, Sviridenko M, Uetz M. LP rounding and an almost harmonic algorithm for scheduling with resource dependent processing times. In Díaz J, Jansen K, Rolim JDP, Zwick U, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques: 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. Springer. 2006. p. 140-151. (Lecture Notes in Computer Science). https://doi.org/10.1007/11830924_15

LP rounding and an almost harmonic algorithm for scheduling with resource dependent processing times

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this