Ordonnancement de tâches sur un système multiprocesseur - modèles déterministes et modèles stochastiques

S. Norre

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

  • Volume: 28, Issue: 3, page 221-253
  • ISSN: 0399-0559

How to cite


Norre, S.. "Ordonnancement de tâches sur un système multiprocesseur - modèles déterministes et modèles stochastiques." RAIRO - Operations Research - Recherche Opérationnelle 28.3 (1994): 221-253. <http://eudml.org/doc/105084>.

author = {Norre, S.},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {discrete event simulation; task allocation; precedence constraints; stochastic scheduling; simulated annealing},
language = {fre},
number = {3},
pages = {221-253},
publisher = {EDP-Sciences},
title = {Ordonnancement de tâches sur un système multiprocesseur - modèles déterministes et modèles stochastiques},
url = {http://eudml.org/doc/105084},
volume = {28},
year = {1994},

AU - Norre, S.
TI - Ordonnancement de tâches sur un système multiprocesseur - modèles déterministes et modèles stochastiques
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 1994
PB - EDP-Sciences
VL - 28
IS - 3
SP - 221
EP - 253
LA - fre
KW - discrete event simulation; task allocation; precedence constraints; stochastic scheduling; simulated annealing
UR - http://eudml.org/doc/105084
ER -


  1. 1. T. L. ADAM, K. M. CHANDY, J. R. DICKSON, A comparison of list schedules for parallel processing Systems, Communications of the ACM, 1974, Vol.17, p. 685-690. Zbl0293.68047
  2. 2. J. BRUNO, Deterministic and stochastic scheduling with treelike precedence constraints, in Deterministic and stochastic scheduling, Dempster et al. (eds.), Dordrecht (Hollande), 1982, p. 367-374. Zbl0488.68036
  3. 3. A. A. BULGAK, J. L. SANDERS, Integrating a modified simulated annealing algorithm with the simulation of a manufacturing System to optimize buffer sizes in automatic assembly systems, Proceeding of the 1988Winter Simulation Conference, p. 684-690. 
  4. 4. J. CARLIER, P. CHRÉTIENNE, Problèmes d'ordonnancement, Masson, Paris, 1988. Zbl0494.90040
  5. 5. K. M. CHANDY, P. F. REYNOLDS, Scheduling partially ordered tasks with probabilistic execution times, in Proceedings of the Fifth Symposium on Operating Systems Principles, 1975, p. 164-177. 
  6. 6. E. G. COFFMAN, R. L. GRAHAM, Optimal scheduling for two processor Systems, Acta Informatica, 1972, Vol. 1, p. 200-213. Zbl0248.68023MR334913
  7. 7. E. G. COFFMAN, Computer and jobshop scheduling theory, John Wiley and sons, 1976. Zbl0359.90031
  8. 8. E. G. COFFMAN, Z. LIU, On the optimal stochastic scheduling of out-forests, Operations Research, Jan-Feb. 1992, Vol. 40, Supp. n° 1, p. 567-575. Zbl0764.90042MR1152742
  9. 9. C. COROYER, Z. LIU, Effectiveness of heuristics and simulated annealing for the scheduling of concurrent tasks - an empirical comparison, Rapport INRIA, n° 1379, Janvier 1991. 
  10. 10. E. D'HOLLANDER, Computer aided dataflow analysis for the conversion of sequential programs into parallel form, Special topics in supercomputing, Vol. 3 : algorithms and applications on vector and parallel computers), North-Holland, 1987. 
  11. 11. A. FERRARA, R. MINCIARDI, Resource constrained scheduling via simulated annealing: a discrete event approach, Proceedings of the European Simulation Symposium, Ghent (Belgium), 1990, p. 177-181. 
  12. 12. G. FLEURY, Résolution de problèmes NP-complets : méthodes déterministes et stochastiques, Thèse d'université, Université Blaise Pascal, Clermont-Ferrand II, 1993. 
  13. 13. E. FROSTIG, A stochastic scheduling problem with intree precedence constraints, Operations Research, 1988, Vol. 36, p. 937-942. Zbl0679.90022MR973149
  14. 14. M. R. GAREY, D. S. JOHNSON, Computers and intractability: a guide to the theory of NP-completeness, Freeman, New York, 1983. Zbl0411.68039MR519066
  15. 15. J. M. GOURGAND, S. NORRE, Design and realization of a Petri Net simulator for program parallelization, Proceedings of the tenth IASTED International Conference, Innsbruck (Austria), p. 83-86, February 1992. 
  16. 16. J. M. GOURGAND, S. NORRE, Static allocation of tasks on multibus multiprocessor architectures, OPOPAC (International Workshop On Principles Of PArallel Computing), 22-26 Novembre 1993, Lacanau (France), Ed. Hermès. Zbl0817.68030
  17. 17. B. HAJECK, Cooling schedules for optimal annealing, Mathematics of Operations Research, 1988, p. 311-329. Zbl0652.65050MR942621
  18. 18. T. C. HU, Parallel sequencing and assembly line problem, Operational Research, 1961, Vol. 9, p. 841-843. MR135614
  19. 19. H. KASAHARA, S. NARITA, Practical multiprocessor scheduling algorithms for efficient parallel processing, IEEE Transaction on Computers, 1984, Vol. C33, n° 11, p.1023-1029. 
  20. 20. T. G. LEWIS, W. H. PAYNE, Generalized feedback shift register pseudo random number algorithm, J. ACM, 1973, Vol. 20, n° 3, p. 456-468. Zbl0266.65009
  21. 21. Z. LIU, E. SANLAVILLE, Stochastically minimizing the makespan of structured jobs, École d'été sur la théorie de l'ordonnancement et ses applications, 28 Sept-2 Oct 1992, Chateau de Bonas (Gers), France, p. 166-184. 
  22. 22. M. A. MARSAN, G. BALBO, G. CONTE, Performance models of multiprocessor Systems, The MIT Press, USA, 1986. 
  23. 23. M. K. MOLLOY, Performance analysis using stochastic Petri nets, IEEE Transactions on Computers, 1984, Vol. C31, p. 913-917. 
  24. 24. S. NORRE, Static allocation of tasks on multiprocessor architectures with interprocessor communication delays, Lecture Notes in Computer Science 694, Arndt Bode-Mike Reeve-Gottfried Wolf (eds), Springer-Verlag, p. 488-499. 
  25. 25. S. NORRE, Affectation de tâches sur une architecture multiprocesseur - Méthodes stochastiques et évaluation des performances, Thèse de Doctorat, Université de Clermont-Ferrand II, 1993. 
  26. 26. C. H. PAPADIMITRIOU, M. YANNAKAKIS, Scheduling interval-ordered tasks, Siam. J. Comput., 1979, Vol. 8, n° 3, p. 405-409. Zbl0421.68040MR539257
  27. 27. M. PINEDO, G. WEISS, Scheduling jobs with exponentially distributed processing times and intree preceding constraints on two parallel machines, Operations Research, 1985, Vol. 33, p. 1381-1388. Zbl0581.90036MR819187
  28. 28. QNAP2 version 8, manuel de référence, Société Simulog, 1991. 
  29. 29. P. QUINTON, From specifications to machine code: parallelization methods, Parallel and Distributed Algorithms, M. Cosnard et al. (Editors), North-Holland, 1989, p. 253-256. 
  30. 30. P. SIARRY, G. DREYFUS, La méthode de recuit simulé : théorie et applications, ISDET, Paris, 1988. 
  31. 31. N. TAWBI, Parallélisation automatique: estimation des durées d'exécution et allocation statique des processeurs, Thèse de doctorat, Université Paris VI, MASI 91.47, 1991. 
  32. 32. P. J. M. VAN LAARHOVEN, Simulated annealing: theory and applications, Kluwer Academic Publishors, The Netherlands, 1989. Zbl0643.65028
  33. 33. M. WIDMER, Modèles mathématiques pour une gestion efficace des ateliers flexibles, Thèse d'état, École Polytechnique de Lausanne, 1990. 

NotesEmbed ?


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.