Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-22T19:10:37.226Z Has data issue: false hasContentIssue false
  • English
  • Français

Scheduling an interval ordered precedence graph with communication delaysand a limited number of processors

Published online by Cambridge University Press:  07 March 2013

Alix Munier Kordon ,
Fadi Kacem ,
Benoît Dupont de Dinechin  and
Lucian Finta
Alix Munier Kordon
Affiliation:
LIP6 – Université Pierre et Marie Curie, 4 place Jussieu, 75252 Paris Cedex 05, France. [email protected]
Fadi Kacem
Affiliation:
Laboratoire IBISC, 523 place des terrasses, 91000 Evry, France
Benoît Dupont de Dinechin
Affiliation:
Kalray, 445 rue Lavoisier, 38330 Montbonnot Saint Martin, France
Lucian Finta
Affiliation:
LIPN, Laboratoire d’Informatique de l’Université Paris-Nord, 99 avenue Jean-Baptiste Clment, 93430 Villetaneuse, France
Get access

Abstract

We consider the scheduling of an interval order precedence graph of unit execution time tasks with communication delays, release dates and deadlines. Tasks must be executed by a set of processors partitioned into K classes; each task requires one processor from a fixed class. The aim of this paper is to study the extension of the Leung–Palem–Pnueli (in short LPP) algorithm to this problem. The main result is to prove that the LPP algorithm can be extended to dedicated processors and monotone communication delays. It is also proved that the problem is NP–complete for two dedicated processors if communication delays are non monotone. Lastly, we show that list scheduling algorithm cannot provide a solution for identical processors.

Keywords

Approximation and complexitycombinatorial optimizationscheduling
Type
Research Article
Information
RAIRO - Operations Research , Volume 47 , Issue 1 , January 2013 , pp. 73 - 87
Copyright
© EDP Sciences, ROADEF, SMAI, 2013

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Ali, H.H. and El.-Rewini, H.H., An optimal algorithm for scheduling interval ordered tasks with communication on processors. J. Comput. Syst. Sci. 2 (1995) 301–307. Google Scholar
P. Chrétienne and C. Picouleau, Scheduling with communication delays : a survey. in Scheduling Theory and its Applications, edited P. Chrétienne, E.G. Coffman, J.K. Lenstra and Z. Liu. John Wiley Ltd (1995) 65–89.
B. Dupont de Dinechin, Scheduling monotone interval orders on typed task systems. In PLANSIG 2007, 26th Worshop of the UK Planning and Scheduling Special Interest Group (2007) 25–31.
Giroudeau, R., Konig, J.-C., Moulai, F.K. and Palaysi, J., Complexity and approximation for precedence constrained scheduling problems with large communication delays. Theor. Comput. Sci. 401 (2008) 107–119. Google Scholar
Horn, W., Some simple scheduling algorithms. Naval Research Logistics Quarterly 21 (1974) 177–185. Google Scholar
Hwang, J., Chow, Y., Anger, F. and Lee, C., Scheduling precedence graphs in systems with interprocessor communication times. SIAM J. Comput. 18 (1989) 244–257. Google Scholar
Jansen, K., Analysis of Scheduling Problems with Typed Task Systems. Discrete Appl. Math. 52 (1994) 223–232. Google Scholar
Leung, A., Palem, K.V. and Pnueli, A., Scheduling Time-Constrained Instructions on Pipelined Processors. ACM Transact. Program. Languages Syst. 23 (2001) 73–103. Google Scholar
Palem, K. and Simons, B., Scheduling time-critical instructions on risc machines. ACM Transactions on Programming Languages and Systems 4 (1993) 632–658. Google Scholar
Papadimitriou, C.H and Yannakakis, M., Scheduling interval-ordered tasks. SIAM J. Comput. 8 (1979) 405–409. Google Scholar
Veltman, B., Lageweg, B.J. and Lenstra, J.K., Multiprocessor scheduling with communication delays. Parallel Comput. 16 (1990) 173–182. Google Scholar
J. Verriet, The complexity of scheduling typed task systems with and without communication delays. External Report 1998-26, UU-CS (1998).
Verriet, J., Scheduling interval-ordered tasks with non-uniform deadlines subject to non-zero communication delays. Parallel Comput. 25 (1999) 3–21. Google Scholar
Yu, W., Hoogeveen, H. and Lenstra, J.K., Minimizing makespan in a two-machine flow shop with delays and unit-time operations is np-hard. J. Scheduling 7 (2004) 333–348. Google Scholar