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

Alix Munier Kordon; Fadi Kacem; Benoît Dupont de Dinechin; Lucian Finta

RAIRO - Operations Research - Recherche Opérationnelle (2013)

  • Volume: 47, Issue: 1, page 73-87
  • ISSN: 0399-0559

Abstract

top
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.

How to cite

top

Kordon, Alix Munier, et al. "Scheduling an interval ordered precedence graph with communication delays and a limited number of processors." RAIRO - Operations Research - Recherche Opérationnelle 47.1 (2013): 73-87. <http://eudml.org/doc/275037>.

@article{Kordon2013,
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.},
author = {Kordon, Alix Munier, Kacem, Fadi, Dupont de Dinechin, Benoît, Finta, Lucian},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {approximation and complexity; combinatorial optimization; scheduling},
language = {eng},
number = {1},
pages = {73-87},
publisher = {EDP-Sciences},
title = {Scheduling an interval ordered precedence graph with communication delays and a limited number of processors},
url = {http://eudml.org/doc/275037},
volume = {47},
year = {2013},
}

TY - JOUR
AU - Kordon, Alix Munier
AU - Kacem, Fadi
AU - Dupont de Dinechin, Benoît
AU - Finta, Lucian
TI - Scheduling an interval ordered precedence graph with communication delays and a limited number of processors
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 2013
PB - EDP-Sciences
VL - 47
IS - 1
SP - 73
EP - 87
AB - 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.
LA - eng
KW - approximation and complexity; combinatorial optimization; scheduling
UR - http://eudml.org/doc/275037
ER -

References

top
  1. [1] H.H. Ali and H.H. El.-Rewini, An optimal algorithm for scheduling interval ordered tasks with communication on processors. J. Comput. Syst. Sci. 2 (1995) 301–307. Zbl0830.68007MR1356508
  2. [2] 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. MR1376609
  3. [3] 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. 
  4. [4] R. Giroudeau, J.-C. Konig, F.K. Moulai and J. Palaysi, Complexity and approximation for precedence constrained scheduling problems with large communication delays. Theor. Comput. Sci.401 (2008) 107–119. Zbl1143.90012MR2431829
  5. [5] W. Horn, Some simple scheduling algorithms. Naval Research Logistics Quarterly21 (1974) 177–185. Zbl0276.90024MR343895
  6. [6] J. Hwang, Y. Chow, F. Anger and C. Lee, Scheduling precedence graphs in systems with interprocessor communication times. SIAM J. Comput.18 (1989) 244–257. Zbl0677.68026MR986664
  7. [7] K. Jansen, Analysis of Scheduling Problems with Typed Task Systems. Discrete Appl. Math.52 (1994) 223–232. Zbl0822.90083MR1287973
  8. [8] A. Leung, K.V. Palem and A. Pnueli, Scheduling Time-Constrained Instructions on Pipelined Processors. ACM Transact. Program. Languages Syst.23 (2001) 73–103. 
  9. [9] K. Palem and B. Simons, Scheduling time-critical instructions on risc machines. ACM Transactions on Programming Languages and Systems4 (1993) 632–658. 
  10. [10] C.H Papadimitriou and M. Yannakakis, Scheduling interval-ordered tasks. SIAM J. Comput.8 (1979) 405–409. Zbl0421.68040MR539257
  11. [11] B. Veltman, B.J. Lageweg and J.K. Lenstra, Multiprocessor scheduling with communication delays. Parallel Comput.16 (1990) 173–182. Zbl0711.68017
  12. [12] J. Verriet, The complexity of scheduling typed task systems with and without communication delays. External Report 1998-26, UU-CS (1998). 
  13. [13] J. Verriet, Scheduling interval-ordered tasks with non-uniform deadlines subject to non-zero communication delays. Parallel Comput.25 (1999) 3–21. Zbl0914.68014MR1675126
  14. [14] W. Yu, H. Hoogeveen and J.K. Lenstra, Minimizing makespan in a two-machine flow shop with delays and unit-time operations is np-hard. J. Scheduling7 (2004) 333–348. Zbl1154.90506MR2101693

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.