Approximation algorithms for time constrained scheduling

DOI10.1006/inco.1996.2616zbMath0866.68012MaRDI QIDQ676776

Klaus Jansen, Sabine R. Öhring

Publication date: 6 July 1997

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/42dde019ed65474bf5d5ddc49d00b44b9ffefb77

zbMATH Keywords

time constrained scheduling problem

Mathematics Subject Classification ID

68W10: Parallel algorithms in computer science

68M20: Performance evaluation, queueing, and scheduling in the context of computer systems

Related Items

Online variable-sized bin packing with conflicts, Paths, trees and matchings under disjunctive constraints, Two-dimensional packing with conflicts, New lower bounds for bin packing problems with conflicts, The min-conflict packing problem, Tree-decomposition based heuristics for the two-dimensional bin packing problem with conflicts, Heuristics and lower bounds for the bin packing problem with conflicts, Approximation of a batch consolidation problem, Working time constraints in operational fixed job scheduling

Cites Work

• A simple proof of the inequality \(\text{FFD}(L)\leq {11 \over 9} \text{OPT}(L)+1\), \(\forall L\) for the FFD bin-packing algorithm
• Precoloring extension. I: Interval graphs
• Resource constrained scheduling as generalized bin packing
• Mutual exclusion scheduling
• Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
• Precoloring Extension III: Classes of Perfect Graphs
• On the hardness of approximating minimization problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item