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

DOI10.1016/J.DAM.2024.06.031zbMATH Open1547.90076MaRDI QIDQ6611071FDOQ6611071

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

Publication date: 26 September 2024

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

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

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)

Cites Work

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

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)