Approximation of the parallel machine scheduling problem with additional unit resources

DOI10.1016/J.DAM.2016.07.003MaRDI QIDQ323055zbMATH OpenOpenAlexFDO

Authors Emmanuel Hebrard, Marie-José Huguet, Nicolas Jozefowiez, Adrien Maillard, Cédric Pralet, Gérard Verfaillie

Publication date 7 October 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2016.07.003

zbMATH Keywords

approximationschedulingadditional resources

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25)

Recommendations

• An approximation algorithm for identical parallel machine scheduling with resource dependent processing times
• An improved algorithm for parallel machine scheduling under additional resource constraints
• Approximation and Online Algorithms
• Unrelated Parallel Machine Scheduling with Resource Dependent Processing Times
• Approximation algorithms for parallel machine scheduling with speed-up resources

Cites work

• Parallel machine scheduling with additional resources: notation, classification, models and solution methods
• Scheduling jobs on identical machines with agreement graph
• Scheduling jobs with time-resource tradeoff via nonlinear programming
• Scheduling problems for parallel dedicated machines under multiple resource constraints.
• Scheduling subject to resource constraints: Classification and complexity
• Scheduling with conflicts: Online and offline algorithms
• `` Strong NP-Completeness Results

Cited in

(6)

• A PTAS for a resource scheduling problem with arbitrary number of parallel machines
• Models and matheuristics for the unrelated parallel machine scheduling problem with additional resources
• An improved algorithm for parallel machine scheduling under additional resource constraints
• An FPTAS for scheduling with resource constraints
• Generalizing Horn's conditions for preemptive scheduling on identical parallel machines via network flow techniques
• Parallel Machine Scheduling: Impact of Adding Extra Machines

This page was built for publication: Approximation of the parallel machine scheduling problem with additional unit resources

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