Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Queueing Systems
Published in: Queueing Systems 2-4/2013

01-11-2013

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

Author: Pascal Moyal

Published in: Queueing Systems | Issue 2-4/2013

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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.
previous article Workload and busy period for with a general impatience mechanism
next article Gaussian skewness approximation for dynamic rate multi-server queues with abandonment

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now
Appendix
Available only for authorised users
Footnotes
1
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.
 
Literature
1.
Baccelli, F., Brémaud, P.: Elements of Queueing Theory, 2nd edn. Springer, Berlin (2002)
2.
Baccelli, F., Hébuterne, G.: On queues with impatient customers. In: Performance’81, pp. 159–179 (1981)
3.
Baccelli, F., Boyer, P., Hébuterne, G.: Single-server queues with impatient customers. Adv. Appl. Probab. 16(4), 887–905 (1984)CrossRef
4.
Barrer, D.Y.: Queuing with impatient customers and ordered service. Oper. Res. 5, 650–656 (1957)CrossRef
5.
Borovkov, A.A., Foss, S.: Stochastic recursive sequences and their generalizations. Sib. Adv. Math. 2(1), 16–81 (1992)
6.
Borovkov, A.A., Foss, S.: Two ergodicity criteria for stochastically recursive sequences. Acta Appl. Math. 34, 125–134 (1994)CrossRef
7.
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)
8.
Decreusefond, L., Moyal, P.: Stochastic Modeling and Analysis of Telecom Networks. Wiley-ISTE (2012)
9.
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
Metadata
Title
On queues with impatience: stability, and the optimality of Earliest Deadline First
Author
Pascal Moyal
Publication date
01-11-2013
Publisher
Springer US
Published in
Queueing Systems / Issue 2-4/2013
Print ISSN: 0257-0130
Electronic ISSN: 1572-9443
DOI
https://doi.org/10.1007/s11134-013-9342-1

Other articles of this Issue 2-4/2013

Queueing Systems 2-4/2013 Go to the issue

OriginalPaper

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

OriginalPaper

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

Erratum

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

OriginalPaper

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

OriginalPaper

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

Editorial

Introduction: queueing systems special issue on queueing systems with abandonments

Premium Partner

    Image Credits