An Improved Branch-and-Bound Algorithm for the One-Machine Scheduling Problem with Delayed Precedence Constraints

DOI10.1287/ijoc.2020.0988zbMath1492.90062MaRDI QIDQ5085478

Jason J. Sauppe, Jacobson, Sheldon H., Wenda Zhang

Publication date: 27 June 2022

Published in: INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/ijoc.2020.0988

zbMATH Keywords

combinatorial optimization; branch-and-bound; one-machine scheduling

Mathematics Subject Classification ID

90C57: Polyhedral combinatorics, branch-and-bound, branch-and-cut

90B35: Deterministic scheduling theory in operations research

90C59: Approximation methods and heuristics in mathematical programming

90C27: Combinatorial optimization

Related Items

Results for the close-enough traveling salesman problem with a branch-and-bound algorithm

Uses Software

• GitHub

Cites Work

• Unnamed Item
• A branch, bound, and remember algorithm for the \(1|r _{i }|\sum t _{i }\) scheduling problem
• Hybrid decomposition heuristics for solving large-scale scheduling problems in semiconductor wafer fabrication
• Jackson's semi-preemptive scheduling on a single machine
• The one-machine sequencing problem
• Constraint-based scheduling: Applying constraint programming to scheduling problems.
• A BB\&R algorithm for minimizing total tardiness on a single machine with sequence dependent setup times
• An application of the branch, bound, and remember algorithm to a new simple assembly line balancing dataset
• Branch-and-bound algorithms for solving hard instances of the one-machine sequencing problem
• 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
• The Shifting Bottleneck Procedure for Job Shop Scheduling
• Technical Note—Analysis of a Heuristic for One Machine Sequencing with Release Dates and Delivery Times
• On Scheduling with Ready Times and Due Dates to Minimize Maximum Lateness
• Minimizing maximum lateness on one machine: computational experience and some applications
• Sequencing with due-dates and early start times to minimize maximum tardiness
• Cyclic best first search: Using contours to guide branch‐and‐bound algorithms
• A modified shifting bottleneck procedure for job-shop scheduling
• The One-Machine Problem with Delayed Precedence Constraints and its Use in Job Shop Scheduling
• An efficient ILP formulation for the single machine scheduling problem
• Mixed Integer Programming: Analyzing 12 Years of Progress