Mutual exclusion scheduling

DOI10.1016/0304-3975(96)00031-XzbMath0877.68007MaRDI QIDQ1365931

Edward G. jun. Coffman, Brenda S. Baker

Publication date: 10 September 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

mutual exclusionmutual exclusion scheduling

Mathematics Subject Classification ID

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

Related Items (50)

Path cover with minimum nontrivial paths and its application in two-machine flow-shop scheduling with a conflict graph ⋮ Scheduling: agreement graph vs resource constraints ⋮ On partitioning interval graphs into proper interval subgraphs and related problems ⋮ Scheduling with conflicts: Online and offline algorithms ⋮ Approximation algorithms for two parallel dedicated machine scheduling with conflict constraints ⋮ Equitable colorings of Cartesian products of square of cycles and paths with complete bipartite graphs ⋮ Branch-and-cut for linear programs with overlapping SOS1 constraints ⋮ Scheduling with complete multipartite incompatibility graph on parallel machines: complexity and algorithms ⋮ Models and complexity of multibin packing problems ⋮ Equitable colorings of Kronecker products of graphs ⋮ New results in two identical machines scheduling with agreement graphs ⋮ Weighted and locally bounded list-colorings in split graphs, cographs, and partial \(k\)-trees ⋮ Complexity and approximation algorithms for two parallel dedicated machine scheduling with conflict constraints ⋮ Window-based greedy contention management for transactional memory: theory and practice ⋮ Structural parameterizations for equitable coloring: complexity, FPT algorithms, and kernelization ⋮ The mutual exclusion scheduling problem for permutation and comparability graphs. ⋮ Scheduling with machine conflicts ⋮ A competitive analysis for balanced transactional memory workloads ⋮ Scheduling on uniform machines with a conflict graph: complexity and resolution ⋮ Flow shop scheduling problem with conflict graphs ⋮ Restricted assignment scheduling with resource constraints ⋮ Probabilistic analysis for scheduling with conflicts ⋮ Bounded max-colorings of graphs ⋮ Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem ⋮ Partitioning a weighted partial order ⋮ The equitable vertex arboricity of complete tripartite graphs ⋮ Approximation algorithms for time constrained scheduling ⋮ Mutual exclusion scheduling with interval graphs or related classes. II ⋮ Scheduling jobs on identical machines with agreement graph ⋮ On the equitable vertex arboricity of graphs ⋮ Heuristics and lower bounds for the bin packing problem with conflicts ⋮ Scheduling identical jobs on uniform machines with a conflict graph ⋮ On the equitable vertex arboricity of complete tripartite graphs ⋮ Equitable list coloring of planar graphs without 4- and 6-cycles ⋮ Mutual exclusion scheduling with interval graphs or related classes. I ⋮ Locally boundedk-colorings of trees ⋮ An approximation scheme for bin packing with conflicts ⋮ Structural parameterizations of budgeted graph coloring ⋮ Equitable coloring of Kronecker products of complete multipartite graphs and complete graphs ⋮ Structural parameterizations of budgeted graph coloring ⋮ Equitable defective coloring of sparse planar graphs ⋮ Equitable colorings of Cartesian products of graphs ⋮ Asynchronous Coordination Under Preferences and Constraints ⋮ Graph coloring with cardinality constraints on the neighborhoods ⋮ Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review ⋮ Two-machine open shop problem with agreement graph ⋮ Clique partitioning with value-monotone submodular cost ⋮ Open shop scheduling problems with conflict graphs ⋮ Equitable colorings of bounded treewidth graphs ⋮ On equitable \(\Delta\)-coloring of graphs with low average degree

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Restrictions of graph partition problems. I
• A better performance guarantee for approximate graph coloring
• Every planar map is four colorable. I: Discharging
• Scheduling with incompatible jobs
• A spectral technique for coloring random 3-colorable graphs (preliminary version)
• Approximation algorithms for NP-complete problems on planar graphs
• On the hardness of approximating minimization problems
• An upper bound for the chromatic number of a graph and its application to timetabling problems

This page was built for publication: Mutual exclusion scheduling