2026-07-21T14:16:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8546 2024-03-06T10:41:32Z ddc:004 open_access

Merging Nodes in Search Trees: an Exact Exponential Algorithm for the Single Machine Total Tardiness Scheduling Problem Shang, Lei Garraffa, Michele Della Croce, Federico T'Kindt, Vincent Exact exponential algorithm Single machine total tardiness Branch-and-merge 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Lei Shang and Michele Garraffa and Federico Della Croce and Vincent T'Kindt 2018 Is Part Of LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2017.28 urn:nbn:de:0030-drops-85468 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.28 eng https://creativecommons.org/licenses/by/3.0/legalcode