Complexity and approximation results for scheduling multiprocessor tasks on a ring.

DOI10.1016/S0166-218X(03)00432-3zbMath1049.90023OpenAlexW2019537610MaRDI QIDQ1417558

Paolo Dell'Olmo, Giuseppe Confessore, Stefano Giordani

Publication date: 5 January 2004

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

Full work available at URL: https://doi.org/10.1016/s0166-218x(03)00432-3

zbMATH Keywords

Complexity analysisMultiprocessor task schedulingAcyclic orientationsApproximation resultsGraph model

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An approximation result for a duo-processor task scheduling problem
• Multiprocessor scheduling with communication delays
• The complexity of scheduling independent two-processor tasks on dedicated processors
• Scheduling multiprocessor tasks on three dedicated processors
• Scheduling multiprocessor tasks -- An overview
• Approximation algorithms for scheduling trees with general communication delays: Special issue on task scheduling problems for parallel and distributed systems
• Some models for scheduling parallel programs with communication delays