Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-25T06:06:18.598Z Has data issue: false hasContentIssue false
  • English
  • Français

On stability of queueing networks with job deadlines

Part of: Special processes Operations research and management science

Published online by Cambridge University Press:  14 July 2016

Amy R. Ward  and
Nicholas Bambos
Amy R. Ward*
Affiliation:
Georgia Institute of Technology
Nicholas Bambos*
Affiliation:
Stanford University
*
∗ Postal address: School of Industrial Engineering, Georgia Institute of Technology, Atlanta, GA 30332-0205, USA. Email address: [email protected]
∗∗ Postal address: Department of Management Science and Engineering and Department of Electrical Engineering, Stanford University, Stanford, CA 94305, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper, we consider a single-server queue with stationary input, where each job joining the queue has an associated deadline. The deadline is a time constraint on job sojourn time and may be finite or infinite. If the job does not complete service before its deadline expires, it abandons the queue and the partial service it may have received up to that point is wasted. When the queue operates under a first-come-first served discipline, we establish conditions under which the actual workload process—that is, the work the server eventually processes—is unstable, weakly stable, and strongly stable. An interesting phenomenon observed is that in a nontrivial portion of the parameter space, the queue is weakly stable, but not strongly stable. We also indicate how our results apply to other nonidling service disciplines. We finally extend the results for a single node to acyclic (feed-forward) networks of queues with either per-queue or network-wide deadlines.

Keywords

Deadlinesabandonmentsrenegingimpatiencestability

MSC classification

Primary: 60K25: Queueing theory
Secondary: 90B15: Network models, stochastic
Type
Research Papers
Information
Journal of Applied Probability , Volume 40 , Issue 2 , June 2003 , pp. 293 - 304
Copyright
Copyright © Applied Probability Trust 2003 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

Research supported in part by the National Science Foundation.

References

Afanaséeva, L. G. (1965). On the existence of a limit distribution in queueing systems with bounded sojourn time. Teor. Veroyat. Primen. 10, 570–578. English traslation: Theor. Prob. Appl.Google Scholar
Anantharam, V., and Konstantopoulos, T. (1997). Stationary solutions of stochastic recursions describing discrete event systems. Stoch. Process. Appl. 68, 181–194.CrossRefGoogle Scholar
Anantharam, V., and Konstantopoulos, T. (1999). A correction and some additional remarks on: stationary solutions of stochastic recursions describing discrete event systems. Stoch. Process. Appl. 80, 271–278.Google Scholar
Asmussen, S. (1987). Applied Probability and Queues. John Wiley, New York.Google Scholar
Baccelli, F. and Brémaud, P. (1987). Palm Probabilities and Stationary Queues (Lecture Notes Statist. 41). Springer, Berlin.Google Scholar
Baccelli, F. and Brémaud, P. (1994) Elements of Queueing Theory. Springer, New York.Google Scholar
Baccelli, F., Boyer, P., and Hebuterne, G. (1984). Single-server queues with impatient customers. Adv. Appl. Prob. 16, 887–905.Google Scholar
Daley, D. J. (1965). General customer impatience in the queue GI/G/1. J. Appl. Prob. 2, 186–205.Google Scholar
Franken, P., Konig, D., Arndt, U., and Schimdt, V. (1982). Queues and Point Processes. John Wiley, Chichester.Google Scholar
Kovalenko, I. N. (1965). Some queueing problems with restrictions. Theory Prob. Appl. 6, 204–208.CrossRefGoogle Scholar
Lindley, D. V. (1952). The theory of queues with a single server. Proc. Camb. Phil. Soc. 48, 277–289.Google Scholar
Lillo, R. E., and Martin, M. (2001). Stability in queues with impatient customers. Stoch. Models 17, 375–389.Google Scholar
Loynes, R. M. (1962). The stability of a queue with non-independent inter-arrival and service times. Proc. Camb. Phil. Soc. 58, 497–520.CrossRefGoogle Scholar
Matthes, K., Kerstan, J., and Mecke, J. (1978). Infinitely Divisible Point Processes. John Wiley, Chichester.Google Scholar
Palm, C. (1937). Étude des delais d'attente. Ericsson Technics 5, 37–56.Google Scholar
Sigman, K. (1995). Stationary Marked Point Processes. Chapman and Hall, New York.Google Scholar
Stanford, R. E. (1979). Reneging phenomena in single channel queues. Math. Operat. Res. 4, 162–178.Google Scholar