nach oben

Queueing Systems

Erschienen in:

01.11.2013

On queues with impatience: stability, and the optimality of Earliest Deadline First

verfasst von: Pascal Moyal

Erschienen in: Queueing Systems | Ausgabe 2-4/2013

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In this paper, we consider a queue with impatient customers, under general assumptions. We introduce a convenient representation of the system by a stochastic recursive sequence keeping track of the remaining service and patience times of the customers. This description allows us (i) to provide a comprehensive stability condition in the general case, (ii) to give a rigorous proof of the optimality of the Earliest Deadline First (EDF) service discipline in several cases, and (iii) to show that the abandonment probability of the system follows inversely the stochastic ordering of the generic patience time distribution.

Vorheriger Artikel Workload and busy period for with a general impatience mechanism

Nächster Artikel Gaussian skewness approximation for dynamic rate multi-server queues with abandonment

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nur mit Berechtigung zugänglich

Notice that the result presented in [1] only concerns GI/GI/1 queues. However, it should be clear that this also holds true whenever the inter-arrival times are not independent of one another, but only independent of the service times. Indeed, even in that case any permutation of the service times clearly do not affect the global statistics of the system, provided that the arrival times and patience times are left unchanged, and that the service discipline is independent of the service times.

Baccelli, F., Brémaud, P.: Elements of Queueing Theory, 2nd edn. Springer, Berlin (2002)

Baccelli, F., Hébuterne, G.: On queues with impatient customers. In: Performance’81, pp. 159–179 (1981)

Baccelli, F., Boyer, P., Hébuterne, G.: Single-server queues with impatient customers. Adv. Appl. Probab. 16(4), 887–905 (1984)CrossRef

Barrer, D.Y.: Queuing with impatient customers and ordered service. Oper. Res. 5, 650–656 (1957)CrossRef

Borovkov, A.A., Foss, S.: Stochastic recursive sequences and their generalizations. Sib. Adv. Math. 2(1), 16–81 (1992)

Borovkov, A.A., Foss, S.: Two ergodicity criteria for stochastically recursive sequences. Acta Appl. Math. 34, 125–134 (1994)CrossRef

Decreusefond, L., Moyal, P.: The fluid limit of a heavily loaded EDF queue with impatient customers. Markov Process. Relat. Fields 14(1), 131–158 (2008)

Decreusefond, L., Moyal, P.: Stochastic Modeling and Analysis of Telecom Networks. Wiley-ISTE (2012)

Decreusefond, L., Moyal, P.: A functional central limit theorem for the M/GI/\(\infty \) queue. Ann. Appl. Probab. 18(6), 2156–2178 (2008)CrossRef

10.

Dertouzos, M.: Control robotics: the procedural control of physical processus. Proc. IFIP Congress (1974)

11.

Doytchinov, B., Lehoczky, J.P., Shreve, S.: Real-time queues in heavy-traffic with earliest deadline first queue discipline. Ann. Appl. Probab. 11(2), 332–378 (2001)CrossRef

12.

Flipo, D.: Comparaison des disciplines de service des files d’attente G/G/1 (in french). Annales de l’institut Henri Poincaré, Section B 17(2), 190–197 (1981)

13.

Gromoll, C., Puha, A., Williams, R.: The fluid limit of a heavily loaded processor sharing queue. Ann. Appl. Probab. 12, 797–859 (2002)CrossRef

14.

Gromoll, C., Robert, Ph., Zwart, B.: Fluid limits for processor sharing queues with impatience. Math. Oper. Res. 33, 375–402 (2008). (2006), no. 34(1)

15.

Jackson, J.R.: Scheduling a production line to minimize maximum tardiness. Res. Rep. 43, Management Sci. Rep. Univ. of Calif., Los Angeles (1955)

16.

Kruk, L., Lehoczky, J., Ramanan, K., Shreve, S.: Heavy traffic analysis for EDF queues with reneging. Ann. Appl. Probab. 21(2), 484–545 (2011)CrossRef

17.

Liu, C.L., Layland, J.W.: Scheduling algorithms for multiprogramming in a hard real-time environment. J. Assoc. Comput. Mach. 20(1), 46–61 (1973)CrossRef

18.

Loynes, R.M.: The stability of queues with non-independent interarrivals and service times. Proce. Cambridge Philos. Soc. 58, 497–520 (1962)CrossRef

19.

Moyal, P.: Stability of a processor sharing queue with varying throughput. Journ. Appl. Probab. 45(4), 953–962 (2008)CrossRef

20.

Moyal, P.: Convex comparison of service disciplines in Real-time queues. Oper. Res. Lett. 36(4), 496–499 (2008)CrossRef

21.

Moyal, P.: The queue with impatience: construction of the stationary workload under FIFO. J. Appl. Probab. 47(4), 498–512 (2010)CrossRef

22.

Panwar, S.S., Towsley, D.: Optimality of the stochastic earliest dead- line policy for the G/M/c queue serving customers with deadlines. Second ORSA Telecommunications Conference, Boca Raton (March 1992)

23.

Panwar, S.S., Towsley, D., Wolf, J.K.: Optimal scheduling policies for a class of queues with customer deadlines to the beginning of service. J. ACM. 35(4), 832–844 (1988)CrossRef

24.

Pinedo, M.: Stochastic scheduling with release dates and due dates. Oper. Res. 31, 559–572 (1983)CrossRef

25.

Sorenson, P.G., Hamacher, V.C.: A real-time system design methodology. INFOR 13(1), 1–18 (1975)

26.

Stoyenko, A.D., Georgiadis, L.: On optimal lateness and tardiness scheduling in real-time systems. Computing 47, 215–234 (1992)CrossRef

27.

Thorisson, H.: Coupling, Stationarity and Regeneration. Springer, Berlin (2000)CrossRef

Titel: On queues with impatience: stability, and the optimality of Earliest Deadline First
verfasst von: Pascal Moyal
Publikationsdatum: 01.11.2013
Verlag: Springer US
Erschienen in: Queueing Systems / Ausgabe 2-4/2013
Print ISSN: 0257-0130
Elektronische ISSN: 1572-9443
DOI: https://doi.org/10.1007/s11134-013-9342-1

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 2-4/2013

Gaussian skewness approximation for dynamic rate multi-server queues with abandonment

Introduction: queueing systems special issue on queueing systems with abandonments

Data-stories about (im)patient customers in tele-queues

Dynamic scheduling of a GI/GI/1+GI queue with multiple customer classes

Abandonment versus blocking in many-server queues: asymptotic optimality in the QED regime

Erratum to: Data-stories about (im)patient customers in tele-queues