Scheduling with conflicts: Online and offline algorithms

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

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

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 algorithmsapproximation algorithmsmutual exclusion schedulingscheduling with conflicts

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Stochastic scheduling theory in operations research (90B36)

Related Items (35)

Path cover with minimum nontrivial paths and its application in two-machine flow-shop scheduling with a conflict graph ⋮ Fair Packing of Independent Sets ⋮ Scheduling: agreement graph vs resource constraints ⋮ Approximation of the parallel machine scheduling problem with additional unit resources ⋮ Approximation algorithms for two parallel dedicated machine scheduling with conflict constraints ⋮ An exact algorithm for parallel machine scheduling with conflicts ⋮ Makespan minimization on unrelated parallel machines with a few bags ⋮ A stand-alone branch-and-price algorithm for identical parallel machine scheduling with conflicts ⋮ Parameterized complexity of conflict-free matchings and paths ⋮ Multiprofessor scheduling ⋮ Scheduling of unit-length jobs with cubic incompatibility graphs on three uniform machines ⋮ Fair allocation algorithms for indivisible items under structured conflict constraints ⋮ New results in two identical machines scheduling with agreement graphs ⋮ Complexity and approximation algorithms for two parallel dedicated machine scheduling with conflict constraints ⋮ Window-based greedy contention management for transactional memory: theory and practice ⋮ On minimizing dataset transfer time in an acyclic network with four servers ⋮ A competitive analysis for balanced transactional memory workloads ⋮ Scheduling on uniform machines with a conflict graph: complexity and resolution ⋮ An improved algorithm for parallel machine scheduling under additional resource constraints ⋮ Flow shop scheduling problem with conflict graphs ⋮ Fair allocation of indivisible items with conflict graphs ⋮ Restricted assignment scheduling with resource constraints ⋮ Non-clairvoyant scheduling with conflicts for unit-size jobs ⋮ Exploring the Kernelization Borders for Hitting Cycles ⋮ Scheduling jobs on identical machines with agreement graph ⋮ Bounds on contention management algorithms ⋮ Approximation of knapsack problems with conflict and forcing graphs ⋮ Scheduling identical jobs on uniform machines with a conflict graph ⋮ Unnamed Item ⋮ Conflict free version of covering problems on graphs: classical and parameterized ⋮ Parameterized complexity of conflict-free set cover ⋮ A hybrid metaheuristic for the two-dimensional strip packing problem ⋮ Asynchronous Coordination Under Preferences and Constraints ⋮ On minimizing the makespan when some jobs cannot be assigned on the same machine ⋮ Open shop scheduling problems with conflict graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: Scheduling with conflicts: Online and offline algorithms