Scheduling in the presence of processor networks : complexity and approximation

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Deterministic scheduling theory in operations research (90B35)

Recommendations

scientific article; zbMATH DE number 1979517
Task scheduling in networks
Scheduling in synchronous networks and the greedy algorithm
Scheduling problems over network of machines
On the complexity of multiprocessor task scheduling
Computational complexity of some scheduling problems with multiprocessor tasks
Scheduling problems over a network of machines
scientific article; zbMATH DE number 2087831

Cites work

A Heuristic for a Scheduling Problem with Communication Delays
Bounds for Certain Multiprocessing Anomalies
Complexity of Task Graph Scheduling with Fixed Communication Capacity
scientific article; zbMATH DE number 3639144 (Why is no real title available?)
scientific article; zbMATH DE number 1061006 (Why is no real title available?)
scientific article; zbMATH DE number 975350 (Why is no real title available?)
New complexity results on scheduling with small communication delays
On a routing problem
On the complexity of scheduling with large communication delays
Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
Scheduling \(UET\)-tasks on a star network: complexity and approximation
Scheduling Precedence Graphs in Systems with Interprocessor Communication Times
Three, four, five, six, or the complexity of scheduling with communication delays
UET scheduling with unit interprocessor communication delays

Cited in

(24)

On the minimum number of processors for scheduling problems with communication delays
Three, four, five, six, or the complexity of scheduling with communication delays
Upper bound on the number of processors for scheduling with interprocessor communication delays.
Complexity and approximation results for scheduling multiprocessor tasks on a ring.
Scheduling with interjob communication on parallel processors
Minimizing the volume in scheduling an out-tree with communication delays and duplication.
Scheduling chains on uniform processors with communication delays
Scheduling problems over a network of machines
DVS scheduling in a line or a star network of processors
On the Complexity of Scheduling in Half-Duplex Diamond Networks
Complexity of Task Graph Scheduling with Fixed Communication Capacity
A Heuristic for a Scheduling Problem with Communication Delays
Task Scheduling in Networks
scientific article; zbMATH DE number 1560337 (Why is no real title available?)
Scheduling jobs with communication delays: using infeasible solutions for approximation
scientific article; zbMATH DE number 2086382 (Why is no real title available?)
scientific article; zbMATH DE number 1424438 (Why is no real title available?)
Scheduling problems over network of machines
Task scheduling in networks
Scheduling 2-dimensional grids with large communication delays
Scheduling \(UET\)-tasks on a star network: complexity and approximation
On approximating a scheduling problem
Inapproximability and polynomial-time approximation algorithm for UET tasks on structured processor networks
Minimizing makespan for a bipartite graph on a single processor with an integer precedence delay.

This page was built for publication: Scheduling in the presence of processor networks : complexity and approximation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2893338)