Scheduling with conflicts: Online and offline algorithms

DOI10.1007/s10951-008-0089-1zbMath1170.90390MaRDI QIDQ842559

Dana Ron, Magnús M. Halldórsson, Guy Even, Lotem Kaplan

Publication date: 25 September 2009

Published in: Journal of Scheduling (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10951-008-0089-1

zbMATH Keywords

online algorithms; approximation algorithms; mutual exclusion scheduling; scheduling with conflicts

Mathematics Subject Classification ID

90B35: Deterministic scheduling theory in operations research

90B36: Stochastic scheduling theory in operations research

Cites Work

• Restrictions of graph partition problems. I
• Bounded vertex colorings of graphs
• A note on the decomposition of graphs into isomorphic matchings
• Zero knowledge and the chromatic number
• Scheduling multiprocessor tasks -- An overview
• The hardness of approximation: Gap location
• Scheduling with incompatible jobs
• Mutual exclusion scheduling
• The mutual exclusion scheduling problem for permutation and comparability graphs.
• Multicoloring trees.
• An approximation scheme for bin packing with conflicts
• Scheduling with conflicts on bipartite and interval graphs
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Scheduling File Transfers
• Bounds for Multiprocessor Scheduling with Resource Constraints
• Complexity Results for Multiprocessor Scheduling under Resource Constraints
• Sum Multicoloring of Graphs
• The χt-coloring problem
• OPTVersusLOADin Dynamic Storage Allocation
• Polynomial time approximation schemes for general multiprocessor job shop scheduling
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Scheduling Parallel Machines On-Line
• On Bin Packing with Conflicts
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item