Tight complexity analysis of the relocation problem with arbitrary release dates

DOI10.1016/J.TCS.2011.04.034zbMath1230.90100OpenAlexW2094901897MaRDI 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

makespanrelease datesNP-hardnessresource constraintsrelocation problemmulti-parametric dynamic programming

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39)

Related Items (1)

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

This page was built for publication: Tight complexity analysis of the relocation problem with arbitrary release dates