Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2024-12-26T09:32:44.806Z Has data issue: false hasContentIssue false
  • English
  • Français

On the stationary workload distribution of work-conserving single-server queues: a general formula via stochastic intensity

Part of: Special processes

Published online by Cambridge University Press:  14 July 2016

Naoto Miyoshi
Naoto Miyoshi*
Affiliation:
Tokyo Institute of Technology
*
∗ Postal address: Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, Tokyo 152-8552, Japan. Email address: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

It is well known that a simple closed-form formula exists for the stationary distribution of the workload in M/GI/1 queues. In this paper, we extend this to the general stationary framework. Namely, we consider a work-conserving single-server queueing system, where the sequence of customers’ arrival epochs and their service times is described as a general stationary marked point process, and we derive a closed-form formula for the stationary workload distribution. The key to our proof is two-fold: one is the Palm-martingale calculus, that is, the connection between the notion of Palm probability and that of stochastic intensity. The other is the preemptive-resume last-come, first-served discipline.

Keywords

Work-conserving single-server queuesstationary workload distributionPalm-martingale calculusstochastic intensity kernelLCFS-PR discipline

MSC classification

Primary: 60K25: Queueing theory
Type
Short Communications
Information
Journal of Applied Probability , Volume 38 , Issue 3 , September 2001 , pp. 793 - 798
Copyright
Copyright © by the Applied Probability Trust 2001 

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.)

References

Baccelli, F. and Brémaud, P. (1994). Elements of Queueing Theory: Palm-Martingale Calculus and Stochastic Recurrences. Springer, Berlin.Google Scholar
Brémaud, P. (1981). Point Processes and Queues: Martingale Dynamics. Springer, New York.Google Scholar
Brémaud, P. (1989). Characteristics of queueing systems observed at events and the connection between stochastic intensity and Palm probability. Queueing Systems 5, 99–112.CrossRefGoogle Scholar
Guillemin, F., and Mazumdar, R. (1995). Excursions of the workload process in G/GI/1 queues. Stoch. Proc. Appl. 58, 139–154.Google Scholar
Kelly, F. (1979). Reversibility and Stochastic Networks. John Wiley, Chichester.Google Scholar
Last, G., and Brandt, A. (1995). Marked Point Processes on the Real Line: The Dynamic Approach. Springer, New York.Google Scholar
Loynes, R. (1962). The stability of queues with non-independent inter-arrival and service times. Proc. Camb. Phil. Soc. 58, 497–520.Google Scholar
Melamed, B., and Whitt, W. (1990). On arrivals that see time averages: a martingale approach. J. Appl. Prob. 27, 376–384.Google Scholar
Papangelou, F. (1972). Integrability of expected increments and a related random change of time scale. Trans. Amer. Math. Soc. 165, 483–506.CrossRefGoogle Scholar
Prabhu, N. (1997). Foundations of Queueing Theory. Kluwer, Boston.CrossRefGoogle Scholar
Sigman, K. (1996). Queues under preemptive LIFO and ladder height distributions for risk processes: a duality. Commun. Statist. Stoch. Models 12, 725–735.CrossRefGoogle Scholar
Takine, T. (2000). Matrix product-form solution for an LCFS-PR single-server queue with multiple arrival streams governed by a Markov chain. Tech. Rept 2000-003, Department of Applied Mathematics and Physics, Kyoto University.Google Scholar
Yamazaki, G. (1990). Invariance relations in single-server queues with LCFS service discipline. Ann. Inst. Statist. Math. 42, 475–488.CrossRefGoogle Scholar