Un ordonnancement dynamique de tâches stochastiques sur un seul processeur

Ali Derbala

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

  • Volume: 36, Issue: 4, page 365-373
  • ISSN: 0399-0559

Abstract

top
We show that a particular dynamic priority given to jobs in a multitasks operating system of computers is a deteriorating jobs or a delaying jobs scheduling. Under some assumptions we also show that it is an index rule. To do this, we present the tool of bandit processes to solve stochastic scheduling problems on a single machine.

How to cite

top

Derbala, Ali. "Un ordonnancement dynamique de tâches stochastiques sur un seul processeur." RAIRO - Operations Research - Recherche Opérationnelle 36.4 (2002): 365-373. <http://eudml.org/doc/244656>.

@article{Derbala2002,
abstract = {Nous montrons qu’une priorité dynamique particulière allouée aux tâches dans un système d’exploitation d’ordinateurs multitâches s’interprète comme deux problèmes d’ordonnancement particuliers, l’ordonnancement de tâches détériorantes à durée opératoires variables et de tâches en retard ou en attente de réparation de la machine. Deux propositions sur son comportement sont énoncées. Sous certaines conditions nous montrons qu’elle est une règle d’indice. Pour le faire, nous présentons l’outil des processus bandits pour la résolution des problèmes d’ordonnancement stochastiques sur une machine. Mots-clés : Indices de Gittins, ordonnancement stochastique, processus bandit, stratégies préemptive et non préemptive.},
author = {Derbala, Ali},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {bandit processes; Gittins indices},
language = {fre},
number = {4},
pages = {365-373},
publisher = {EDP-Sciences},
title = {Un ordonnancement dynamique de tâches stochastiques sur un seul processeur},
url = {http://eudml.org/doc/244656},
volume = {36},
year = {2002},
}

TY - JOUR
AU - Derbala, Ali
TI - Un ordonnancement dynamique de tâches stochastiques sur un seul processeur
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 2002
PB - EDP-Sciences
VL - 36
IS - 4
SP - 365
EP - 373
AB - Nous montrons qu’une priorité dynamique particulière allouée aux tâches dans un système d’exploitation d’ordinateurs multitâches s’interprète comme deux problèmes d’ordonnancement particuliers, l’ordonnancement de tâches détériorantes à durée opératoires variables et de tâches en retard ou en attente de réparation de la machine. Deux propositions sur son comportement sont énoncées. Sous certaines conditions nous montrons qu’elle est une règle d’indice. Pour le faire, nous présentons l’outil des processus bandits pour la résolution des problèmes d’ordonnancement stochastiques sur une machine. Mots-clés : Indices de Gittins, ordonnancement stochastique, processus bandit, stratégies préemptive et non préemptive.
LA - fre
KW - bandit processes; Gittins indices
UR - http://eudml.org/doc/244656
ER -

References

top
  1. [1] S. Browne et U. Yechiali, Scheduling deteriorating jobs on a single processor. Oper. Res. 38 (1990) 495-498. Zbl0703.90051
  2. [2] J.C. Gittins et D.M. Jones, A dynamic index for the sequential Design of experiments, dans Colloquia Mathematica Janes Bolai, Vol. 9, European meeting of statisticians. Budapest, Hungary (1972) 241-266. Zbl0303.62064MR370964
  3. [3] J.C. Gittins et K.D. Glazebrook, On Bayesian models in stochastic scheduling. J. Appl. Probab. 14 (1977) 556-565. Zbl0373.90035MR452716
  4. [4] J.C. Gittins, Bandit process and dynamic allocation indices. J. Roy. Statist. Soc. Sect. B 41 (1979a) 148-177. Zbl0411.62055MR547241
  5. [5] J.C. Gittins et D.M. Jones, A dynamic allocation index for the discounted multiarmed bandit problem. Biometrika 66 (1979b) 561-565. 
  6. [6] J.C. Gittins, Multi armed Bandit allocation indices. John Wiley & Sons (1989). Zbl0699.90068MR996417
  7. [7] K.D. Glazebrook, Stochastic scheduling, Ph.D. Thesis. Downing College, Cambridge (1976). Zbl0339.90030MR418896
  8. [8] K.D. Glazebrook, Myopic strategies for Bayesian models in stochastic scheduling. Oper. Res. 19 (1982) 160-170. Zbl0511.90070MR696149
  9. [9] K.D. Glazebrook, Optimal strategies for families of alternative bandit processes. IEEE Trans. Automat. Control AC-28 (1983) 858-861. Zbl0538.90095MR717847
  10. [10] K.D. Glazebrook, Evaluating the effects of machine breakdowns in stochastic scheduling problems. Naval Res. Logist. Quarterly 34 (1987) 319-335. Zbl0648.90042MR888500
  11. [11] C. Haro et C. Proust, Un ordonnancement équitable par priorités bornées, dans Colloque Méthodes et outils d’aide à la décision, MOAD’92. Béjaia, Algérie (1992) 46-49. 
  12. [12] P. Nash, Optimal allocation of resources between research projects, Ph.D. Thesis. Cambridge University (1973). 
  13. [13] P. Nash, A generalized bandit problem. J. Roy. Statist. Soc. Sect. B 42 (1980) 165-169. Zbl0459.90087MR583351
  14. [14] D.R. Robinson, Algorithms for evaluating the dynamic allocation index. Oper. Res. Lett. 1 (1982) 72-74. Zbl0488.90074
  15. [15] K.C. Sevcik, The use of service time distributions in scheduling, Ph.D. Dissertation. Comm. on Information Sciences, University of Chicago (1971). 
  16. [16] K.C. Sevcik, Scheduling for minimum total loss using service time distributions. J. Assoc. Comput. Mach. 21 (1974) 66-75. Zbl0271.68047MR339801
  17. [17] W.E. Smith, Various optimizers for single state production. Naval Res. Logist. Quarterly 3 (1956) 59-66. MR89109
  18. [18] G. Weiss, Turnpike optimality of Smith’s rule in parallel machines stochastic scheduling. Math. Oper. Res. 17 (1992a) 255-270. Zbl0776.90043
  19. [19] G. Weiss, A tutorial in stochastic scheduling School of Isy. E. Georgia Tech, Atlanta, GA 30332 (1992b). 
  20. [20] P. Whittle, Multi-armed bandits and the Gittins index. J. Roy. Statist. Soc. Sect. B 42 (1980) 143-149. Zbl0439.90096MR583348

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.