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

Ali Derbala

RAIRO - Operations Research (2010)

  • 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 36.4 (2010): 365-373. <http://eudml.org/doc/105279>.

@article{Derbala2010,
abstract = { 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. },
author = {Derbala, Ali},
journal = {RAIRO - Operations Research},
keywords = {Indices de Gittins; ordonnancement stochastique; processus bandit; stratégies préemptive et non préemptive; bandit processes; Gittins indices},
language = {fre},
month = {3},
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/105279},
volume = {36},
year = {2010},
}

TY - JOUR
AU - Derbala, Ali
TI - Un ordonnancement dynamique de tâches stochastiques sur un seul processeur
JO - RAIRO - Operations Research
DA - 2010/3//
PB - EDP Sciences
VL - 36
IS - 4
SP - 365
EP - 373
AB - 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.
LA - fre
KW - Indices de Gittins; ordonnancement stochastique; processus bandit; stratégies préemptive et non préemptive; bandit processes; Gittins indices
UR - http://eudml.org/doc/105279
ER -

References

top
  1. S. Browne et U. Yechiali, Scheduling deteriorating jobs on a single processor. Oper. Res.38 (1990) 495-498.  Zbl0703.90051
  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.  
  3. J.C. Gittins et K.D. Glazebrook, On Bayesian models in stochastic scheduling. J. Appl. Probab.14 (1977) 556-565.  Zbl0373.90035
  4. J.C. Gittins, Bandit process and dynamic allocation indices. J. Roy. Statist. Soc. Sect. B41 (1979a) 148-177.  Zbl0411.62055
  5. J.C. Gittins et D.M. Jones, A dynamic allocation index for the discounted multiarmed bandit problem. Biometrika66 (1979b) 561-565.  
  6. J.C. Gittins, Multi armed Bandit allocation indices. John Wiley & Sons (1989).  Zbl0699.90068
  7. K.D. Glazebrook, Stochastic scheduling, Ph.D. Thesis. Downing College, Cambridge (1976).  Zbl0339.90030
  8. K.D. Glazebrook, Myopic strategies for Bayesian models in stochastic scheduling. Oper. Res.19 (1982) 160-170.  Zbl0511.90070
  9. K.D. Glazebrook, Optimal strategies for families of alternative bandit processes. IEEE Trans. Automat. Control AC-28 (1983) 858-861.  Zbl0538.90095
  10. K.D. Glazebrook, Evaluating the effects of machine breakdowns in stochastic scheduling problems. Naval Res. Logist. Quarterly34 (1987) 319-335.  Zbl0648.90042
  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. P. Nash, Optimal allocation of resources between research projects, Ph.D. Thesis. Cambridge University (1973).  
  13. P. Nash, A generalized bandit problem. J. Roy. Statist. Soc. Sect. B42 (1980) 165-169.  Zbl0459.90087
  14. D.R. Robinson, Algorithms for evaluating the dynamic allocation index. Oper. Res. Lett.1 (1982) 72-74.  Zbl0488.90074
  15. K.C. Sevcik, The use of service time distributions in scheduling, Ph.D. Dissertation. Comm. on Information Sciences, University of Chicago (1971).  
  16. K.C. Sevcik, Scheduling for minimum total loss using service time distributions. J. Assoc. Comput. Mach.21 (1974) 66-75.  Zbl0271.68047
  17. W.E. Smith, Various optimizers for single state production. Naval Res. Logist. Quarterly3 (1956) 59-66.  
  18. G. Weiss, Turnpike optimality of Smith's rule in parallel machines stochastic scheduling. Math. Oper. Res.17 (1992a) 255-270.  Zbl0776.90043
  19. G. Weiss, A tutorial in stochastic scheduling School of Isy. E. Georgia Tech, Atlanta, GA 30332 (1992b).  
  20. P. Whittle, Multi-armed bandits and the Gittins index. J. Roy. Statist. Soc. Sect. B42 (1980) 143-149.  Zbl0439.90096

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.