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 complexity, combinatorial optimization, scheduling

@article{RO_2013__47_1_73_0, author = {Kordon, Alix Munier and Kacem, Fadi and Dupont de Dinechin, Beno{\^\i}t and Finta, Lucian}, title = {Scheduling an interval ordered precedence graph with communication delays and a limited number of processors}, journal = {RAIRO - Operations Research - Recherche Op\'erationnelle}, pages = {73--87}, publisher = {EDP-Sciences}, volume = {47}, number = {1}, year = {2013}, doi = {10.1051/ro/2013028}, mrnumber = {3143743}, zbl = {1282.90072}, language = {en}, url = {http://archive.numdam.org/articles/10.1051/ro/2013028/} }

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 SP - 73 EP - 87 VL - 47 IS - 1 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ro/2013028/ DO - 10.1051/ro/2013028 LA - en ID - RO_2013__47_1_73_0 ER -

%0 Journal Article %A Kordon, Alix Munier %A Kacem, Fadi %A Dupont de Dinechin, Benoît %A Finta, Lucian %T Scheduling an interval ordered precedence graph with communication delays and a limited number of processors %J RAIRO - Operations Research - Recherche Opérationnelle %D 2013 %P 73-87 %V 47 %N 1 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ro/2013028/ %R 10.1051/ro/2013028 %G en %F RO_2013__47_1_73_0

Kordon, Alix Munier; Kacem, Fadi; Dupont de Dinechin, Benoît; Finta, Lucian. Scheduling an interval ordered precedence graph with communication delays and a limited number of processors. RAIRO - Operations Research - Recherche Opérationnelle, Volume 47 (2013) no. 1, pp. 73-87. doi : 10.1051/ro/2013028. http://archive.numdam.org/articles/10.1051/ro/2013028/

[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. | MR | Zbl

[2] 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. | MR

and ,[3] 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] Complexity and approximation for precedence constrained scheduling problems with large communication delays. Theor. Comput. Sci. 401 (2008) 107-119. | MR | Zbl

, , and ,[5] Some simple scheduling algorithms. Naval Research Logistics Quarterly 21 (1974) 177-185. | MR | Zbl

,[6] Scheduling precedence graphs in systems with interprocessor communication times. SIAM J. Comput. 18 (1989) 244-257. | MR | Zbl

, , and ,[7] Analysis of Scheduling Problems with Typed Task Systems. Discrete Appl. Math. 52 (1994) 223-232. | MR | Zbl

,[8] Scheduling Time-Constrained Instructions on Pipelined Processors. ACM Transact. Program. Languages Syst. 23 (2001) 73-103.

, and ,[9] Scheduling time-critical instructions on risc machines. ACM Transactions on Programming Languages and Systems 4 (1993) 632-658.

and ,[10] Scheduling interval-ordered tasks. SIAM J. Comput. 8 (1979) 405-409. | MR | Zbl

and ,[11] Multiprocessor scheduling with communication delays. Parallel Comput. 16 (1990) 173-182. | Zbl

, and ,[12] The complexity of scheduling typed task systems with and without communication delays. External Report 1998-26, UU-CS (1998).

,[13] Scheduling interval-ordered tasks with non-uniform deadlines subject to non-zero communication delays. Parallel Comput. 25 (1999) 3-21. | MR | Zbl

,[14] Minimizing makespan in a two-machine flow shop with delays and unit-time operations is np-hard. J. Scheduling 7 (2004) 333-348. | MR | Zbl

, and ,*Cited by Sources: *