Fixed-Order Scheduling on Parallel Machines

Thomas Bosman, Dario Frascaria, Neil Olver, René Sitters, Leen Stougie

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

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 languageEnglish
Title of host publicationInteger Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, Proceedings
EditorsAndrea Lodi, Viswanath Nagarajan
PublisherSpringer Verlag
Pages88-100
Number of pages13
ISBN (Print)9783030179526
DOIs
Publication statusPublished - 1 Jan 2019
Event20th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2019 - Ann Arbor, United States
Duration: 22 May 201924 May 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11480 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference20th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2019
CountryUnited States
CityAnn Arbor
Period22/05/1924/05/19

Fingerprint

Parallel Machines
Scheduling Problem
Scheduling
Multi-server
Queuing System
Approximation algorithms
Completion Time
NP-hard Problems
Processing
Twist
Assign
Approximation Algorithms
Computational complexity
Servers
Minimise
Unit

Cite this

Bosman, T., Frascaria, D., Olver, N., Sitters, RE., & Stougie, L. (2019). Fixed-Order Scheduling on Parallel Machines. In A. Lodi, & V. Nagarajan (Eds.), Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, Proceedings (pp. 88-100). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11480 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-030-17953-3_7
Bosman, Thomas ; Frascaria, Dario ; Olver, Neil ; Sitters, René ; Stougie, Leen. / Fixed-Order Scheduling on Parallel Machines. Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, Proceedings. editor / Andrea Lodi ; Viswanath Nagarajan. 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 René Sitters and Leen Stougie",
year = "2019",
month = "1",
day = "1",
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 = "Andrea Lodi and Viswanath Nagarajan",
booktitle = "Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, Proceedings",
address = "Germany",

}

Bosman, T, Frascaria, D, Olver, N, Sitters, RE & Stougie, L 2019, Fixed-Order Scheduling on Parallel Machines. in A Lodi & V Nagarajan (eds), Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11480 LNCS, 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; Sitters, René Stougie, Leen.

Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, Proceedings. ed. / Andrea Lodi; Viswanath Nagarajan. 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 LNCS).

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Fixed-Order Scheduling on Parallel Machines

AU - Bosman, Thomas

AU - Frascaria, Dario

AU - Olver, Neil

AU - Sitters, René

AU - Stougie, Leen

PY - 2019/1/1

Y1 - 2019/1/1

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 - http://www.scopus.com/inward/record.url?scp=85065867793&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85065867793&partnerID=8YFLogxK

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

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

M3 - Conference contribution

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 - 20th International Conference, IPCO 2019, Proceedings

A2 - Lodi, Andrea

A2 - Nagarajan, Viswanath

PB - Springer Verlag

ER -

Bosman T, Frascaria D, Olver N, Sitters RE, Stougie L. Fixed-Order Scheduling on Parallel Machines. In Lodi A, Nagarajan V, editors, Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 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)). https://doi.org/10.1007/978-3-030-17953-3_7