Approximation algorithms for time constrained scheduling

DOI10.1006/INCO.1996.2616zbMATH Open0866.68012OpenAlexW2088776663MaRDI QIDQ676776FDOQ676776

Authors: 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

Recommendations

• Approximation Algorithms for Fixed Job Schedule Problems
• Scheduling of incompatible jobs on unrelated machines
• scientific article; zbMATH DE number 613300

zbMATH Keywords

time constrained scheduling problem

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Parallel algorithms in computer science (68W10)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the hardness of approximating minimization problems
• Resource constrained scheduling as generalized bin packing
• Mutual exclusion scheduling
• Title not available (Why is that?)
• Precoloring extension. I: Interval graphs
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Precoloring Extension III: Classes of Perfect Graphs
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (39)

• A Bi-Criteria FPTAS for Scheduling with Memory Constraints on Graphs with Bounded Tree-Width
• Online results for black and white bin packing
• An APTAS for bin packing with clique-graph conflicts
• Exact solution algorithms for the maximum flow problem with additional conflict constraints
• Working time constraints in operational fixed job scheduling
• Robust Multiperiod Vehicle Routing Under Customer Order Uncertainty
• Linear approximation of execution-time constraints
• New lower bounds for bin packing problems with conflicts
• Online variable-sized bin packing with conflicts
• Title not available (Why is that?)
• Approximation algorithms for scheduling with reservations
• The maximum flow problem with disjunctive constraints
• Heuristics and lower bounds for the bin packing problem with conflicts
• Scheduling Jobs with Temporal Distance Constraints
• Minimum cost flow problem with conflicts
• An exact algorithm for the bi-objective timing problem
• Two-dimensional packing with conflicts
• Heuristics and matheuristics for a real‐life machine reassignment problem
• Title not available (Why is that?)
• An approximation scheme for bin packing with conflicts
• Algorithms for Flows over Time with Scheduling Costs
• Robustly assigning unstable items
• On the benchmark instances for the bin packing problem with conflicts
• A Multi-start Tabu Search Based Algorithm for Solving the Warehousing Problem with Conflict
• The min-conflict packing problem
• Tree-decomposition based heuristics for the two-dimensional bin packing problem with conflicts
• Scheduling real-time computations with separation constraints
• Tight bounds for budgeted maximum weight independent set in bipartite and perfect graphs
• Approximating Bin Packing with Conflict Graphs via Maximization Techniques
• Algorithms for Scheduling Imprecise Computations with Timing Constraints
• Bin packing with directed stackability conflicts
• Paths, trees and matchings under disjunctive constraints
• Approximation of a batch consolidation problem
• Just-in-time logistics for far-distant suppliers: scheduling truck departures from an intermediate cross-docking terminal
• Title not available (Why is that?)
• A large neighborhood search algorithm and lower bounds for the variable-sized bin packing problem with conflicts
• A DSS based on optimizer tools and MTS meta-heuristic for the warehousing problem with conflicts
• Approximate solution of a resource-constrained scheduling problem
• Bin packing with ``largest in bottom constraint: tighter bounds and generalizations

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

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