Tree scheduling with communication delays

DOI10.1016/0166-218X(94)90205-4zbMath0799.90062OpenAlexW2030403716MaRDI QIDQ1327224

Philippe Chrétienne

Publication date: 17 November 1994

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

Full work available at URL: https://doi.org/10.1016/0166-218x(94)90205-4

zbMATH Keywords

makespanpolynomial-time algorithminterprocessor communication delaysscheduling a tree-structured task system

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Communication networks in operations research (90B18) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (2)

New complexity results on scheduling with small communication delays ⋮ Scheduling multiprocessor tasks -- An overview

Cites Work

• A polynomial algorithm to optimally schedule tasks on a virtual distributed system under tree-like precedence constraints
• UET scheduling with unit interprocessor communication delays
• Multiprocessor scheduling with interprocessor communication delays
• On Graham's bound for cyclic scheduling
• C.P.M. Scheduling with Small Communication Delays and Task Duplication
• Two-Processor Scheduling with Start-Times and Deadlines
• Complexity of Scheduling under Precedence Constraints

This page was built for publication: Tree scheduling with communication delays