Hardness of Interval Scheduling on Unrelated Machines
Document Open Access Logo

Hardness of Interval Scheduling on Unrelated Machines

Authors Danny Hermelin, Yuval Itzhaki, Hendrik Molter, Dvir Shabtay

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2022.18.pdf
  • Filesize: 0.62 MB
  • 16 pages

Document Identifiers

Author Details

Danny Hermelin
  • Department of Industrial Engineering and Management, Ben-Gurion University of the Negev, Beer-Sheva, Israel
Yuval Itzhaki
  • Department of Industrial Engineering and Management, Ben-Gurion University of the Negev, Beer-Sheva, Israel
Hendrik Molter
  • Department of Industrial Engineering and Management, Ben-Gurion University of the Negev, Beer-Sheva, Israel
Dvir Shabtay
  • Department of Industrial Engineering and Management, Ben-Gurion University of the Negev, Beer-Sheva, Israel

Funding

Supported by the ISF, grant No. 1070/20.

Cite As Get BibTex

Danny Hermelin, Yuval Itzhaki, Hendrik Molter, and Dvir Shabtay. Hardness of Interval Scheduling on Unrelated Machines. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.IPEC.2022.18

Abstract

We provide new (parameterized) computational hardness results for Interval Scheduling on Unrelated Machines. It is a classical scheduling problem motivated from just-in-time or lean manufacturing, where the goal is to complete jobs exactly at their deadline. We are given n jobs and m machines. Each job has a deadline, a weight, and a processing time that may be different on each machine. The goal is find a schedule that maximizes the total weight of jobs completed exactly at their deadline. Note that this uniquely defines a processing time interval for each job on each machine.
Interval Scheduling on Unrelated Machines is closely related to coloring interval graphs and has been thoroughly studied for several decades. However, as pointed out by Mnich and van Bevern [Computers & Operations Research, 2018], the parameterized complexity for the number m of machines as a parameter remained open. We resolve this by showing that Interval Scheduling on Unrelated Machines is W[1]-hard when parameterized by the number m of machines. To this end, we prove W[1]-hardness with respect to m of the special case where we have parallel machines with eligible machine sets for jobs. This answers Open Problem 8 of Mnich and van Bevern’s list of 15 open problems in the parameterized complexity of scheduling [Computers & Operations Research, 2018].
Furthermore, we resolve the computational complexity status of the unweighted version of Interval Scheduling on Unrelated Machines by proving that it is NP-complete. This answers an open question by Sung and Vlach [Journal of Scheduling, 2005].

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Discrete mathematics
  • Theory of computation → W hierarchy
  • Theory of computation → Scheduling algorithms
Keywords
  • Just-in-time scheduling
  • Parallel machines
  • Eligible machine sets
  • W[1]-hardness
  • NP-hardness

Metrics

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

References

  1. Enrico Angelelli, Nicola Bianchessi, and Carlo Filippi. Optimal interval scheduling with a resource constraint. Computers & Operations Research, 51:268-281, 2014. Google Scholar
  2. Esther M. Arkin and Ellen B. Silverberg. Scheduling jobs with fixed start and end times. Discrete Applied Mathematics, 18(1):1-8, 1987. Google Scholar
  3. Kenneth R Baker and Gary D Scudder. Sequencing with earliness and tardiness penalties: a review. Operations Research, 38(1):22-36, 1990. Google Scholar
  4. Matthias Bentert, René van Bevern, and Rolf Niedermeier. Inductive k-independent graphs and c-colorable subgraphs in scheduling: a review. Journal of Scheduling, 22(1):3-20, 2019. Google Scholar
  5. 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
  6. René van Bevern, Rolf Niedermeier, and Ondřej Suchỳ. A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack. Journal of Scheduling, 20(3):255-265, 2017. Google Scholar
  7. Khalid I Bouzina and Hamilton Emmons. Interval scheduling on identical machines. Journal of Global Optimization, 9(3):379-393, 1996. Google Scholar
  8. Martin C Carlisle and Errol L Lloyd. On the k-coloring of intervals. Discrete Applied Mathematics, 59(3):225-235, 1995. Google Scholar
  9. Ondřej Čepek and Shao Chin Sung. A quadratic time algorithm to maximize the number of just-in-time jobs on identical parallel machines. Computers & operations research, 32(12):3265-3271, 2005. Google Scholar
  10. Michael R. Fellows, Danny Hermelin, Frances Rosamond, and Stéphane Vialette. On the parameterized complexity of multiple-interval graph problems. Theoretical Computer Science, 410(1):53-61, 2009. Google Scholar
  11. Fǎnicǎ Gavril. The intersection graphs of subtrees in trees are exactly the chordal graphs. Journal of Combinatorial Theory, Series B, 16(1):47-56, 1974. Google Scholar
  12. Ronald L. Graham. Bounds on multiprocessing timing anomalies. SIAM Journal on Applied Mathematics, 17(2):416-429, 1969. Google Scholar
  13. Kunihiko Hiraishi, Eugene Levner, and Milan Vlach. Scheduling of parallel identical machines to maximize the weighted number of just-in-time jobs. Computers & Operations Research, 29(7):841-848, 2002. Google Scholar
  14. Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. Journal of Computer and System Sciences, 62(2):367-375, 2001. Google Scholar
  15. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512-530, 2001. Google Scholar
  16. Antoon WJ Kolen, Jan Karel Lenstra, Christos H Papadimitriou, and Frits CR Spieksma. Interval scheduling: A survey. Naval Research Logistics (NRL), 54(5):530-543, 2007. Google Scholar
  17. Mikhail Y. Kovalyov, Chi To Ng, and T.C. Edwin Cheng. Fixed interval scheduling: Models, applications, computational complexity and algorithms. European Journal of Operational Research, 178(2):331-342, 2007. Google Scholar
  18. John F Krafcik. Triumph of the lean production system. Sloan Management Review, 30(1):41-52, 1988. Google Scholar
  19. Avital Lann and Gur Mosheiov. Single machine scheduling to minimize the number of early and tardy jobs. Computers & Operations Research, 23(8):769-781, 1996. Google Scholar
  20. Yaron Leyvand, Dvir Shabtay, George Steiner, and Liron Yedidsion. Just-in-time scheduling with controllable processing times on parallel machines. Journal of Combinatorial Optimization, 19(3):347-368, 2010. Google Scholar
  21. Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Lower bounds based on the exponential time hypothesis. Bulletin of EATCS, 3(105), 2013. Google Scholar
  22. Matthias Mnich and René van Bevern. Parameterized complexity of machine scheduling: 15 open problems. Computers & Operations Research, 100:254-261, 2018. Google Scholar
  23. Taiichi Ohno and Norman Bodek. Toyota production system: beyond large-scale production. Productivity Press, 1988. Google Scholar
  24. Donald J. Rose, Robert Endre Tarjan, and George S. Lueker. Algorithmic aspects of vertex elimination on graphs. SIAM Journal on Computing, 5(2):266-283, 1976. Google Scholar
  25. Dvir Shabtay. The just-in-time scheduling problem in a flow-shop scheduling system. European Journal of Operational Research, 216(3):521-532, 2012. Google Scholar
  26. Shigeo Shingo and Andrew P Dillon. A revolution in manufacturing: the SMED system. Productivity Press, 1985. Google Scholar
  27. Frits C.R. Spieksma. On the approximability of an interval scheduling problem. Journal of Scheduling, 2(5):215-227, 1999. Google Scholar
  28. Shao Chin Sung and Milan Vlach. Maximizing weighted number of just-in-time jobs on unrelated parallel machines. Journal of Scheduling, 8(5):453-460, 2005. Google Scholar
  29. Craig A. Tovey. A simplified NP-complete satisfiability problem. Discrete Applied Mathematics, 8(1):85-89, 1984. Google Scholar
  30. James P Womack and Daniel T Jones. Lean thinking - banish waste and create wealth in your corporation. Journal of the Operational Research Society, 48(11):1148-1148, 1997. Google Scholar
  31. James P Womack, Daniel T Jones, and Daniel Roos. The machine that changed the world: The story of lean production - Toyota’s secret weapon in the global car wars that is now revolutionizing world industry. Simon and Schuster, 1990. Google Scholar
  32. Mihalis Yannakakis and Fǎnicǎ Gavril. The maximum k-colorable subgraph problem for chordal graphs. Information Processing Letters, 24(2):133-137, 1987. 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 About DROPS Imprint Privacy Contact