HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download

Contributor : Marie-France Sagot Connect in order to contact the contributor
Submitted on : Tuesday, October 29, 2019 - 8:13:41 AM
Last modification on : Friday, May 29, 2020 - 6:56:01 AM
Long-term archiving on: : Thursday, January 30, 2020 - 1:27:03 PM


Files produced by the author(s)



Thomas Bosman, Dario Frascaria, Neil Olver, Rene Sitters, Leen Stougie. Fixed-Order Scheduling on Parallel Machines. Integer Programming and Combinatorial Optimization (IPCO), 2019, Ann Arbor, United States. pp.88-100, ⟨10.1007/978-3-030-17953-3_7⟩. ⟨hal-02336592⟩



Record views


Files downloads