Multiprocessor scheduling with communication delays

DOI10.1016/0167-8191(90)90056-FzbMath0711.68017OpenAlexW2581172100MaRDI QIDQ922681

B. J. Lageweg, Jan Karel Lenstra, Bart Veltman

Publication date: 1990

Published in: Parallel Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-8191(90)90056-f

zbMATH Keywords

complexityschedulingparallel computationmultiprocessorparallel processorscommunication delays

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (43)

A note on scheduling multiprocessor tasks with precedence constraints on parallel processors ⋮ Improved mixed-integer programming models for the multiprocessor scheduling problem with communication delays ⋮ Three, four, five, six, or the complexity of scheduling with communication delays ⋮ Minimizing the total weighted late work in scheduling of identical parallel processors with communication delays ⋮ Complexity of scheduling multiprocessor tasks with prespecified processors allocations ⋮ Maximizing the throughput of parallel jobs on hypercubes ⋮ Scheduling complete intrees on two uniform processors with communication delays ⋮ Real-time scheduling of linear speedup parallel tasks ⋮ An approximation algorithm for scheduling on three dedicated machines ⋮ Shop scheduling problems with multiprocessor tasks on dedicated processors ⋮ Efficiency and effectiveness of normal schedules on three dedicated processors ⋮ Reducing the solution space of optimal task scheduling ⋮ Scheduling multiprocessor tasks on a dynamic configuration of dedicated processors ⋮ Distributed processing of divisible jobs with communication startup costs ⋮ Scheduling UET-UCT series-parallel graphs on two processors ⋮ Branch and bound methods for scheduling problems with multiprocessor tasks on dedicated processors ⋮ Performance of Coffman-Graham schedules in the presence of unit communication delays ⋮ Using duplication for scheduling unitary tasks on m processors with unit communication delays ⋮ On contiguous and non-contiguous parallel task scheduling ⋮ Scheduling multiprocessor tasks on parallel processors with limited availability. ⋮ Scheduling of pipelined operator graphs ⋮ Complexity and approximation results for scheduling multiprocessor tasks on a ring. ⋮ Scheduling groups of tasks with precedence constraints on three dedicated processors. ⋮ Scheduling multiprocessor tasks for mean flow time criterion ⋮ Scheduling trees with large communication delays on two identical processors ⋮ An approximation algorithm for scheduling dependent tasks on \(m\) processors with small communication delays ⋮ New applications of the Muntz and Coffman algorithm ⋮ A \(\frac 54\)-approximation algorithm for scheduling identical malleable tasks ⋮ Some models for scheduling parallel programs with communication delays ⋮ Linear algorithms for preemptive scheduling of multiprocessor tasks subject to minimal lateness ⋮ Polynomial time approximation algorithms for machine scheduling: Ten open problems ⋮ Preemptive scheduling of multiprocessor tasks on the dedicated processor system subject to minimal lateness ⋮ Scheduling unitary task systems with zero--one communication delays for quasi-interval orders ⋮ Polynomial algorithms for resource-constrained and multiprocessor task scheduling problems ⋮ Scheduling multiprocessor tasks -- An overview ⋮ Scheduling multiprocessor tasks with chain constraints ⋮ On the complexity of scheduling with large communication delays ⋮ MPI Parallelization of Variable Neighborhood Search ⋮ Single machine scheduling subject to precedence delays ⋮ Scheduling rooted forests with communication delays ⋮ Unconstrained static scheduling with communication weights ⋮ A very difficult scheduling problem with communication delays ⋮ Scheduling multiprocessor tasks on two parallel processors

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