Scheduling UET trees with communication delays on two processors
RAIRO - Operations Research - Recherche Opérationnelle, Volume 34 (2000) no. 2, pp. 131-144.
@article{RO_2000__34_2_131_0,
     author = {Guinand, Fr\'ed\'eric and Trystman, Denis},
     title = {Scheduling {UET} trees with communication delays on two processors},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {131--144},
     publisher = {EDP-Sciences},
     volume = {34},
     number = {2},
     year = {2000},
     mrnumber = {1755979},
     zbl = {0961.90032},
     language = {en},
     url = {http://archive.numdam.org/item/RO_2000__34_2_131_0/}
}
TY  - JOUR
AU  - Guinand, Frédéric
AU  - Trystman, Denis
TI  - Scheduling UET trees with communication delays on two processors
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2000
SP  - 131
EP  - 144
VL  - 34
IS  - 2
PB  - EDP-Sciences
UR  - http://archive.numdam.org/item/RO_2000__34_2_131_0/
LA  - en
ID  - RO_2000__34_2_131_0
ER  - 
%0 Journal Article
%A Guinand, Frédéric
%A Trystman, Denis
%T Scheduling UET trees with communication delays on two processors
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2000
%P 131-144
%V 34
%N 2
%I EDP-Sciences
%U http://archive.numdam.org/item/RO_2000__34_2_131_0/
%G en
%F RO_2000__34_2_131_0
Guinand, Frédéric; Trystman, Denis. Scheduling UET trees with communication delays on two processors. RAIRO - Operations Research - Recherche Opérationnelle, Volume 34 (2000) no. 2, pp. 131-144. http://archive.numdam.org/item/RO_2000__34_2_131_0/

[Chr89] P. Chrétienne, A Polynomial Algorithm to Optimally Schedule Tasks on a Virtual Distributed System Under Tree-like Precedence Constraints. European J. Oper. Res. 43 (1989) 225-230. | MR | Zbl

[DL88] J. Du and J.Y.-T. Leung, Scheduling tree-structured tasks with restricted execution times. Inform. Process. Lett. 28 (1988) 183-188. | MR | Zbl

[DL89] J. Du and J.Y.-T. Leung, Complexity of Scheduling Parallel Tasks Systems. SIAM J. Discrete Math. 2 (1989) 473-487. | MR | Zbl

[GRT97] F. Guinand, C. Rapine and D. Trystram, Worst-Case Analysis of Algorithms for Scheduling UECT Trees on m Processors. IEEE Trans. Parallel and Distributed Systems 8 (1997).

[GT93] F. Guinand and D. Trystram, Optimal Scheduling of UECT Trees on Two Processors. Technical Report Rapport APACHE n° 3. Laboratoire de Modélisation et de Calcul - IMAG, Grenoble (1993).

[Hu61] T.C. Hu, Parallel Sequencing and Assembly Line Problems. Oper. Res. 9 (1961) 841-848. | MR

[Law93] E.L. Lawler, Scheduling Trees on Multiprocessors with Unit Communication Delays, Workshop on Models and Algorithms for Planning and Scheduling Problems. Villa Vigoni, Lake Como, Italy (1993).

[LVV93] J. K. Lenstra, M. Veldhorst and B. Veltman, The Complexity of Scheduling Trees with Communication Delays. Lecture Notes in Comput. Sci. (ESA'93) 726 (1993) 284-294. | Zbl

[NLH81] K. Nakajima, J.Y.-T. Leung and S. L. Hakimi, Optimal Processor Scheduling of Tree Precedence Constrainted Tasks with Two Execution Times. Performance Evaluation 1 (1981) 320-330. | MR | Zbl

[Pic93] C. Picouleau, Étude des Problèmes d'Optimisation dans les Systèmes Distribués. Ph.D. Thesis, Paris VI, Paris - France ( 1993, in French.

[PY90] C.H. Papadimitriou and M. Yannakakis, Towards an architecture-independent analysis of parallel algorithms. SIAM J. Comput. 19 (1990) 322-328. | MR | Zbl

[RS87] V. J. Rayward-Smith, UET Scheduling with Unit Interprocessor Communication Delays. Discrete Appl Math 18 (1987) 55-71. | MR | Zbl

[Vel93] M. Veldhorst, A Linear Time Algorithm to Schedule Trees with Communication Delays Optimally on Two Machines, Technical Report RUU-CS-93-04. Department of computer science, Utrecht (1993).

[VRKL96] T. A. Varvarigou, V.P. Roychowdhury, T. Kailath and E. Lawler, Scheduling In and Out Forests in the Presence of Communication Delays. IEE Trans. Parallel and Distributed Systems 7 (1996).