Un ordonnancement dynamique de tâches stochastiques sur un seul processeur
RAIRO - Operations Research - Recherche Opérationnelle, Tome 36 (2002) no. 4, pp. 365-373.

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.

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.

@article{RO_2002__36_4_365_0,
     author = {Derbala, Ali},
     title = {Un ordonnancement dynamique de t\^aches stochastiques sur un seul processeur},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {365--373},
     publisher = {EDP-Sciences},
     volume = {36},
     number = {4},
     year = {2002},
     doi = {10.1051/ro:2003010},
     mrnumber = {1997930},
     zbl = {1037.90036},
     language = {fr},
     url = {http://www.numdam.org/articles/10.1051/ro:2003010/}
}
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
SP  - 365
EP  - 373
VL  - 36
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro:2003010/
DO  - 10.1051/ro:2003010
LA  - fr
ID  - RO_2002__36_4_365_0
ER  - 
%0 Journal Article
%A Derbala, Ali
%T Un ordonnancement dynamique de tâches stochastiques sur un seul processeur
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2002
%P 365-373
%V 36
%N 4
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro:2003010/
%R 10.1051/ro:2003010
%G fr
%F RO_2002__36_4_365_0
Derbala, Ali. Un ordonnancement dynamique de tâches stochastiques sur un seul processeur. RAIRO - Operations Research - Recherche Opérationnelle, Tome 36 (2002) no. 4, pp. 365-373. doi : 10.1051/ro:2003010. http://www.numdam.org/articles/10.1051/ro:2003010/

[1] S. Browne et U. Yechiali, Scheduling deteriorating jobs on a single processor. Oper. Res. 38 (1990) 495-498. | Zbl

[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. | MR | Zbl

[3] J.C. Gittins et K.D. Glazebrook, On Bayesian models in stochastic scheduling. J. Appl. Probab. 14 (1977) 556-565. | MR | Zbl

[4] J.C. Gittins, Bandit process and dynamic allocation indices. J. Roy. Statist. Soc. Sect. B 41 (1979a) 148-177. | MR | Zbl

[5] J.C. Gittins et D.M. Jones, A dynamic allocation index for the discounted multiarmed bandit problem. Biometrika 66 (1979b) 561-565.

[6] J.C. Gittins, Multi armed Bandit allocation indices. John Wiley & Sons (1989). | MR | Zbl

[7] K.D. Glazebrook, Stochastic scheduling, Ph.D. Thesis. Downing College, Cambridge (1976). | MR

[8] K.D. Glazebrook, Myopic strategies for Bayesian models in stochastic scheduling. Oper. Res. 19 (1982) 160-170. | MR | Zbl

[9] K.D. Glazebrook, Optimal strategies for families of alternative bandit processes. IEEE Trans. Automat. Control AC-28 (1983) 858-861. | MR | Zbl

[10] K.D. Glazebrook, Evaluating the effects of machine breakdowns in stochastic scheduling problems. Naval Res. Logist. Quarterly 34 (1987) 319-335. | MR | Zbl

[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. B 42 (1980) 165-169. | MR | Zbl

[14] D.R. Robinson, Algorithms for evaluating the dynamic allocation index. Oper. Res. Lett. 1 (1982) 72-74. | Zbl

[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. | MR | Zbl

[17] W.E. Smith, Various optimizers for single state production. Naval Res. Logist. Quarterly 3 (1956) 59-66. | MR

[18] G. Weiss, Turnpike optimality of Smith's rule in parallel machines stochastic scheduling. Math. Oper. Res. 17 (1992a) 255-270. | Zbl

[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. B 42 (1980) 143-149. | MR | Zbl

Cité par Sources :