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.009MaRDI QIDQ342431zbMATH OpenOpenAlexFDO

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

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 datessequence-dependent setup timessingle machine scheduling

Mathematics Subject Classification ID

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

Recommendations

• A tabu search heuristic for a sequence-dependent and time-dependent scheduling problem on a single machine
• Beam search algorithms for the single machine total weighted tardiness scheduling problem with sequence-dependent setups
• Job shop scheduling with separable sequence-dependent setups
• A branch-and-bound algorithm of the single machine schedule with sequence-dependent setup times for minimizing maximum tardiness
• A multicriteria scheduling with sequence-dependent setup times

Cites work

• A beam search algorithm for the circular packing problem
• A recovering beam search algorithm for the single machine just-in-time scheduling problem
• 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
• Beam-ACO for the travelling salesman problem with time windows
• 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
• scientific article; zbMATH DE number 35511 (Why is no real title available?)
• On solving the assembly line worker assignment and balancing problem via beam search
• Rolling horizon algorithms for a single-machine dynamic scheduling problem with sequence-dependent setup times
• Scheduling tasks with sequence-dependent processing times
• Scheduling with shutdowns and sequence dependent set-up times
• Scheduling. Theory, algorithms, and systems.
• Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem
• Survey of scheduling research involving setup times
• The third comprehensive survey on scheduling problems with setup times/costs

Cited in

(9)

• 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
• Meta-heuristic solution with considering setup time for multi-skilled project scheduling problem
• A hybrid metaheuristic for the prize-collecting single machine scheduling problem with sequence-dependent setup times
• Job sequencing with one common and multiple secondary resources: an A*/beam search based anytime algorithm
• Beam search algorithms for the single machine total weighted tardiness scheduling problem with sequence-dependent setups
• BEAM SEARCH HEURISTICS FOR THE SINGLE MACHINE SCHEDULING PROBLEM WITH LINEAR EARLINESS AND QUADRATIC TARDINESS COSTS
• Exact and heuristic algorithms for minimizing the makespan on a single machine scheduling problem with sequence-dependent setup times and release dates
• A branch-and-price algorithm for unrelated parallel machine scheduling with machine usage costs
• The fourth comprehensive review of scheduling problems with setup times

This page was built for publication: A beam search heuristic for scheduling a single machine with release dates and sequence dependent setup times to minimize the makespan

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