Fixed-Order Scheduling on Parallel Machines

Thomas Bosman; Dario Frascaria; Neil Olver; Rene Sitters; Leen Stougie

doi:10.1007/978-3-030-17953-3_7

Fixed-Order Scheduling on Parallel Machines

Thomas Bosman^*
, Dario Frascaria
, Neil Olver
, Rene Sitters
, Leen Stougie

^*Corresponding author for this work

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

171 Downloads (Pure)

Abstract

We consider the following natural scheduling problem: Given a sequence of jobs with weights and processing times, one needs to assign each job to one of m identical machines in order to minimize the sum of weighted completion times. The twist is that for machine the jobs assigned to it must obey the order of the input sequence, as is the case in multi-server queuing systems. We establish a constant factor approximation algorithm for this (strongly NP-hard) problem. Our approach is necessarily very different from what has been used for similar scheduling problems without the fixed-order assumption. We also give a QPTAS for the special case of unit processing times.

Original language	English
Title of host publication	Integer Programming and Combinatorial Optimization
Subtitle of host publication	20th International Conference, IPCO 2019, Ann Arbor, MI, USA, May 22-24, 2019, Proceedings
Editors	Viswanath Nagarajan, Andrea Lodi
Publisher	Springer Verlag
Pages	88-100
Number of pages	13
ISBN (Electronic)	9783030179533
ISBN (Print)	9783030179526
DOIs	https://doi.org/10.1007/978-3-030-17953-3_7
Publication status	Published - 2019
Event	20th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2019 - Ann Arbor, United States Duration: 22 May 2019 → 24 May 2019

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	11480
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	20th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2019
Country/Territory	United States
City	Ann Arbor
Period	22/05/19 → 24/05/19

Funding

This work was partially supported by the Netherlands Organisation for Scientific Research (NWO) through a VIDI grant (016.Vidi.189.087) and the Gravitation Programme Networks (024.002.003).

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 8 Decent Work and Economic Growth

Access to Document

10.1007/978-3-030-17953-3_7

Fixed-Order Scheduling on Parallel MachinesFinal published version, 283 KBLicence: Article 25fa Dutch Copyright Act

Persistent URL (handle)

Persistent link

Cite this

Bosman, T., Frascaria, D., Olver, N., Sitters, R., & Stougie, L. (2019). Fixed-Order Scheduling on Parallel Machines. In V. Nagarajan, & A. Lodi (Eds.), Integer Programming and Combinatorial Optimization: 20th International Conference, IPCO 2019, Ann Arbor, MI, USA, May 22-24, 2019, Proceedings (pp. 88-100). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11480). Springer Verlag. https://doi.org/10.1007/978-3-030-17953-3_7

Bosman, Thomas ; Frascaria, Dario ; Olver, Neil et al. / Fixed-Order Scheduling on Parallel Machines. Integer Programming and Combinatorial Optimization: 20th International Conference, IPCO 2019, Ann Arbor, MI, USA, May 22-24, 2019, Proceedings. editor / Viswanath Nagarajan ; Andrea Lodi. Springer Verlag, 2019. pp. 88-100 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{fff67312c59a4553a277ab9cef364673,

title = "Fixed-Order Scheduling on Parallel Machines",

abstract = "We consider the following natural scheduling problem: Given a sequence of jobs with weights and processing times, one needs to assign each job to one of m identical machines in order to minimize the sum of weighted completion times. The twist is that for machine the jobs assigned to it must obey the order of the input sequence, as is the case in multi-server queuing systems. We establish a constant factor approximation algorithm for this (strongly NP-hard) problem. Our approach is necessarily very different from what has been used for similar scheduling problems without the fixed-order assumption. We also give a QPTAS for the special case of unit processing times.",

author = "Thomas Bosman and Dario Frascaria and Neil Olver and Rene Sitters and Leen Stougie",

year = "2019",

doi = "10.1007/978-3-030-17953-3\_7",

language = "English",

isbn = "9783030179526",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "88--100",

editor = "Viswanath Nagarajan and Andrea Lodi",

booktitle = "Integer Programming and Combinatorial Optimization",

address = "Germany",

note = "20th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2019 ; Conference date: 22-05-2019 Through 24-05-2019",

}

Bosman, T, Frascaria, D, Olver, N, Sitters, R & Stougie, L 2019, Fixed-Order Scheduling on Parallel Machines. in V Nagarajan & A Lodi (eds), Integer Programming and Combinatorial Optimization: 20th International Conference, IPCO 2019, Ann Arbor, MI, USA, May 22-24, 2019, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11480, Springer Verlag, pp. 88-100, 20th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2019, Ann Arbor, United States, 22/05/19. https://doi.org/10.1007/978-3-030-17953-3_7

Fixed-Order Scheduling on Parallel Machines. / Bosman, Thomas; Frascaria, Dario; Olver, Neil et al.
Integer Programming and Combinatorial Optimization: 20th International Conference, IPCO 2019, Ann Arbor, MI, USA, May 22-24, 2019, Proceedings. ed. / Viswanath Nagarajan; Andrea Lodi. Springer Verlag, 2019. p. 88-100 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11480).

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

TY - GEN

T1 - Fixed-Order Scheduling on Parallel Machines

AU - Bosman, Thomas

AU - Frascaria, Dario

AU - Olver, Neil

AU - Sitters, Rene

AU - Stougie, Leen

PY - 2019

Y1 - 2019

N2 - We consider the following natural scheduling problem: Given a sequence of jobs with weights and processing times, one needs to assign each job to one of m identical machines in order to minimize the sum of weighted completion times. The twist is that for machine the jobs assigned to it must obey the order of the input sequence, as is the case in multi-server queuing systems. We establish a constant factor approximation algorithm for this (strongly NP-hard) problem. Our approach is necessarily very different from what has been used for similar scheduling problems without the fixed-order assumption. We also give a QPTAS for the special case of unit processing times.

AB - We consider the following natural scheduling problem: Given a sequence of jobs with weights and processing times, one needs to assign each job to one of m identical machines in order to minimize the sum of weighted completion times. The twist is that for machine the jobs assigned to it must obey the order of the input sequence, as is the case in multi-server queuing systems. We establish a constant factor approximation algorithm for this (strongly NP-hard) problem. Our approach is necessarily very different from what has been used for similar scheduling problems without the fixed-order assumption. We also give a QPTAS for the special case of unit processing times.

UR - https://www.scopus.com/pages/publications/85065867793

UR - https://www.scopus.com/pages/publications/85065867793#tab=citedBy

U2 - 10.1007/978-3-030-17953-3_7

DO - 10.1007/978-3-030-17953-3_7

M3 - Conference contribution

AN - SCOPUS:85065867793

SN - 9783030179526

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 88

EP - 100

BT - Integer Programming and Combinatorial Optimization

A2 - Nagarajan, Viswanath

A2 - Lodi, Andrea

PB - Springer Verlag

T2 - 20th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2019

Y2 - 22 May 2019 through 24 May 2019

ER -

Bosman T, Frascaria D, Olver N, Sitters R , Stougie L. Fixed-Order Scheduling on Parallel Machines. In Nagarajan V, Lodi A, editors, Integer Programming and Combinatorial Optimization: 20th International Conference, IPCO 2019, Ann Arbor, MI, USA, May 22-24, 2019, Proceedings. Springer Verlag. 2019. p. 88-100. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). Epub 2019 Apr 13. doi: 10.1007/978-3-030-17953-3_7

Fixed-Order Scheduling on Parallel Machines

Abstract

Publication series

Conference

Funding

UN SDGs

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this