On the complexity of interval scheduling with a resource constraint

DOI10.1016/j.tcs.2011.03.025zbMath1234.90005OpenAlexW1982134276MaRDI QIDQ551193

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

complexityschedulingresource allocationfixed 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)

Related Items (7)

Optimal interval scheduling with a resource constraint ⋮ Distributionally robust fixed interval scheduling on parallel identical machines under uncertain finishing times ⋮ A combinatorial auction mechanism for time-varying multidimensional resource allocation and pricing in fog computing ⋮ Scheduling the two-machine open shop problem under resource constraints for setting the jobs ⋮ Flow-based formulations for operational fixed interval scheduling problems with random delays ⋮ A branch-and-price algorithm for the temporal bin packing problem ⋮ Strategy-proof mechanism for online resource allocation in cloud and edge collaboration

Cites Work

• Resource allocation with time intervals
• Fixed interval scheduling: models, applications, computational complexity and algorithms
• Scheduling jobs with fixed start and end times
• On the computational complexity of (maximum) class scheduling
• Exact and approximation algorithms for the operational fixed interval scheduling problem
• Interval scheduling on identical machines
• Interval scheduling: A survey
• An Optimal Solution for the Channel-Assignment Problem
• The Complexity of Coloring Circular Arcs and Chords
• Games of Boldness, Where the Player Performing the Hardest Task Wins
• On the Computational Complexity of Combinatorial Problems
• Minimal Resources for Fixed and Variable Job Schedules
• A logarithmic approximation for unsplittable flow on line graphs
• Theoretical Computer Science
• Unnamed Item
• Unnamed Item
• Unnamed Item

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