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},
     zbl = {1037.90036},
     mrnumber = {1997930},
     language = {fr},
     url = {http://www.numdam.org/articles/10.1051/ro:2003010/}
}
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 0703.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. | MR 370964 | Zbl 0303.62064

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

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

[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 996417 | Zbl 0699.90068

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

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

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

[10] K.D. Glazebrook, Evaluating the effects of machine breakdowns in stochastic scheduling problems. Naval Res. Logist. Quarterly 34 (1987) 319-335. | MR 888500 | Zbl 0648.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. B 42 (1980) 165-169. | MR 583351 | Zbl 0459.90087

[14] D.R. Robinson, Algorithms for evaluating the dynamic allocation index. Oper. Res. Lett. 1 (1982) 72-74. | Zbl 0488.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. | MR 339801 | Zbl 0271.68047

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

[18] G. Weiss, Turnpike optimality of Smith's rule in parallel machines stochastic scheduling. Math. Oper. Res. 17 (1992a) 255-270. | Zbl 0776.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. B 42 (1980) 143-149. | MR 583348 | Zbl 0439.90096