Approximation algorithms for scheduling unrelated parallel machines

J.K. Lenstra; D.B. Shmoys; É. Tardos

doi:10.1007/978-3-642-73778-7_165

Approximation algorithms for scheduling unrelated parallel machines

J.K. Lenstra
, D.B. Shmoys
, É. Tardos

Combinatorial Optimization

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

Abstract

We consider the following problem. There are m parallel machines and n independent jobs. Each job is to be assigned to one of the machines. The processing of job j on machine i requires time P ij . The objective is to find a schedule that minimizes the makespan.

Original language	English
Title of host publication	Operations Research Proceedings 1987 (Papers of the 16th Annual Meeting of DGOR, in cooperation with NSOR, Veldhoven, The Netherlands, September 23-25, 1987)
Editors	H. Schellhaas, P. Beek, van, H. Isermann, R. Schmidt, M. Zijlstra
Place of Publication	Berlin
Publisher	Springer
Pages	623
ISBN (Print)	3-540-19365-0
DOIs	https://doi.org/10.1007/978-3-642-73778-7_165
Publication status	Published - 1988

Access to Document

10.1007/978-3-642-73778-7_165

Cite this

Lenstra, J. K., Shmoys, D. B., & Tardos, É. (1988). Approximation algorithms for scheduling unrelated parallel machines. In H. Schellhaas, P. Beek, van, H. Isermann, R. Schmidt, & M. Zijlstra (Eds.), Operations Research Proceedings 1987 (Papers of the 16th Annual Meeting of DGOR, in cooperation with NSOR, Veldhoven, The Netherlands, September 23-25, 1987) (pp. 623). Springer. https://doi.org/10.1007/978-3-642-73778-7_165

Lenstra, J.K. ; Shmoys, D.B. ; Tardos, É. / Approximation algorithms for scheduling unrelated parallel machines. Operations Research Proceedings 1987 (Papers of the 16th Annual Meeting of DGOR, in cooperation with NSOR, Veldhoven, The Netherlands, September 23-25, 1987). editor / H. Schellhaas ; P. Beek, van ; H. Isermann ; R. Schmidt ; M. Zijlstra. Berlin : Springer, 1988. pp. 623

@inproceedings{539a0ad30744457f82221721deae08cd,

title = "Approximation algorithms for scheduling unrelated parallel machines",

abstract = "We consider the following problem. There are m parallel machines and n independent jobs. Each job is to be assigned to one of the machines. The processing of job j on machine i requires time P ij . The objective is to find a schedule that minimizes the makespan.",

author = "J.K. Lenstra and D.B. Shmoys and {\'E}. Tardos",

year = "1988",

doi = "10.1007/978-3-642-73778-7\_165",

language = "English",

isbn = "3-540-19365-0",

pages = "623",

editor = "H. Schellhaas and \{Beek, van\}, P. and H. Isermann and R. Schmidt and M. Zijlstra",

booktitle = "Operations Research Proceedings 1987 (Papers of the 16th Annual Meeting of DGOR, in cooperation with NSOR, Veldhoven, The Netherlands, September 23-25, 1987)",

publisher = "Springer",

address = "Germany",

}

Lenstra, JK, Shmoys, DB & Tardos, É 1988, Approximation algorithms for scheduling unrelated parallel machines. in H Schellhaas, P Beek, van, H Isermann, R Schmidt & M Zijlstra (eds), Operations Research Proceedings 1987 (Papers of the 16th Annual Meeting of DGOR, in cooperation with NSOR, Veldhoven, The Netherlands, September 23-25, 1987). Springer, Berlin, pp. 623. https://doi.org/10.1007/978-3-642-73778-7_165

Approximation algorithms for scheduling unrelated parallel machines. / Lenstra, J.K.; Shmoys, D.B.; Tardos, É.
Operations Research Proceedings 1987 (Papers of the 16th Annual Meeting of DGOR, in cooperation with NSOR, Veldhoven, The Netherlands, September 23-25, 1987). ed. / H. Schellhaas; P. Beek, van; H. Isermann; R. Schmidt; M. Zijlstra. Berlin: Springer, 1988. p. 623.

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

TY - GEN

T1 - Approximation algorithms for scheduling unrelated parallel machines

AU - Lenstra, J.K.

AU - Shmoys, D.B.

AU - Tardos, É.

PY - 1988

Y1 - 1988

N2 - We consider the following problem. There are m parallel machines and n independent jobs. Each job is to be assigned to one of the machines. The processing of job j on machine i requires time P ij . The objective is to find a schedule that minimizes the makespan.

AB - We consider the following problem. There are m parallel machines and n independent jobs. Each job is to be assigned to one of the machines. The processing of job j on machine i requires time P ij . The objective is to find a schedule that minimizes the makespan.

U2 - 10.1007/978-3-642-73778-7_165

DO - 10.1007/978-3-642-73778-7_165

M3 - Conference contribution

SN - 3-540-19365-0

SP - 623

BT - Operations Research Proceedings 1987 (Papers of the 16th Annual Meeting of DGOR, in cooperation with NSOR, Veldhoven, The Netherlands, September 23-25, 1987)

A2 - Schellhaas, H.

A2 - Beek, van, P.

A2 - Isermann, H.

A2 - Schmidt, R.

A2 - Zijlstra, M.

PB - Springer

CY - Berlin

ER -

Lenstra JK, Shmoys DB, Tardos É. Approximation algorithms for scheduling unrelated parallel machines. In Schellhaas H, Beek, van P, Isermann H, Schmidt R, Zijlstra M, editors, Operations Research Proceedings 1987 (Papers of the 16th Annual Meeting of DGOR, in cooperation with NSOR, Veldhoven, The Netherlands, September 23-25, 1987). Berlin: Springer. 1988. p. 623 doi: 10.1007/978-3-642-73778-7_165

Approximation algorithms for scheduling unrelated parallel machines

Abstract

Access to Document

Fingerprint

Cite this