Optimal interval scheduling with a resource constraint

DOI10.1016/j.cor.2014.06.002zbMath1348.90239OpenAlexW1972086438MaRDI QIDQ337149

Nicola Bianchessi, Enrico Angelelli, Carlo Filippi

Publication date: 10 November 2016

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2014.06.002

zbMATH Keywords

complexityheuristicsschedulingresource allocationbranch and pricefixed job scheduling

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Deterministic scheduling theory in operations research (90B35)

Related Items (10)

Distributionally robust fixed interval scheduling on parallel identical machines under uncertain finishing times ⋮ Fixed interval scheduling with third‐party machines ⋮ Integer programming column generation: accelerating branch-and-price using a novel pricing scheme for finding high-quality solutions in set covering, packing, and partitioning problems ⋮ A combinatorial flow-based formulation for temporal bin packing problems ⋮ Mobility offer allocations in corporate settings ⋮ Primal Heuristics for Branch and Price: The Assets of Diving Methods ⋮ Flow-based formulations for operational fixed interval scheduling problems with random delays ⋮ A branch-and-price algorithm for the temporal bin packing problem ⋮ Interval scheduling with economies of scale ⋮ Strategy-proof mechanism for online resource allocation in cloud and edge collaboration

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of interval scheduling with a resource constraint
• Resource allocation with time intervals
• Fixed interval scheduling: models, applications, computational complexity and algorithms
• Approximation algorithms for the unsplittable flow problem
• Scheduling jobs with fixed start and end times
• On the computational complexity of (maximum) class scheduling
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Exact and approximation algorithms for the operational fixed interval scheduling problem
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Optimal solutions for routing problems with profits
• Interval scheduling on identical machines
• Branch-and-Price: Column Generation for Solving Huge Integer Programs
• Column Generation based Primal Heuristics
• Interval scheduling: A survey
• Truthful Mechanisms via Greedy Iterative Packing
• 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
• An analysis of approximations for maximizing submodular set functions—I
• Column Generation
• The Temporal Knapsack Problem and Its Solution
• A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
• A Constant Factor Approximation Algorithm for Unsplittable Flow on Paths
• A logarithmic approximation for unsplittable flow on line graphs
• Theoretical Computer Science

This page was built for publication: Optimal interval scheduling with a resource constraint