A graph coloring approach to scheduling of multiprocessor tasks on dedicated machines with availability constraints

DOI10.1016/j.dam.2009.02.024zbMath1227.05234MaRDI QIDQ967430

Krzysztof Giaro, Marek Kubale, Paweł Obszarski

Publication date: 28 April 2010

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2009.02.024

zbMATH Keywords

multiprocessor scheduling; NP-completeness; hypergraph coloring; dedicated machines

Mathematics Subject Classification ID

05C65: Hypergraphs

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

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

On the complexity of the selective graph coloring problem in some special classes of graphs

Cites Work

• The complexity of scheduling independent two-processor tasks on dedicated processors
• Scheduling multiprocessor tasks -- An overview
• Preemptive versus nonpreemptive scheduling for biprocessor tasks on dedicated processors
• Corrigendum to: ``Scheduling multiprocessor tasks on three dedicated processors
• Preemptive multiprocessor task scheduling with release times and time windows
• Scheduling multiprocessor tasks on parallel processors with limited availability.
• Optimal parallel machines scheduling with availability constraints
• Concurrent Task Systems
• Reducibility among Combinatorial Problems
• Parallel Processing and Applied Mathematics
• Unnamed Item