An exact exponential branch-and-merge algorithm for the single machine total tardiness problem

DOI10.1016/j.tcs.2018.05.040zbMath1407.90153OpenAlexW2805463268WikidataQ115566733 ScholiaQ115566733MaRDI QIDQ1786599

Michele Garraffa, Lei Shang, Vincent T'kindt, Frederico Della Croce

Publication date: 24 September 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2018.05.040

zbMATH Keywords

dynamic programmingexact exponential algorithmbranch and mergesingle machine total tardiness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39)

Related Items (6)

Deep learning-driven scheduling algorithm for a single machine problem minimizing the total tardiness ⋮ Parallel machine scheduling with minimum number of tardy jobs: approximation and exponential algorithms ⋮ \textit{Branch} \& \textit{Memorize} exact algorithms for sequencing problems: efficient embedding of memorization into search trees ⋮ Exponential time algorithms for just-in-time scheduling problems with common due date and symmetric weights ⋮ Merging Nodes in Search Trees: an Exact Exponential Algorithm for the Single Machine Total Tardiness Scheduling Problem ⋮ Moderate exponential-time algorithms for scheduling problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On an extension of the Sort \& Search method with application to scheduling theory
• Exact exponential algorithms.
• Scheduling and fixed-parameter tractability
• The single-machine total tardiness scheduling problem: review and extensions
• Decomposition of the single machine total tardiness problem
• A decomposition algorithm for the single machine total tardiness problem
• Revisiting branch and bound search strategies for machine scheduling problems
• On exact algorithms for treewidth
• A new decomposition approach for the single machine total tardiness scheduling problem
• Minimizing Total Tardiness on One Machine is NP-Hard
• Expected Computation Time for Hamiltonian Path problem
• Merging Nodes in Search Trees: an Exact Exponential Algorithm for the Single Machine Total Tardiness Scheduling Problem
• One-Machine Sequencing to Minimize Certain Functions of Job Tardiness
• Algorithmic paradoxes of the single-machine total tardiness problem

This page was built for publication: An exact exponential branch-and-merge algorithm for the single machine total tardiness problem