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

Claire Hanen, Alix Munier

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




Related Items (18)

A genetic approach to solving the problem of cyclic job shop scheduling with linear constraintsCyclic multiple-robot scheduling with time-window constraints using a critical path approachBenchmarking the clustering algorithms for multiprocessor environments using dynamic priority of modulesPetri nets for the design and operation of manufacturing systemsThe basic cyclic scheduling problem with linear precedence constraintsPerformance of Coffman-Graham schedules in the presence of unit communication delaysBicriteria approximation algorithms for scheduling problems with communications delaysPreemptive scheduling of independent jobs on identical parallel machines subject to migration delaysUsing duplication for scheduling unitary tasks on m processors with unit communication delaysMalleable scheduling beyond identical machinesMinimizing flow time in cyclic schedules for identical jobs with acyclic precedence: The bottleneck lower bound.Unnamed ItemA mixed integer programming model for the cyclic job-shop problem with transportationComplexity and approximation for precedence constrained scheduling problems with large communication delaysInapproximability and polynomial-time approximation algorithm for UET tasks on structured processor networksHigh-multiplicity cyclic job shop schedulingScheduling \(UET\)-tasks on a star network: complexity and approximationThe complexity of a cyclic scheduling problem with identical machines and precedence constraints



Cites Work


This page was built for publication: An approximation algorithm for scheduling dependent tasks on \(m\) processors with small communication delays