On the approximability of an interval scheduling problem
From MaRDI portal
Publication:1806343
DOI<link itemprop=identifier href="https://doi.org/10.1002/(SICI)1099-1425(199909/10)2:5<215::AID-JOS27>3.0.CO;2-Y" /><215::AID-JOS27>3.0.CO;2-Y 10.1002/(SICI)1099-1425(199909/10)2:5<215::AID-JOS27>3.0.CO;2-YzbMath0938.90034MaRDI QIDQ1806343
Publication date: 1 November 1999
Published in: Journal of Scheduling (Search for Journal in Brave)
Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)
Related Items (35)
Improved algorithms for resource allocation under varying capacity ⋮ Working time constraints in operational fixed job scheduling ⋮ Online real-time preemptive scheduling of jobs with deadlines on multiple machines ⋮ A fixed job scheduling problem with machine-dependent job weights ⋮ Heuristics for the time dependent team orienteering problem: application to tourist route planning ⋮ Fixed interval scheduling: models, applications, computational complexity and algorithms ⋮ Inverse interval scheduling via reduction on a single machine ⋮ Primal-dual analysis for online interval scheduling problems ⋮ Online selection of intervals and \(t\)-intervals ⋮ Interval scheduling and colorful independent sets ⋮ Winner determination in geometrical combinatorial auctions ⋮ Improving fleet utilization for carriers by interval scheduling ⋮ Breaking 1 - 1/e Barrier for Nonpreemptive Throughput Maximization ⋮ Complex-demand scheduling problem with application in smart grid ⋮ The Maximum Equality-Free String Factorization Problem: Gaps vs. No Gaps ⋮ Bicriteria scheduling for contiguous and non contiguous parallel tasks ⋮ Bandwidth allocation in cellular networks with multiple interferences ⋮ AFSCN scheduling: how the problem and solution have evolved ⋮ Grasp and delivery for moving objects on broken lines ⋮ Runway sequencing with holding patterns ⋮ Approximation algorithms for variable voltage processors: min energy, max throughput and online heuristics ⋮ DECOMPOSITION ALGORITHMS FOR THE INTERVAL SCHEDULING PROBLEM ⋮ On the complexity of the independent set problem in triangle graphs ⋮ Balanced splitting on weighted intervals ⋮ Single-machine scheduling with release times, deadlines, setup times, and rejection ⋮ Dynamic algorithms for multimachine interval scheduling through analysis of idle intervals ⋮ The temporal explorer who returns to the base ⋮ Throughput scheduling with equal additive laxity ⋮ Throughput scheduling with equal additive laxity ⋮ Scheduling with a minimum number of machines ⋮ Approximating Interval Selection on Unrelated Machines with Unit-Length Intervals and Cores ⋮ Approximation Algorithms for Variable Voltage Processors: Min Energy, Max Throughput and Online Heuristics ⋮ Approximation algorithms for time-dependent orienteering. ⋮ Interval scheduling with economies of scale ⋮ Primal-dual approximation algorithms for a packing-covering pair of problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the complexity of scheduling tasks with discrete starting times
- The assembly of printed circuit boards: A case with multiple machines and multiple board types
- Note on scheduling intervals on-line
- Complexity results for scheduling tasks with discrete starting times
- When Is the Classroom Assignment Problem Hard?
- Approximation Algorithms for Fixed Job Schedule Problems
- Exact and Approximation Algorithms for the Tactical Fixed Interval Scheduling Problem
This page was built for publication: On the approximability of an interval scheduling problem
