Multithread interval scheduling with flexible machine availabilities: complexity and efficient algorithms

DOI10.1016/J.DAM.2024.06.031MaRDI QIDQ6611071zbMATH OpenFDO

Authors Tabea Brandt, Christina Büsing, Tobias Mömke

Publication date 26 September 2024

Published in Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

algorithmscomplexityinterval scheduling

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)

Recommendations

• Interval scheduling on identical machines
• A fully polynomial time approximation scheme for makespan minimization problems on two machines with a fixed non-availability interval
• Interval selection with machine-dependent intervals
• Interval scheduling: A survey
• Bi-criteria scheduling on multiple machines subject to machine availability constraints

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 2079419 (Why is no real title available?)
• A \((5/3+\varepsilon)\)-approximation for unsplittable flow on a path: placing small tasks into boxes
• A constant factor approximation algorithm for the storage allocation problem
• An optimal greedy heuristic to color interval graphs
• Fixed interval scheduling with third‐party machines
• Fixed interval scheduling: models, applications, computational complexity and algorithms
• Flexible resource allocation to interval jobs
• Integrated Production and Outbound Distribution Scheduling: Review and Extensions
• Interval scheduling: A survey
• Introduction to algorithms
• License class design: Complexity and algorithms
• Minimizing total busy time in parallel scheduling with application to optical networks
• On the Complexity of Timetable and Multicommodity Flow Problems
• On the \(k\)-coloring of intervals
• On the complexity of interval scheduling with a resource constraint
• Online interval scheduling with a bounded number of failures
• Online optimization of busy time on parallel machines
• Optimal interval scheduling with a resource constraint
• Optimizing bandwidth allocation in elastic optical networks with application to scheduling
• Optimizing busy time on parallel machines
• Precoloring extension on unit interval graphs
• Precoloring extension. I: Interval graphs
• Profit maximization in flex-grid all-optical networks
• Resource allocation with time intervals
• The Complexity of Coloring Circular Arcs and Chords
• The k-track assignment problem
• The personnel task scheduling problem

This page was built for publication: Multithread interval scheduling with flexible machine availabilities: complexity and efficient algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6611071)