Back to Search
Start Over
An exact exponential branch-and-merge algorithm for the single machine total tardiness problem.
- Source :
-
Theoretical Computer Science . Oct2018, Vol. 745, p133-149. 17p. - Publication Year :
- 2018
-
Abstract
- Abstract This paper proposes an exact exponential algorithm for the single machine total tardiness problem. It exploits the structure of a basic branch-and-reduce framework based on the well known Lawler's decomposition property that solves the problem with worst-case complexity in time O ⁎ (3 n) and polynomial space. 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 converges to O ⁎ (2 n) keeping the space complexity polynomial. This improves upon the best-known complexity result for this problem provided by dynamic programming across the subsets with O ⁎ (2 n) worst-case time and space complexity. The branch-and-merge technique is likely to be generalized to other sequencing problems with similar decomposition properties. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 745
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 131631664
- Full Text :
- https://doi.org/10.1016/j.tcs.2018.05.040