Approximation algorithms for time constrained scheduling

DOI10.1006/inco.1996.2616zbMath0866.68012OpenAlexW2088776663MaRDI 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

"Parallel+algorithms+in+computer+science"&go=Go Parallel algorithms in computer science (68W10) "Performance+evaluation%2C+queueing%2C+and+scheduling+in+the+context+of+computer+systems"&go=Go Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (25)

Working time constraints in operational fixed job scheduling ⋮ An APTAS for bin packing with clique-graph conflicts ⋮ The maximum flow problem with disjunctive constraints ⋮ Bin packing with ``largest in bottom constraint: tighter bounds and generalizations ⋮ Minimum cost flow problem with conflicts ⋮ A Multi-start Tabu Search Based Algorithm for Solving the Warehousing Problem with Conflict ⋮ A large neighborhood search algorithm and lower bounds for the variable-sized bin packing problem with conflicts ⋮ Online variable-sized bin packing with conflicts ⋮ Just-in-time logistics for far-distant suppliers: scheduling truck departures from an intermediate cross-docking terminal ⋮ A DSS based on optimizer tools and MTS meta-heuristic for the warehousing problem with conflicts ⋮ Paths, trees and matchings under disjunctive constraints ⋮ Two-dimensional packing 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 ⋮ New lower bounds for bin packing problems with conflicts ⋮ Exact solution algorithms for the maximum flow problem with additional conflict constraints ⋮ Robustly assigning unstable items ⋮ An approximation scheme for bin packing with conflicts ⋮ On the benchmark instances for the bin packing problem with conflicts ⋮ Robust Multiperiod Vehicle Routing Under Customer Order Uncertainty ⋮ Approximation of a batch consolidation problem ⋮ Bin packing with directed stackability conflicts ⋮ Heuristics and matheuristics for a real‐life machine reassignment problem ⋮ Online results for black and white bin packing

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

This page was built for publication: Approximation algorithms for time constrained scheduling