Tight complexity analysis of the relocation problem with arbitrary release dates

DOI10.1016/J.TCS.2011.04.034MaRDI QIDQ638514zbMATH OpenOpenAlexFDO

Authors B. M. T. Lin, Hsiao-Lan Huang, Sergey Sevastyanov

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

makespanNP-hardnessresource constraintsrelease datesrelocation problemmulti-parametric dynamic programming

Mathematics Subject Classification ID

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

Recommendations

• Some results of the relocation problems with processing times and deadlines
• scientific article; zbMATH DE number 1264427
• Minimizing the weighted number of tardy jobs and maximum tardiness in relocation problem with due date constraints
• Minimizing the total weighted completion time in the relocation problem
• Relocation scheduling subject to fixed processing sequences

Cites work

• scientific article; zbMATH DE number 4095196 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A fast feasibility test for relocation problems
• An exact algorithm for the resource-constrained project scheduling problem based on a new mathematical formulation
• Johnson's rule, composite jobs and the relocation problem
• Minimizing the total weighted completion time in the relocation problem
• On relocation problems with multiple identical working crews
• Optimal two- and three-stage production schedules with set-up time included
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Planning and Scheduling in Manufacturing and Services
• 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
• Scheduling subject to resource constraints: Classification and complexity

Cited in

(3)

• Parametrized relocation of low-mobility resources
• Minimizing the weighted number of tardy jobs and maximum tardiness in relocation problem with due date constraints
• Minimizing the total weighted completion time in the relocation problem

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

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