Document Open Access Logo

Merging Nodes in Search Trees: an Exact Exponential Algorithm for the Single Machine Total Tardiness Scheduling Problem

Authors Lei Shang, Michele Garraffa, Federico Della Croce, Vincent T'Kindt

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2017.28.pdf
  • Filesize: 0.66 MB
  • 12 pages

Document Identifiers

Author Details

Lei Shang
Michele Garraffa
Federico Della Croce
Vincent T'Kindt

Cite As Get BibTex

Lei Shang, Michele Garraffa, Federico Della Croce, and Vincent T'Kindt. Merging Nodes in Search Trees: an Exact Exponential Algorithm for the Single Machine Total Tardiness Scheduling Problem. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 28:1-28:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.IPEC.2017.28

Abstract

This paper proposes an exact exponential algorithm for the problem of minimizing the total tardiness of jobs on a single machine. It exploits the structure of a basic branch-and-reduce framework based on the well known Lawler's decomposition property. The proposed algorithm, called branch-and-merge, is an improvement of the branch-and-reduce technique with the embedding of a node merging operation.  Its time complexity is O*(2.247^n) keeping the space complexity polynomial. The branch-and-merge technique is likely to be generalized to other sequencing problems with similar decomposition properties.

Subject Classification

Keywords
  • Exact exponential algorithm
  • Single machine total tardiness
  • Branch-and-merge

Metrics

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

References

  1. Federico Della Croce, R Tadei, P Baracco, and A Grosso. A new decomposition approach for the single machine total tardiness scheduling problem. Journal of the Operational Research Society, pages 1101-1106, 1998. Google Scholar
  2. Jianzhong Du and Joseph Y-T Leung. Minimizing total tardiness on one machine is NP-hard. Mathematics of Operations Research, 15(3):483-495, 1990. Google Scholar
  3. Hamilton Emmons. One-machine sequencing to minimize certain functions of job tardiness. Operations Research, 17(4):701-715, 1969. Google Scholar
  4. Fedor V Fomin and Dieter Kratsch. Exact exponential algorithms. Springer Science &Business Media, 2010. Google Scholar
  5. Michele Garraffa, Lei Shang, Federico Della Croce, and Vincent T'Kindt. An Exact Exponential Branch-and-Merge Algorithm for the Single Machine Total Tardiness Problem. submitted to TCS, 2017. URL: https://hal.archives-ouvertes.fr/hal-01477835.
  6. Christos Koulamas. The single-machine total tardiness scheduling problem: review and extensions. European Journal of Operational Research, 202(1):1-7, 2010. Google Scholar
  7. Eugene L Lawler. A "pseudopolynomial" algorithm for sequencing jobs to minimize total tardiness. Annals of Discrete Mathematics, 1:331-342, 1977. Google Scholar
  8. Christophe Lenté, Mathieu Liedloff, Ameur Soukhal, and Vincent T'Kindt. Exponential Algorithms for Scheduling Problems. HAL, https://hal.archives-ouvertes.fr/hal-00944382, 2014.
  9. C.N Potts and L.N Van Wassenhove. A decomposition algorithm for the single machine total tardiness problem. Operations Research Letters, 1(5):177-181, 1982. Google Scholar
  10. Wlodzimierz Szwarc. Single machine total tardiness problem revisited. Creative and Innovative Approaches to the Science of Management, Quorum Books, pages 407-419, 1993. Google Scholar
  11. Wlodzimierz Szwarc, Andrea Grosso, and Federico Della Croce. Algorithmic paradoxes of the single-machine total tardiness problem. Journal of Scheduling, 4(2):93-104, 2001. Google Scholar
  12. Wlodzimierz Szwarc and Samar K Mukhopadhyay. Decomposition of the single machine total tardiness problem. Operations Research Letters, 19(5):243-250, 1996. Google Scholar
  13. Gerhard J. Woeginger. Exact Algorithms for NP-hard Problems: A Survey. In Michael Jünger, Gerhard Reinelt, and Giovanni Rinaldi, editors, Combinatorial Optimization — Eureka, You Shrink!, volume 2570 of Lecture Notes in Computer Science, pages 185-207. Springer Berlin Heidelberg, 2003. 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