A beam search heuristic for scheduling a single machine with release dates and sequence dependent setup times to minimize the makespan

DOI10.1016/j.cor.2016.04.009zbMath1349.90405OpenAlexW2320442349MaRDI QIDQ342431

Jairo R. Montoya-Torres, Mario C. Vélez-Gallego, Jairo Maya

Publication date: 17 November 2016

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2016.04.009

zbMATH Keywords

beam searchmakespanrelease datessingle machine schedulingsequence-dependent setup times

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items

Meta-heuristic solution with considering setup time for multi-skilled project scheduling problem, Job sequencing with one common and multiple secondary resources: an A*/beam search based anytime algorithm

Cites Work

• Unnamed Item
• The third comprehensive survey on scheduling problems with setup times/costs
• On solving the assembly line worker assignment and balancing problem via beam search
• A beam search algorithm for the circular packing problem
• Coupling genetic local search and recovering beam search algorithms for minimizing the total completion time in the single machine scheduling problem subject to release dates
• Beam-ACO for the travelling salesman problem with time windows
• A survey of scheduling problems with setup times or costs
• Beam search algorithms for the single machine total weighted tardiness scheduling problem with sequence-dependent setups
• A recovering beam search algorithm for the single machine just-in-time scheduling problem
• Scheduling tasks with sequence-dependent processing times
• Rolling horizon algorithms for a single-machine dynamic scheduling problem with sequence-dependent setup times
• Scheduling with shutdowns and sequence dependent set-up times
• Survey of scheduling research involving setup times
• Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem
• Scheduling