Single machine scheduling with resource constraints: Equivalence to two-machine flow-shop scheduling for regular objectives
Sergey Kovalev, Isabelle Chalamon, Audrey Bécuwe
Abstract
A number of results have been reported in the literature for a single machine job scheduling problem with resource constraints. We demonstrate that many of these results and some new results follow from an equivalence of this problem and the classical two-machine flow-shop scheduling problem. We further refine computational complexity of the problem with resource constraints by presenting new NP-hardness proofs.
Topics & Concepts
Flow shop schedulingComputer scienceJob shop schedulingScheduling (production processes)Equivalence (formal languages)Fair-share schedulingTwo-level schedulingMathematical proofRate-monotonic schedulingSingle-machine schedulingMathematical optimizationDynamic priority schedulingOperations researchDistributed computingMathematicsScheduleDiscrete mathematicsOperating systemGeometryScheduling and Optimization AlgorithmsOptimization and Search ProblemsOptimization and Packing Problems