UET scheduling with unit interprocessor communication delays

DOI10.1016/0166-218X(87)90042-4zbMath0634.90031OpenAlexW2078031780MaRDI QIDQ1097163

Publication date: 1987

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

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

zbMATH Keywords

list scheduling NP-completeness NP-hard multiprocessor systems communication delay parallel languages greedy schedule scheduling a partially ordered set of unit execution time speed-up anomaly UET scheduling

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Deterministic scheduling theory in operations research (90B35)

Related Items

Tree scheduling with communication delays, Scheduling in the presence of processor networks : complexity and approximation, 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, New complexity results on scheduling with small communication delays, Parallel Machine Scheduling with Uncertain Communication Delays, Multiprocessor scheduling with interprocessor communication delays, Reducing the solution space of optimal task scheduling, Scheduling UET-UCT series-parallel graphs on two processors, Performance of Coffman-Graham schedules in the presence of unit communication delays, Open shop scheduling with delays, Using duplication for scheduling unitary tasks on m processors with unit communication delays, Malleable scheduling beyond identical machines, Scheduling UET-UCT tasks: Branch-and-bound search in the priority space, 1-optimality of static BSP computations: Scheduling independent chains as a case study., Optimising makespan and energy consumption in task scheduling for parallel systems, Unnamed Item, Erratum to ``Inapproximability and polynomial-time approximation algorithm for UET tasks on structured processor networks, A note on Graham's bound, Complexity and approximation for precedence constrained scheduling problems with large communication delays, Scheduling tree-like task systems with non-uniform deadlines subject to unit-length communication delays, Inapproximability and polynomial-time approximation algorithm for UET tasks on structured processor networks, SCHEDULING PARALLEL PROGRAM TASKS WITH NON-NEGLIGIBLE INTERTASK COMMUNICATIONS ON TO NUMA MULTIPROCESSOR SYSTEMS, Scheduling trees with large communication delays on two identical processors, An EPTAS for scheduling fork-join graphs with communication delay, An approximation algorithm for scheduling dependent tasks on \(m\) processors with small communication delays, Scheduling with uncertainties on new computing platforms, Scheduling on parallel machines with preemption and transportation delays, Scheduling \(UET\)-tasks on a star network: complexity and approximation, Scheduling UET-UCT outforests to minimize maximum lateness, Performance of critical path type algorithms for scheduling on parallel processors, New MIP model for multiprocessor scheduling problem with communication delays, Some models for scheduling parallel programs with communication delays, Scheduling unitary task systems with zero--one communication delays for quasi-interval orders, Task scheduling with and without communication delays: A unified approach, Scheduling multiprocessor tasks -- An overview, On the complexity of scheduling with large communication delays, Minimizing the overhead for some tree-scheduling problems, Scheduling 2-dimensional grids with large communication delays, Scheduling rooted forests with communication delays

Cites Work