Job shop scheduling with setup times, deadlines and precedence constraints

DOI10.1007/s10951-008-0067-7zbMath1168.90419OpenAlexW2086998347MaRDI QIDQ835609

Egon Balas, Neil Simonetti, Alkis A. Vazacopoulos

Publication date: 28 August 2009

Published in: Journal of Scheduling (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10951-008-0067-7

zbMATH Keywords

dynamic programmingsequence-dependent setup timestraveling salesman problem with time windows shifting bottleneck

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39)

Related Items

A multi-criteria approach for scheduling semiconductor wafer fabrication facilities ⋮ The third comprehensive survey on scheduling problems with setup times/costs ⋮ Scatter search with path relinking for the job shop with time lags and setup times ⋮ A neighborhood for complex job shop scheduling problems with regular objectives ⋮ Depth-first heuristic search for the job shop scheduling problem ⋮ Exact and heuristic dynamic programming algorithms for the traveling salesman problem with flexible time windows ⋮ An exact dynamic programming algorithm for the precedence-constrained class sequencing problem ⋮ A column generation-based heuristic for a rehabilitation patient scheduling and routing problem ⋮ A general variable neighborhood search for the traveling salesman problem with time windows under various objectives ⋮ Solving job shop scheduling with setup times through constraint-based iterative sampling: an experimental analysis ⋮ Optimization of setup times in the furniture industry ⋮ Mathematical model applied to single-track line scheduling problem in Brazilian railways ⋮ A worker constrained flexible job shop scheduling problem with sequence-dependent setup times ⋮ A branch and bound method for the job-shop problem with sequence-dependent setup times ⋮ A survey of scheduling problems with setup times or costs ⋮ Sequencing and scheduling for filling lines in dairy production ⋮ Local search and genetic algorithm for the job shop scheduling problem with sequence dependent setup times ⋮ A competent memetic algorithm for complex scheduling ⋮ Scheduling for multi-robot routing with blocking and enabling constraints

Cites Work

• A branch and bound method for the job-shop problem with sequence-dependent setup times
• The one-machine sequencing problem
• New classes of efficiently solvable generalized traveling salesman problems
• Job shop scheduling with deadlines
• A branch \(\&\) bound method for the general-shop problem with sequence dependent setup-times
• Guided Local Search with Shifting Bottleneck for Job Shop Scheduling
• Linear Time Dynamic-Programming Algorithms for New Classes of Restricted TSPs: A Computational Study
• A Dynamic Programming Approach to Sequencing Problems
• The Shifting Bottleneck Procedure for Job Shop Scheduling
• The One-Machine Problem with Delayed Precedence Constraints and its Use in Job Shop Scheduling