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

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 -