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

DOI10.1016/J.TCS.2018.05.040MaRDI QIDQ1786599zbMATHOpenAlexWikidataFDO

Authors Michele Garraffa, Lei Shang, Vincent T'kindt, F. 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)

Recommendations

• Merging nodes in search trees: an exact exponential algorithm for the single machine total tardiness scheduling problem
• An Exact Algorithm for the Single-Machine Earliness–Tardiness Scheduling Problem
• An exact algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times
• A hybrid algorithm for the single-machine total tardiness problem
• A branch-and-bound algorithm for the single machine earliness and tardiness scheduling problem
• A branch and bound algorithm to minimize total weighted tardiness on a single processor
• The single machine earliness and tardiness scheduling problem: lower bounds and a branch-and-bound algorithm
• Single machine total tardiness maximization problems: complexity and algorithms
• A branch-and-bound algorithm to minimise the sum of maximum earliness and tardiness in the single machine
• A faster fully polynomial approximation scheme for the single-machine total tardiness problem

Cites work

• scientific article; zbMATH DE number 3550186 (Why is no real title available?)
• scientific article; zbMATH DE number 1953201 (Why is no real title available?)
• A decomposition algorithm for the single machine total tardiness problem
• A new decomposition approach for the single machine total tardiness scheduling problem
• Algorithmic paradoxes of the single-machine total tardiness problem
• Decomposition of the single machine total tardiness problem
• Exact exponential algorithms.
• Expected Computation Time for Hamiltonian Path problem
• Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction.
• Merging nodes in search trees: an exact exponential algorithm for the single machine total tardiness scheduling problem
• Minimizing Total Tardiness on One Machine is NP-Hard
• On an extension of the Sort \& Search method with application to scheduling theory
• On exact algorithms for treewidth
• One-Machine Sequencing to Minimize Certain Functions of Job Tardiness
• Revisiting branch and bound search strategies for machine scheduling problems
• Scheduling and fixed-parameter tractability
• The single-machine total tardiness scheduling problem: review and extensions

Cited in

(6)

• Moderate exponential-time algorithms for scheduling problems
• 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
• Deep learning-driven scheduling algorithm for a single machine problem minimizing the total tardiness
• Merging nodes in search trees: an exact exponential algorithm for the single machine total tardiness scheduling problem
• Exponential time algorithms for just-in-time scheduling problems with common due date and symmetric weights

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1786599)