Scheduling UET-UCT series-parallel graphs on two processors

DOI10.1016/0304-3975(96)00035-7zbMath0877.68008OpenAlexW2089340573MaRDI QIDQ1365936

Lucian Finta, Zhen Liu, Ioannis Milis, Evripidis Bampis

Publication date: 10 September 1997

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

Full work available at URL: https://hal.inria.fr/inria-00074115/file/RR-2566.pdf

zbMATH Keywords

quadratic algorithmscheduling of task graphsSP1 graphs

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (11)

A note on algebraic expressions of rhomboidal labeled graphs ⋮ On lengths of edge-labeled graph expressions ⋮ Performance of Coffman-Graham schedules in the presence of unit communication delays ⋮ Scheduling series-parallel task graphs to minimize peak memory ⋮ On algebraic expressions of directed grid graphs ⋮ Scheduling tree-like task systems with non-uniform deadlines subject to unit-length communication delays ⋮ Scheduling trees with large communication delays on two identical processors ⋮ A linear time algorithm for a variant of the MAX CUT problem in series parallel graphs ⋮ Scheduling UET-UCT outforests to minimize maximum lateness ⋮ Scheduling unitary task systems with zero--one communication delays for quasi-interval orders ⋮ Decomposition methods for generating algebraic expressions of full square rhomboids and other graphs

Cites Work

• Multiprocessor scheduling with communication delays
• UET scheduling with unit interprocessor communication delays
• The Recognition of Series Parallel Digraphs
• Linear-time computability of combinatorial problems on series-parallel graphs
• Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
• Scheduling to Minimize Maximum Cumulative Cost Subject to Series-Parallel Precedence Constraints
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey

This page was built for publication: Scheduling UET-UCT series-parallel graphs on two processors