Scheduling in the presence of processor networks : complexity and approximation.

*(English. French summary)*Zbl 1242.90075Summary: We study the problem of makespan minimization for the multiprocessor scheduling problem in the presence of communication delays. The communication delay between two tasks \(i\) and \(j\) depends on the distance between the two processors on which these two tasks are executed. Lahlou shows that a simple polynomial-time algorithm exists when the length of the schedule is at most two (the problem becomes \(\mathcal {NP}\)-complete when the length of the schedule is at most three). We prove that there is no polynomial-time algorithm with a performance guarantee of less than 4/3 (unless \(\mathcal P = \mathcal {NP})\) to minimize the makespan when the network topology is a chain or ring and the precedence graph is a bipartite graph of depth one. We also develop two polynomial-time approximation algorithms with constant ratio dedicated to cases where the processor network admits a limited or unlimited number of processors.

##### MSC:

90B35 | Deterministic scheduling theory in operations research |

68W25 | Approximation algorithms |

68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |

PDF
BibTeX
XML
Cite

\textit{V. Boudet} et al., RAIRO, Oper. Res. 46, No. 1, 1--22 (2012; Zbl 1242.90075)

**OpenURL**

##### References:

[1] | J. Błażewicz, K. Ecker, E. Pesch, G. Schmidt and J. W\?glarz, Handbook on Scheduling. Springer (2007). |

[2] | E. Bampis, A. Giannakos and J.C. König, On the complexity of scheduling with large communication delays. Eur. J. Oper. Res.94 (1996) 252-260. · Zbl 0947.90573 |

[3] | R.E. Bellman, On a routing problem. Quart. Appl. Math.16 (1958) 87-90. · Zbl 0081.14403 |

[4] | B. Chen, C.N. Potts and G.J. Woeginger, Handbook of Combinatorial Optimization, in A review of machine scheduling : Complexity, algorithms and approximability3. Kluwer Academic Publishers (1998). |

[5] | P. Chrétienne and C. Picouleau, Scheduling Theory and its Applications, in Scheduling with Communication Delays : A Survey. Chapt. 4, John Wiley & Sons (1995). |

[6] | K.H. Ecker and H. Hodam, Heuristic algorithms for the task scheduling under consideration of communication delays. Technical Report, T.U. Clausthal (1996). |

[7] | H. El-Rewini and T.G. Lewis, Scheduling parallel program tasks onto arbitrary target machines. J. Parallel Distribut. Comput.9 (1990) 138-153. · Zbl 0861.90072 |

[8] | L. Finta and Z. Liu, Complexity of task graph scheduling with fixed communication capacity. Int. J. Found. Comput. Sci.8 (1997) 43-66. · Zbl 0870.68026 |

[9] | M.R. Garey and D.S. Johnson, Computers and Intractability, a Guide to the Theory of \?\?-Completeness. Freeman (1979). · Zbl 0411.68039 |

[10] | A. Giannakos, Algorithmique pour le parallélisme : certains problèmes d’ordonnancement de tâches et algorithmes de couplage. Ph.D. thesis, Université de Paris-XI Orsay (1997). |

[11] | R. Giroudeau, J.C. König and B. Valéry, Scheduling UET-tasks on a star network : complexity and approximation. Quart. J. Oper. Res.9 (2011) 29-48. · Zbl 1217.68039 |

[12] | R.L. Graham, Bounds for certain multiprocessing anomalies. Bell System Tech. J.45 (1966) 1563-1581. · Zbl 0168.40703 |

[13] | R.L. Graham, Bounds on the performance of scheduling algorithms, Computer and job-shop scheduling theory. E.G. Coffman edition, John Wiley Ltd. (1976). |

[14] | R.L. Graham, E.L. Lawler, J.K. Lenstra and A.H.G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling theory : a survey. Ann. Discrete Math.5 (1979) 287-326. · Zbl 0411.90044 |

[15] | J.A. Hoogeveen, J.K. Lenstra and B. Veltman, Three, four, five, six, or the complexity of scheduling with communication delays. Oper. Res. Lett.16 (1994) 129-137. · Zbl 0816.90083 |

[16] | J.-J. Hwang, Y.C. Chow, F.D. Anger and C.-Y. Lee, Scheduling precedence graphs in systems with interprocessor communication times. SIAM J. Comput.18 (1989) 244-257. · Zbl 0677.68026 |

[17] | C. Lahlou, Scheduling with unit processing and communication times on a ring network : Approximation results, in Proceedings of Europar. Springer-Verlag (1996) 539-542. Zbl0879.90119 · Zbl 0879.90119 |

[18] | C. Lahlou, Ordonnancement dans les réseaux de processeurs : complexité et approximation. Ph.D. thesis, Université Paris VI (1998). |

[19] | A. Munier and J.C. König, A heuristic for a scheduling problem with communication delays. Oper. Res. (1997) 145-148. · Zbl 0892.90104 |

[20] | C. Picouleau, UET - UCTschedules on arbitrary networks. Technical Report, LITP, Blaise Pascal, Université Paris VI (1994). |

[21] | C. Picouleau, New complexity results on scheduling with small communication delays. Disc. Appl. Math.60 (1995) 331-342. Zbl0837.68009 · Zbl 0837.68009 |

[22] | V.J. Rayward-Smith, UET scheduling with unit interprocessor communication delays. Disc. Appl. Math.18 (1987) 55-71. Zbl0634.90031 · Zbl 0634.90031 |

[23] | O. Sinnen, Task Scheduling for Parallel System. Chap. 7, Wiley (2007). |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.