Parameterized complexity of scheduling chains of jobs with delays. (English) Zbl 07764095
Cao, Yixin (ed.) et al., 15th international symposium on parameterized and exact computation, IPEC 2020, Hong Kong, China, virtual conference, December 14–18, 2020. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 180, Article 4, 15 p. (2020).
Summary: In this paper, we consider the parameterized complexity of the following scheduling problem. We must schedule a number of jobs on \(m\) machines, where each job has unit length, and the graph of precedence constraints consists of a set of chains. Each precedence constraint is labelled with an integer that denotes the exact (or minimum) delay between the jobs. We study different cases; delays can be given in unary and in binary, and the case that we have a single machine is discussed separately. We consider the complexity of this problem parameterized by the number of chains, and by the thickness of the instance, which is the maximum number of chains whose intervals between release date and deadline overlap.
We show that this scheduling problem with exact delays in unary is \(W[t]\)-hard for all \(t\), when parameterized by the thickness, even when we have a single machine \((m=1)\). When parameterized by the number of chains, this problem is \(W[1]\)-complete when we have a single or a constant number of machines, and \(W[2]\)-complete when the number of machines is a variable. The problem with minimum delays, given in unary, parameterized by the number of chains (and as a simple corollary, also when parameterized by the thickness) is \(W[1]\)-hard for a single or a constant number of machines, and \(W[2]\)-hard when the number of machines is variable.
With a dynamic programming algorithm, one can show membership in XP for exact and minimum delays in unary, for any number of machines, when parameterized by thickness or number of chains. For a single machine, with exact delays in binary, parameterized by the number of chains, membership in XP can be shown with branching and solving a system of difference constraints. For all other cases for delays in binary, membership in XP is open.
For the entire collection see [Zbl 1451.68020].
We show that this scheduling problem with exact delays in unary is \(W[t]\)-hard for all \(t\), when parameterized by the thickness, even when we have a single machine \((m=1)\). When parameterized by the number of chains, this problem is \(W[1]\)-complete when we have a single or a constant number of machines, and \(W[2]\)-complete when the number of machines is a variable. The problem with minimum delays, given in unary, parameterized by the number of chains (and as a simple corollary, also when parameterized by the thickness) is \(W[1]\)-hard for a single or a constant number of machines, and \(W[2]\)-hard when the number of machines is variable.
With a dynamic programming algorithm, one can show membership in XP for exact and minimum delays in unary, for any number of machines, when parameterized by thickness or number of chains. For a single machine, with exact delays in binary, parameterized by the number of chains, membership in XP can be shown with branching and solving a system of difference constraints. For all other cases for delays in binary, membership in XP is open.
For the entire collection see [Zbl 1451.68020].
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 68Q27 | Parameterized complexity, tractability and kernelization |
| 68Wxx | Algorithms in computer science |
References:
| [1] | Martin Aigner and Günter M. Ziegler. Bertrand’s postulate. In Proofs from THE BOOK, pages 7-12. Springer, 2001. doi:10.1007/978-3-662-04315-8_2. · Zbl 0978.00002 · doi:10.1007/978-3-662-04315-8_2 |
| [2] | S. Bessy and R. Giroudeau. Parameterized complexity of a coupled-task scheduling problem. Journal of Scheduling, 22(3):305-313, 2019. doi:10.1007/s10951-018-0581-1. · Zbl 1427.90132 · doi:10.1007/s10951-018-0581-1 |
| [3] | Hans L. Bodlaender and Michael R. Fellows. W [2]-hardness of precedence constrained K-processor scheduling. Operations Research Letters, 18(2):93-97, 1995. doi:10.1016/ 0167-6377(95)00031-9. · Zbl 0857.90056 · doi:10.1016/0167-6377(95)00031-9 |
| [4] | Peter Brucker, Johann Hurink, and Wieslaw Kubiak. Scheduling identical jobs with chain precedence constraints on two uniform machines. Mathematical Methods of Operations Research, 49:211-219, 1999. doi:10.1007/PL00020913. · Zbl 0941.90019 · doi:10.1007/PL00020913 |
| [5] | Mark Cieliebak, Thomas Erlebach, Fabian Hennecke, Birgitta Weber, and Peter Widmayer. Scheduling with release times and deadlines on a minimum number of machines. In Exploring New Frontiers of Theoretical Informatics. IFIP International Federation for Information Processing, volume 155, pages 209-222, 2004. doi:10.1007/1-4020-8141-3_18. · Zbl 1161.68360 · doi:10.1007/1-4020-8141-3_18 |
| [6] | Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, 3rd Edition. MIT Press, 2009. URL: http://mitpress.mit.edu/books/ introduction-algorithms-third-edition. · Zbl 1187.68679 |
| [7] | Rodney G. Downey and Michael R. Fellows. Fixed-parameter tractability and complete-ness I: Basic results. SIAM Journal on Computing, 24:873-921, 1995. doi:10.1137/ S0097539792228228. · Zbl 0830.68063 · doi:10.1137/S0097539792228228 |
| [8] | Rodney G. Downey and Michael R. Fellows. Fixed-parameter tractability and completeness II: On completeness for W [1]. · Zbl 0828.68077 |
| [9] | Theoretical Computer Science, 141(1-2):109-131, 1995. doi: 10.1016/0304-3975(94)00097-3. · Zbl 0873.68059 · doi:10.1016/0304-3975(94)00097-3 |
| [10] | P. Erdös and P. Turán. On a problem of Sidon in additive number theory, and on some related problems. Journal of the London Mathematical Society, s1-16(4):212-215, 1941. doi:10.1112/jlms/s1-16.4.212. · Zbl 0061.07301 · doi:10.1112/jlms/s1-16.4.212 |
| [11] | Michael R. Fellows and Catherine McCartin. On the parametric complexity of schedules to minimize tardy tasks. Theoretical Computer Science, 298(2):317-324, 2003. doi:10.1016/ S0304-3975(02)00811-3. · Zbl 1038.68049 · doi:10.1016/S0304-3975(02)00811-3 |
| [12] | Michael R. Fellows and Frances A. Rosamond. Collaborating with Hans: Some remaining wonderments. In Fedor V. Fomin, Stefan Kratsch, and Erik Jan van Leeuwen, editors, Treewidth, Kernels, and Algorithms -Essays Dedicated to Hans L. Bodlaender on the Occasion of His 60th Birthday, volume 12160 of Lecture Notes in Computer Science, pages 7-17. Springer, 2020. doi:10.1007/978-3-030-42071-0_2. · Zbl 07604201 · doi:10.1007/978-3-030-42071-0_2 |
| [13] | Matthias Mnich and René van Bevern. Parameterized complexity of machine scheduling: 15 open problems. Comput. Oper. Res., 100:254-261, 2018. doi:10.1016/j.cor.2018.07.020. · Zbl 1458.90333 · doi:10.1016/j.cor.2018.07.020 |
| [14] | Matthias Mnich and Andreas Wiese. Scheduling and fixed-parameter tractability. Mathematical Programming, 154(1):533-562, 2015. doi:10.1007/s10107-014-0830-9. · Zbl 1332.68089 · doi:10.1007/s10107-014-0830-9 |
| [15] | René van Bevern, Christian Komusiewicz, and Manuel Sorge. A parameterized approximation algorithm for the mixed and windy capacitated arc routing problem: Theory and experiments. Networks, 70(3):262-278, 2017. doi:10.1002/net.21742. · Zbl 1539.90130 · doi:10.1002/net.21742 |
| [16] | Erick D. Wikum, Donna C. Llewellyn, and George L. Nemhauser. One-machine generalized precedence constrained scheduling problems. Operations Research Letters, 16(2):87-99, 1994. doi:10.1016/0167-6377(94)90064-7. · Zbl 0823.90066 · doi:10.1016/0167-6377(94)90064-7 |
| [17] | Gerhard J. Woeginger. A comment on scheduling on uniform machines under chain-type precedence constraints. Operations Research Letters, 26(3):107-109, 2000. doi:10.1016/ S0167-6377(99)00076-0. · Zbl 0955.90036 · doi:10.1016/S0167-6377(99)00076-0 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
