On the complexity of interval scheduling with a resource constraint

DOI10.1016/J.TCS.2011.03.025MaRDI QIDQ551193zbMATH OpenOpenAlexFDO

Authors Enrico Angelelli, Carlo Filippi

Publication date 14 July 2011

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

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

zbMATH Keywords

complexityresource allocationschedulingfixed job schedulinginterval availability

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Optimal interval scheduling with a resource constraint
• Interval scheduling on identical machines
• scientific article; zbMATH DE number 3891075
• Scheduling problems for parallel dedicated machines under multiple resource constraints.
• Interval scheduling: A survey

Cites work

• scientific article; zbMATH DE number 3121292 (Why is no real title available?)
• scientific article; zbMATH DE number 4043214 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A logarithmic approximation for unsplittable flow on line graphs
• An Optimal Solution for the Channel-Assignment Problem
• Cost constrained fixed job scheduling.
• Exact and approximation algorithms for the operational fixed interval scheduling problem
• Fixed interval scheduling: models, applications, computational complexity and algorithms
• Games of Boldness, Where the Player Performing the Hardest Task Wins
• Interval scheduling on identical machines
• Interval scheduling: A survey
• Minimal Resources for Fixed and Variable Job Schedules
• On the Computational Complexity of Combinatorial Problems
• On the computational complexity of (maximum) class scheduling
• Resource allocation with time intervals
• Scheduling jobs with fixed start and end times
• The Complexity of Coloring Circular Arcs and Chords

Cited in

(13)

• Strategy-proof mechanism for online resource allocation in cloud and edge collaboration
• scientific article; zbMATH DE number 7650890 (Why is no real title available?)
• Scheduling the two-machine open shop problem under resource constraints for setting the jobs
• scientific article; zbMATH DE number 2086932 (Why is no real title available?)
• A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack
• Multithread interval scheduling with flexible machine availabilities: complexity and efficient algorithms
• Distributionally robust fixed interval scheduling on parallel identical machines under uncertain finishing times
• Flow-based formulations for operational fixed interval scheduling problems with random delays
• Optimal interval scheduling with a resource constraint
• A combinatorial auction mechanism for time-varying multidimensional resource allocation and pricing in fog computing
• scientific article; zbMATH DE number 3894816 (Why is no real title available?)
• A branch-and-price algorithm for the temporal bin packing problem
• A Lagrangian relaxation algorithm for stochastic fixed interval scheduling problem with non-identical machines and job classes

This page was built for publication: On the complexity of interval scheduling with a resource constraint

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