Document Open Access Logo

Parameterized Complexity of Scheduling Chains of Jobs with Delays

Authors Hans L. Bodlaender , Marieke van der Wegen

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2020.4.pdf
  • Filesize: 0.62 MB
  • 15 pages

Document Identifiers

Author Details

Hans L. Bodlaender
  • Department of Information and Computing Sciences, Utrecht University, The Netherlands
Marieke van der Wegen
  • Department of Information and Computing Sciences, Utrecht University, The Netherlands
  • Mathematical Institute, Utrecht University, The Netherlands

Acknowledgements

We would like to thank Sukanya Pandey for helpful discussions.

Cite AsGet BibTex

Hans L. Bodlaender and Marieke van der Wegen. Parameterized Complexity of Scheduling Chains of Jobs with Delays. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.IPEC.2020.4

Abstract

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.

Subject Classification

ACM Subject Classification
  • Computing methodologies → Planning and scheduling
  • Theory of computation → Fixed parameter tractability
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Scheduling
  • parameterized complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

  • Missing proofs can be found at the full version of this paper, which can be found at arXiv [Hans L. Bodlaender and Marieke van der Wegen, 2020] (https://arxiv.org/abs/2007.09023).

References

  1. Martin Aigner and Günter M. Ziegler. Bertrand’s postulate. In Proofs from THE BOOK, pages 7-12. Springer, 2001. URL: https://doi.org/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. URL: https://doi.org/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. URL: https://doi.org/10.1016/0167-6377(95)00031-9.
  4. Hans L. Bodlaender and Marieke van der Wegen. Parameterized complexity of scheduling chains of jobs with delays, 2020. arXiv preprint. URL: http://arxiv.org/abs/2007.09023.
  5. 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. URL: https://doi.org/10.1007/PL00020913.
  6. 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. URL: https://doi.org/10.1007/1-4020-8141-3_18.
  7. 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.
  8. Rodney G. Downey and Michael R. Fellows. Fixed-parameter tractability and completeness I: Basic results. SIAM Journal on Computing, 24:873-921, 1995. URL: https://doi.org/10.1137/S0097539792228228.
  9. Rodney G. Downey and Michael R. Fellows. Fixed-parameter tractability and completeness II: On completeness for W[1]. Theoretical Computer Science, 141(1-2):109-131, 1995. URL: https://doi.org/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. URL: https://doi.org/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. URL: https://doi.org/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. URL: https://doi.org/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. URL: https://doi.org/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. URL: https://doi.org/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. URL: https://doi.org/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. URL: https://doi.org/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. URL: https://doi.org/10.1016/S0167-6377(99)00076-0.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact