Tight complexity analysis of the relocation problem with arbitrary release dates

DOI10.1016/j.tcs.2011.04.034zbMath1230.90100MaRDI QIDQ638514

Bertrand M. T. Lin, Hsiao-Lan Huang, Sergey Sevast'janov

Publication date: 12 September 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.04.034

zbMATH Keywords

makespan; release dates; NP-hardness; resource constraints; relocation problem; multi-parametric dynamic programming

Mathematics Subject Classification ID

90C60: Abstract computational complexity for mathematical programming problems

90B35: Deterministic scheduling theory in operations research

90C39: Dynamic programming

Related Items

Minimizing the total weighted completion time in the relocation problem

Cites Work

• Unnamed Item
• Unnamed Item
• On relocation problems with multiple identical working crews
• Minimizing the total weighted completion time in the relocation problem
• Johnson's rule, composite jobs and the relocation problem
• Scheduling subject to resource constraints: Classification and complexity
• A fast feasibility test for relocation problems
• Polynomial algorithms for single machine scheduling problems with financial constraints
• Resource-constrained project scheduling: A survey of recent developments.
• Resource-constrained project scheduling: Notation, classification, models, and methods
• An Exact Algorithm for the Resource-Constrained Project Scheduling Problem Based on a New Mathematical Formulation
• Optimal two- and three-stage production schedules with setup times included
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Planning and Scheduling in Manufacturing and Services