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

DOI10.1016/J.TCS.2018.05.040zbMATH Open1407.90153OpenAlexW2805463268WikidataQ115566733 ScholiaQ115566733MaRDI QIDQ1786599FDOQ1786599

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

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

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)

Cites Work

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

Cited In (6)

• Parallel machine scheduling with minimum number of tardy jobs: approximation and exponential algorithms
• Exponential time algorithms for just-in-time scheduling problems with common due date and symmetric weights
• \textit{Branch} \& \textit{memorize} exact algorithms for sequencing problems: efficient embedding of memorization into search trees
• Merging nodes in search trees: an exact exponential algorithm for the single machine total tardiness scheduling problem
• Deep learning-driven scheduling algorithm for a single machine problem minimizing the total tardiness
• Moderate exponential-time algorithms for scheduling problems

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)