An approximation algorithm for scheduling dependent tasks on \(m\) processors with small communication delays
From MaRDI portal
Publication:5929309
DOI10.1016/S0166-218X(00)00179-7zbMath0967.68021MaRDI QIDQ5929309
Publication date: 4 April 2001
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
68W05: Nonnumerical algorithms
68M20: Performance evaluation, queueing, and scheduling in the context of computer systems
Related Items
Cyclic multiple-robot scheduling with time-window constraints using a critical path approach, Bicriteria approximation algorithms for scheduling problems with communications delays, Complexity and approximation for precedence constrained scheduling problems with large communication delays, High-multiplicity cyclic job shop scheduling, The complexity of a cyclic scheduling problem with identical machines and precedence constraints, Petri nets for the design and operation of manufacturing systems, 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, Minimizing flow time in cyclic schedules for identical jobs with acyclic precedence: The bottleneck lower bound., A genetic approach to solving the problem of cyclic job shop scheduling with linear constraints, The basic cyclic scheduling problem with linear precedence constraints
Cites Work
- Unnamed Item
- Multiprocessor scheduling with communication delays
- UET scheduling with unit interprocessor communication delays
- Three, four, five, six, or the complexity of scheduling with communication delays
- A study of the cyclic scheduling problem on parallel processors
- Performance of Coffman-Graham schedules in the presence of unit communication delays
- New complexity results on scheduling with small communication delays
- Optimal scheduling for two-processor systems
- Scheduling Precedence Graphs in Systems with Interprocessor Communication Times
- A Heuristic for a Scheduling Problem with Communication Delays
- Bounds on Multiprocessing Timing Anomalies