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.68021OpenAlexW2170627077MaRDI QIDQ5929309
Publication date: 4 April 2001
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0166-218x(00)00179-7
Nonnumerical algorithms (68W05) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)
Related Items (18)
A genetic approach to solving the problem of cyclic job shop scheduling with linear constraints ⋮ Cyclic multiple-robot scheduling with time-window constraints using a critical path approach ⋮ Benchmarking the clustering algorithms for multiprocessor environments using dynamic priority of modules ⋮ Petri nets for the design and operation of manufacturing systems ⋮ The basic cyclic scheduling problem with linear precedence constraints ⋮ Performance of Coffman-Graham schedules in the presence of unit communication delays ⋮ Bicriteria approximation algorithms for scheduling problems with communications delays ⋮ Preemptive scheduling of independent jobs on identical parallel machines subject to migration delays ⋮ Using duplication for scheduling unitary tasks on m processors with unit communication delays ⋮ Malleable scheduling beyond identical machines ⋮ Minimizing flow time in cyclic schedules for identical jobs with acyclic precedence: The bottleneck lower bound. ⋮ Unnamed Item ⋮ A mixed integer programming model for the cyclic job-shop problem with transportation ⋮ Complexity and approximation for precedence constrained scheduling problems with large communication delays ⋮ Inapproximability and polynomial-time approximation algorithm for UET tasks on structured processor networks ⋮ High-multiplicity cyclic job shop scheduling ⋮ Scheduling \(UET\)-tasks on a star network: complexity and approximation ⋮ The complexity of a cyclic scheduling problem with identical machines and 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
This page was built for publication: An approximation algorithm for scheduling dependent tasks on \(m\) processors with small communication delays
