Advances in Operations Research
Volume 2011 (2011), Article ID 476939, 20 pages
Research Article

Inapproximability and Polynomial-Time Approximation Algorithm for UET Tasks on Structured Processor Networks

1Laboratoire G-SCOP, 46 avenue Félix Viallet, 38031 Grenoble Cedex 1, France
2LIRMM, 161 rue Ada, UMR 5056, 34392 Montpellier Cedex 5, France

Received 26 October 2010; Revised 22 March 2011; Accepted 4 April 2011

Academic Editor: Ching-Jong Liao

Copyright © 2011 M. Bouznif and R. Giroudeau. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


We investigate complexity and approximation results on a processor networks where the communication delay depends on the distance between the processors performing tasks. We then prove that there is no heuristic with a performance guarantee smaller than 4/3 for makespan minimization for precedence graph on a large class of processor networks like hypercube, grid, torus, and so forth, with a fixed diameter 𝛿 . We extend complexity results when the precedence graph is a bipartite graph. We also design an efficient polynomial-time 𝑂 ( 𝛿 2 ) -approximation algorithm for the makespan minimization on processor networks with diameter 𝛿 .