On the complexity of interval scheduling with a resource constraint

DOI10.1016/J.TCS.2011.03.025zbMATH Open1234.90005OpenAlexW1982134276MaRDI QIDQ551193FDOQ551193

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

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

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)

Cites Work

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

Cited In (13)

• Strategy-proof mechanism for online resource allocation in cloud and edge collaboration
• Title not available (Why is that?)
• Scheduling the two-machine open shop problem under resource constraints for setting the jobs
• Title not available (Why is that?)
• Multithread interval scheduling with flexible machine availabilities: complexity and efficient algorithms
• A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack
• 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
• Title not available (Why is that?)
• 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)