2019
Fixed-Order Scheduling on Parallel Machines
Publication
Publication
Presented at the
International Conference on Integer Programming and Combinatorial Optimization (May 2019), Ann Arbor, MI, USA,
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.
| Additional Metadata | |
|---|---|
| doi.org/10.1007/978-3-030-17953-3_7 | |
| Lecture Notes in Computer Science/Lecture Notes in Artificial Intelligence | |
| Networks | |
| International Conference on Integer Programming and Combinatorial Optimization | |
| Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |
|
Bosman, T., Frascaria, D. (Dario), Olver, N., Sitters, R., & Stougie, L. (2019). Fixed-Order Scheduling on Parallel Machines. In International Conference on Integer Programming and Combinatorial Optimization, IPCO 2019 (pp. 88–100). doi:10.1007/978-3-030-17953-3_7 |
|
