A BB\&R algorithm for minimizing total tardiness on a single machine with sequence dependent setup times

DOI10.1007/S10898-011-9793-ZzbMath1258.90043OpenAlexW2048656230MaRDI QIDQ1928272

Edward C. Sewell, Gio K. Kao, Jason J. Sauppe, David R. Morrison, Jacobson, Sheldon H.

Publication date: 3 January 2013

Published in: Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10898-011-9793-z

zbMATH Keywords

dynamic programmingdominance rules

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Deterministic scheduling theory in operations research (90B35)

Related Items (12)

An Improved Branch-and-Bound Algorithm for the One-Machine Scheduling Problem with Delayed Precedence Constraints ⋮ A Wide Branching Strategy for the Graph Coloring Problem ⋮ Results for the close-enough traveling salesman problem with a branch-and-bound algorithm ⋮ Domain reduction techniques for global NLP and MINLP optimization ⋮ New dominance rules and exploration strategies for the \(1|r _{i}|\sum U _{i }\) scheduling problem ⋮ ILS heuristics for the single-machine scheduling problem with sequence-dependent family setup times to minimize total tardiness ⋮ Branch-and-bound algorithms: a survey of recent advances in searching, branching, and pruning ⋮ Comparison of the number of nodes explored by cyclic best first search with depth contour and best first search ⋮ Weighted network search games with multiple hidden objects and multiple search teams ⋮ Solving the Pricing Problem in a Branch-and-Price Algorithm for Graph Coloring Using Zero-Suppressed Binary Decision Diagrams ⋮ A Branch, Bound, and Remember Algorithm for the Simple Assembly Line Balancing Problem ⋮ An application of the branch, bound, and remember algorithm to a new simple assembly line balancing dataset

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A dynamic program with fathoming and dynamic upper bounds for the assembly line balancing problem
• A branch-and-bound procedure to minimize total tardiness on one machine with arbitrary release dates
• A branch, bound, and remember algorithm for the \(1|r _{i }|\sum t _{i }\) scheduling problem
• A branch and bound algorithm of the single machine schedule with sequence dependent setup times for minimizing total tardiness
• An ant colony optimization for single-machine tardiness scheduling with sequence-dependent setups
• A branch-and-bound algorithm of the single machine schedule with sequence-dependent setup times for minimizing maximum tardiness
• A new tabu search procedure for an audit-scheduling problem
• Scheduling in a sequence dependent setup environment with genetic search
• Solution of the single machine total tardiness problem
• A decomposition algorithm for the single machine total tardiness problem
• On decomposition of the total tardiness problem
• Algorithms for single machine total tardiness scheduling with sequence dependent setups
• A survey of scheduling problems with setup times or costs
• Minimizing Total Tardiness on One Machine is NP-Hard
• Branch-and-Bound Strategies for Dynamic Programming
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Comparing an ACO algorithm with other heuristics for the single machine scheduling problem with sequence-dependent setup times
• Using metaheuristic compromise programming for the solution of multiple-objective scheduling problems
• Some dominance properties for single-machine tardiness problems with sequence-dependent setup

This page was built for publication: A BB\&R algorithm for minimizing total tardiness on a single machine with sequence dependent setup times