Scheduling UET trees with communication delays on two processors

Frédéric Guinand; Denis Trystman

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

  • Volume: 34, Issue: 2, page 131-144
  • ISSN: 0399-0559

How to cite

top

Guinand, Frédéric, and Trystman, Denis. "Scheduling UET trees with communication delays on two processors." RAIRO - Operations Research - Recherche Opérationnelle 34.2 (2000): 131-144. <http://eudml.org/doc/105212>.

@article{Guinand2000,
author = {Guinand, Frédéric, Trystman, Denis},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {parallel processing; scheduling; intrees; UECT; communication delays},
language = {eng},
number = {2},
pages = {131-144},
publisher = {EDP-Sciences},
title = {Scheduling UET trees with communication delays on two processors},
url = {http://eudml.org/doc/105212},
volume = {34},
year = {2000},
}

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
PB - EDP-Sciences
VL - 34
IS - 2
SP - 131
EP - 144
LA - eng
KW - parallel processing; scheduling; intrees; UECT; communication delays
UR - http://eudml.org/doc/105212
ER -

References

top
  1. [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. Zbl0689.90045MR1033650
  2. [DL88] J. DU and J.Y.-T. LEUNG, Scheduling tree-structured tasks with restricted execution times. Inform. Process. Lett. 28 (1988) 183-188. Zbl0658.68040MR958817
  3. [DL89] J. DU and J.Y.-T. LEUNG, Complexity of Scheduling Parallel Tasks Systems. SIAM J. Discrete Math. 2 (1989) 473-487. Zbl0676.90029MR1018532
  4. [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). 
  5. [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). 
  6. [Hu61] T.C. HU, Parallel Sequencing and Assembly Line Problems. Oper. Res. 9 (1961) 841-848. MR135614
  7. [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). 
  8. [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. Zbl0840.68013
  9. [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. Zbl0504.68022MR664153
  10. [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. 
  11. [PY90] C.H. PAPADIMITRIOU and M. YANNAKAKIS, Towards an architecture-independent analysis of parallel algorithms. SIAM J. Comput. 19 (1990) 322-328. Zbl0692.68032MR1042731
  12. [RS87] V. J. RAYWARD-SMITH, UET Scheduling with Unit Interprocessor Communication Delays. Discrete Appl Math 18 (1987) 55-71. Zbl0634.90031MR905178
  13. [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). 
  14. [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). 

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.