Document Open Access Logo

On the Fine-Grained Parameterized Complexity of Partial Scheduling to Minimize the Makespan

Authors Jesper Nederlof, Céline M. F. Swennenhuis

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2020.25.pdf
  • Filesize: 0.65 MB
  • 17 pages

Document Identifiers

Author Details

Jesper Nederlof
  • Utrecht University, Algorithms and Complexity Group, The Netherlands
Céline M. F. Swennenhuis
  • Eindhoven University of Technology, Combinatorial Optimization Group, The Netherlands

Funding

  • Nederlof, Jesper: ERC project no. 617951. and no. 853234. and NWO project no. 024.002.003.
  • Swennenhuis, Céline M. F.: NWO project no. 613.009.031b, ERC project no. 617951.

Cite AsGet BibTex

Jesper Nederlof and Céline M. F. Swennenhuis. On the Fine-Grained Parameterized Complexity of Partial Scheduling to Minimize the Makespan. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.IPEC.2020.25

Abstract

We study a natural variant of scheduling that we call partial scheduling: In this variant an instance of a scheduling problem along with an integer k is given and one seeks an optimal schedule where not all, but only k jobs, have to be processed. Specifically, we aim to determine the fine-grained parameterized complexity of partial scheduling problems parameterized by k for all variants of scheduling problems that minimize the makespan and involve unit/arbitrary processing times, identical/unrelated parallel machines, release/due dates, and precedence constraints. That is, we investigate whether algorithms with runtimes of the type f(k)n^𝒪(1) or n^𝒪(f(k)) exist for a function f that is as small as possible. Our contribution is two-fold: First, we categorize each variant to be either in 𝖯, NP-complete and fixed-parameter tractable by k, or 𝖶[1]-hard parameterized by k. Second, for many interesting cases we further investigate the run time on a finer scale and obtain run times that are (almost) optimal assuming the Exponential Time Hypothesis. As one of our main technical contributions, we give an 𝒪(8^k k(|V|+|E|)) time algorithm to solve instances of partial scheduling problems minimizing the makespan with unit length jobs, precedence constraints and release dates, where G = (V,E) is the graph with precedence constraints.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Fixed-Parameter Tractability
  • Scheduling
  • Precedence Constraints

Metrics

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

Related Versions

References

  1. Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. Journal of the ACM, 42(4):844-856, 1995. Google Scholar
  2. Stéphane Bessy and Rodolphe Giroudeau. Parameterized complexity of a coupled-task scheduling problem. Journal of Scheduling, 22(3):305-313, 2019. Google Scholar
  3. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Fourier meets Möbius: fast subset convolution. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 67-74. ACM, 2007. Google Scholar
  4. Hans L. Bodlaender and Michael R. Fellows. 𝖶[2]-hardness of precedence constrained k-processor scheduling. Operations Research Letters, 18(2):93-97, 1995. Google Scholar
  5. Julia Chuzhoy, Rafail Ostrovsky, and Yuval Rabani. Approximation algorithms for the job interval selection problem and related scheduling problems. Mathematics of Operations Research, 31(4):730-738, 2006. Google Scholar
  6. Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  7. Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, and Jakub Onufry Wojtaszczyk. Scheduling partially ordered jobs faster than 2ⁿ. Algorithmica, 68(3):692-714, 2014. URL: https://doi.org/10.1007/s00453-012-9694-7.
  8. Joonyup Eun, Chang Sup Sung, and Eun-Seok Kim. Maximizing total job value on a single machine with job selection. Journal of the Operational Research Society, 68(9):998-1005, 2017. Google Scholar
  9. Michael R. Fellows and Catherine McCartin. On the parametric complexity of schedules to minimize tardy tasks. Theoretical Computer Science, 298(2):317-324, 2003. Google Scholar
  10. Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Google Scholar
  11. Ron L. Graham, Eugene L. Lawler, Jan Karel Lenstra, and Alexander H. G. Rinnooy Kan. Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics, 5(2):287-326, 1979. Google Scholar
  12. Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, and Danny Segev. Scheduling with outliers. In Irit Dinur, Klaus Jansen, Joseph Naor, and José D. P. Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 12th International Workshop, APPROX 2009, and 13th International Workshop, RANDOM 2009, Berkeley, CA, USA, August 21-23, 2009. Proceedings, volume 5687 of Lecture Notes in Computer Science, pages 149-162. Springer, 2009. Google Scholar
  13. Danny Hermelin, Matthias Mnich, and Simon Omlor. Single machine batch scheduling to minimize the weighted number of tardy jobs. CoRR, 2019. URL: http://arxiv.org/abs/1911.12350.
  14. Klaus Jansen, Felix Land, and Maren Kaluza. Precedence scheduling with unit execution time is equivalent to parametrized biclique. In International Conference on Current Trends in Theory and Practice of Informatics, pages 329-343. Springer, 2016. Google Scholar
  15. Christos Koulamas and Shrikant S. Panwalkar. A note on combined job selection and sequencing problems. Naval Research Logistics, 60(6):449-453, 2013. Google Scholar
  16. Christophe Lenté, Matthieu Liedloff, Ameur Soukhal, and Vincent T'kindt. Exponential algorithms for scheduling problems, 2014. Google Scholar
  17. Dániel Marx. Can you beat treewidth? Theory of Computing, 6:85-112, 2010. Google Scholar
  18. Nicole Megow, Matthias Mnich, and Gerhard Woeginger. Lorentz Workshop `Scheduling Meets Fixed-Parameter Tractability', 2019. Google Scholar
  19. Matthias Mnich and René van Bevern. Parameterized complexity of machine scheduling: 15 open problems. Computers & Operations Research, 2018. Google Scholar
  20. Matthias Mnich and Andreas Wiese. Scheduling and fixed-parameter tractability. Mathematical Programming, 154(1-2):533-562, 2015. Google Scholar
  21. J. Michael Moore. An n job, one machine sequencing algorithm for minimizing the number of late jobs. Management Science, 15(1):102-109, 1968. Google Scholar
  22. Jesper Nederlof and Céline Swennenhuis. Parameterized complexity of partial scheduling. arXiv preprint, 2019. URL: http://arxiv.org/abs/1912.03185.
  23. Michael L. Pinedo. Scheduling: Theory, Algorithms, and Systems. Springer Publishing Company, Incorporated, 3rd edition, 2008. Google Scholar
  24. Jirí Sgall. Open problems in throughput scheduling. In Algorithms - ESA 2012 - 20th Annual European Symposium, Ljubljana, Slovenia, September 10-12, 2012. Proceedings, pages 2-11, 2012. Google Scholar
  25. Dvir Shabtay, Nufar Gaspar, and Moshe Kaspi. A survey on offline scheduling with rejection. Journal of Scheduling, 16(1):3-28, 2013. Google Scholar
  26. René van Bevern, Robert Bredereck, Laurent Bulteau, Christian Komusiewicz, Nimrod Talmon, and Gerhard J. Woeginger. Precedence-constrained scheduling problems parameterized by partial order width. In Discrete Optimization and Operations Research - 9th International Conference, DOOR 2016, Vladivostok, Russia, September 19-23, 2016, Proceedings, pages 105-120, 2016. Google Scholar
  27. René van Bevern, Matthias Mnich, Rolf Niedermeier, and Mathias Weller. Interval scheduling and colorful independent sets. Journal of Scheduling, 18(5):449-469, 2015. Google Scholar
  28. David P. Williamson and David B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2011. Google Scholar
  29. Bibo Yang and Joseph Geunes. A single resource scheduling problem with job-selection flexibility, tardiness costs and controllable processing times. Computers & Industrial Engineering, 53(3):420-432, 2007. Google Scholar
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