Optimal interval scheduling with a resource constraint

DOI10.1016/J.COR.2014.06.002MaRDI QIDQ337149zbMATHOpenAlexFDO

Authors Enrico Angelelli, Nicola Bianchessi, 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

heuristicscomplexityresource allocationschedulingbranch and pricefixed job scheduling

Mathematics Subject Classification ID

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

Recommendations

• On the complexity of interval scheduling with a resource constraint
• Resource allocation with time intervals
• The \(k\)-track assignment problem
• Resource constrained scheduling on multiple machines
• Interval scheduling on identical machines

Cites work

• scientific article; zbMATH DE number 4043214 (Why is no real title available?)
• scientific article; zbMATH DE number 44282 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2086936 (Why is no real title available?)
• 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
• An Optimal Solution for the Channel-Assignment Problem
• An analysis of approximations for maximizing submodular set functions—I
• Approximation algorithms for the unsplittable flow problem
• Branch-and-price: Column generation for solving huge integer programs
• Column Generation
• Column generation based primal heuristics
• 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
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Minimal Resources for Fixed and Variable Job Schedules
• On the complexity of interval scheduling with a resource constraint
• On the computational complexity of (maximum) class scheduling
• Optimal solutions for routing problems with profits
• Resource allocation with time intervals
• Scheduling jobs with fixed start and end times
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The Temporal Knapsack Problem and Its Solution
• Truthful Mechanisms via Greedy Iterative Packing

Cited in

(23)

• Visiting infinitely often the unit interval while minimizing the idle time of high priority segments
• 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
• Multithread interval scheduling with flexible machine availabilities: complexity and efficient algorithms
• Minimizing the number of machines with limited workload capacity for scheduling jobs with interval constraints
• Strategy-proof mechanism for online resource allocation in cloud and edge collaboration
• Scheduling resources for executing a partial set of jobs
• Mobility offer allocations in corporate settings
• A Lagrangian relaxation algorithm for stochastic fixed interval scheduling problem with non-identical machines and job classes
• Optimal scheduling of slots with season segmentation
• Primal Heuristics for Branch and Price: The Assets of Diving Methods
• Optimal behavior and concurrent variable interval schedules
• Distributionally robust fixed interval scheduling on parallel identical machines under uncertain finishing times
• Interval scheduling with economies of scale
• Flow-based formulations for operational fixed interval scheduling problems with random delays
• Fixed interval scheduling with third‐party machines
• scientific article; zbMATH DE number 7650890 (Why is no real title available?)
• On the complexity of interval scheduling with a resource constraint
• scientific article; zbMATH DE number 3894816 (Why is no real title available?)
• A branch-and-price algorithm for the temporal bin packing problem
• A combinatorial flow-based formulation for temporal bin packing problems
• Scheduling with constrained processor allocation for interval orders
• Resource allocation with time intervals
• On the parameterized complexity of interval scheduling with eligible machine sets

This page was built for publication: Optimal 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 Q337149)