Approximating Interval Selection on Unrelated Machines with Unit-Length Intervals and Cores

DOI10.1007/978-3-319-45587-7_30zbMath1445.90031OpenAlexW2511121390MaRDI QIDQ2835690

Kateřina Böhmová, Matúš Mihalák, Enrico Kravina

Publication date: 30 November 2016

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-45587-7_30

zbMATH Keywords

computational complexityinterval selectionapproximation algorithmsfixed-interval scheduling

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Cites Work

• Fixed interval scheduling: models, applications, computational complexity and algorithms
• Maximizing weighted number of just-in-time jobs on unrelated parallel machines
• Scheduling jobs with fixed start and end times
• On the complexity of scheduling tasks with discrete starting times
• On the approximability of an interval scheduling problem
• Interval scheduling on identical machines
• Interval Selection with Machine-Dependent Intervals
• Complexity results for scheduling tasks with discrete starting times
• Interval scheduling: A survey
• Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems

This page was built for publication: Approximating Interval Selection on Unrelated Machines with Unit-Length Intervals and Cores