• Previous Article
    On the optimality of packet-oriented scheduling in photonic switches with delay lines
  • NACO Home
  • This Issue
  • Next Article
    Kronecker product-forms of steady-state probabilities with $C_k$/$C_m$/$1$ by matrix polynomial approaches
2011, 1(4): 713-725. doi: 10.3934/naco.2011.1.713

On the stationary LCFS-PR single-server queue: A characterization via stochastic intensity

1. 

Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, Tokyo 152-8552, Japan

Received  June 2011 Revised  July 2011 Published  November 2011

We consider a stationary single-server queue with preemptive-resume last-come, first-served (LCFS-PR) queueing discipline. The LCFS-PR single-server queue has some interesting properties and has been studied in the literature. In this paper, we generalize the previous results such that the input process to the queue is given as a general stationary marked point process and derive some formulas concerning the joint distribution of queue length and remaining service times of respective customers in the system at arbitrary time instances as well as at arrival instances. The tool for derivation is the Palm-martingale calculus; that is, the connection between the notion of Palm probability and that of stochastic intensity.
Citation: Naoto Miyoshi. On the stationary LCFS-PR single-server queue: A characterization via stochastic intensity. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 713-725. doi: 10.3934/naco.2011.1.713
References:
[1]

F. Baccelli and P. Brémaud, "Elements of Queueing Theory: Palm-Martingale Calculus and Stochastic Recurrences,'', 2nd edition, (2003).   Google Scholar

[2]

V. E. Beneš, On queues with Poisson arrivals,, Ann. Math. Statist., 28 (1957), 670.  doi: 10.1214/aoms/1177706878.  Google Scholar

[3]

P. Brémaud, "Point Processes and Queues: Martingale Dynamics,'', Springer-Verlag, (1981).   Google Scholar

[4]

P. Brémaud, Characteristics of queueing systems observed at events and the connection between stochastic intensity and Palm probability,, Queueing Systems Theory Appl., 5 (1989), 99.  doi: 10.1007/BF01149188.  Google Scholar

[5]

R. B. Cooper and S. C. Niu, Beneš's formula for M/G/1-FIFO ''explained'' by preemptive-resume LIFO,, J. Appl. Probab., 23 (1986), 550.  doi: 10.2307/3214199.  Google Scholar

[6]

D. Fakinos, The G/G/1 queueing system with a particular queue discipline,, J. Roy. Statist. Soc. Ser. B, 43 (1981), 190.   Google Scholar

[7]

D. Fakinos, The single-server queue with service depending on queue size with the preemptive-resume last-come-first-served queue discipline,, J. Appl. Probab., 24 (1987), 758.  doi: 10.2307/3214105.  Google Scholar

[8]

F. P. Kelly, The departure process from a queueing system,, Math. Proc. Cambridge Philos. Soc., 80 (1976), 283.  doi: 10.1017/S0305004100052919.  Google Scholar

[9]

R. M. Loynes, The stability of a queue with non-independent interarrival and service times,, Proc. Cambridge Philos. Soc., 58 (1962), 497.  doi: 10.1017/S0305004100036781.  Google Scholar

[10]

B. Melamed and W. Whitt, On arrivals that see time averages: A martingale approach,, J. Appl. Probab., 27 (1990), 376.  doi: 10.2307/3214656.  Google Scholar

[11]

N. Miyoshi, On the stationary workload distribution of work-conserving single-server queues: A general formula via stochastic intensity,, J. Appl. Probab., 38 (2001), 793.  doi: 10.1239/jap/1005091044.  Google Scholar

[12]

F. Papangelou, Integrability of expected increments of point processes and a related random change of scale,, Trans. Amer. Math. Soc., 165 (1972), 483.  doi: 10.1090/S0002-9947-1972-0314102-9.  Google Scholar

[13]

T. Takine, Matrix product-form solution for an LCFS-PR single-server queue with multiple arrival streams governed by a Markov chain,, Queueing Syst., 42 (2002), 131.  doi: 10.1023/A:1020152920794.  Google Scholar

[14]

G. Yamazaki, The GI/G/1 queue with last-come-first-served,, Ann. Inst. Statist. Math., 34 (1982), 599.  doi: 10.1007/BF02481057.  Google Scholar

[15]

G. Yamazaki, Invariance relations of GI/G/1 queueing systems with preemptive-resume last-come-first-served queue discipline,, J. Oper. Res. Soc. Japan, 27 (1984), 338.   Google Scholar

show all references

References:
[1]

F. Baccelli and P. Brémaud, "Elements of Queueing Theory: Palm-Martingale Calculus and Stochastic Recurrences,'', 2nd edition, (2003).   Google Scholar

[2]

V. E. Beneš, On queues with Poisson arrivals,, Ann. Math. Statist., 28 (1957), 670.  doi: 10.1214/aoms/1177706878.  Google Scholar

[3]

P. Brémaud, "Point Processes and Queues: Martingale Dynamics,'', Springer-Verlag, (1981).   Google Scholar

[4]

P. Brémaud, Characteristics of queueing systems observed at events and the connection between stochastic intensity and Palm probability,, Queueing Systems Theory Appl., 5 (1989), 99.  doi: 10.1007/BF01149188.  Google Scholar

[5]

R. B. Cooper and S. C. Niu, Beneš's formula for M/G/1-FIFO ''explained'' by preemptive-resume LIFO,, J. Appl. Probab., 23 (1986), 550.  doi: 10.2307/3214199.  Google Scholar

[6]

D. Fakinos, The G/G/1 queueing system with a particular queue discipline,, J. Roy. Statist. Soc. Ser. B, 43 (1981), 190.   Google Scholar

[7]

D. Fakinos, The single-server queue with service depending on queue size with the preemptive-resume last-come-first-served queue discipline,, J. Appl. Probab., 24 (1987), 758.  doi: 10.2307/3214105.  Google Scholar

[8]

F. P. Kelly, The departure process from a queueing system,, Math. Proc. Cambridge Philos. Soc., 80 (1976), 283.  doi: 10.1017/S0305004100052919.  Google Scholar

[9]

R. M. Loynes, The stability of a queue with non-independent interarrival and service times,, Proc. Cambridge Philos. Soc., 58 (1962), 497.  doi: 10.1017/S0305004100036781.  Google Scholar

[10]

B. Melamed and W. Whitt, On arrivals that see time averages: A martingale approach,, J. Appl. Probab., 27 (1990), 376.  doi: 10.2307/3214656.  Google Scholar

[11]

N. Miyoshi, On the stationary workload distribution of work-conserving single-server queues: A general formula via stochastic intensity,, J. Appl. Probab., 38 (2001), 793.  doi: 10.1239/jap/1005091044.  Google Scholar

[12]

F. Papangelou, Integrability of expected increments of point processes and a related random change of scale,, Trans. Amer. Math. Soc., 165 (1972), 483.  doi: 10.1090/S0002-9947-1972-0314102-9.  Google Scholar

[13]

T. Takine, Matrix product-form solution for an LCFS-PR single-server queue with multiple arrival streams governed by a Markov chain,, Queueing Syst., 42 (2002), 131.  doi: 10.1023/A:1020152920794.  Google Scholar

[14]

G. Yamazaki, The GI/G/1 queue with last-come-first-served,, Ann. Inst. Statist. Math., 34 (1982), 599.  doi: 10.1007/BF02481057.  Google Scholar

[15]

G. Yamazaki, Invariance relations of GI/G/1 queueing systems with preemptive-resume last-come-first-served queue discipline,, J. Oper. Res. Soc. Japan, 27 (1984), 338.   Google Scholar

[1]

Tuan Phung-Duc. Single server retrial queues with setup time. Journal of Industrial & Management Optimization, 2017, (3) : 1329-1345. doi: 10.3934/jimo.2016075

[2]

Yoshiaki Inoue, Tetsuya Takine. The FIFO single-server queue with disasters and multiple Markovian arrival streams. Journal of Industrial & Management Optimization, 2014, 10 (1) : 57-87. doi: 10.3934/jimo.2014.10.57

[3]

Tuan Phung-Duc, Wouter Rogiest, Sabine Wittevrongel. Single server retrial queues with speed scaling: Analysis and performance evaluation. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1927-1943. doi: 10.3934/jimo.2017025

[4]

Wai-Ki Ching, Sin-Man Choi, Min Huang. Optimal service capacity in a multiple-server queueing system: A game theory approach. Journal of Industrial & Management Optimization, 2010, 6 (1) : 73-102. doi: 10.3934/jimo.2010.6.73

[5]

Jinting Wang, Linfei Zhao, Feng Zhang. Analysis of the finite source retrial queues with server breakdowns and repairs. Journal of Industrial & Management Optimization, 2011, 7 (3) : 655-676. doi: 10.3934/jimo.2011.7.655

[6]

Wei Liu, Shiji Song, Cheng Wu. Single-period inventory model with discrete stochastic demand based on prospect theory. Journal of Industrial & Management Optimization, 2012, 8 (3) : 577-590. doi: 10.3934/jimo.2012.8.577

[7]

Dhanya Shajin, A. N. Dudin, Olga Dudina, A. Krishnamoorthy. A two-priority single server retrial queue with additional items. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-22. doi: 10.3934/jimo.2019085

[8]

Byeongchan Lee, Jonghun Yoon, Yang Woo Shin, Ganguk Hwang. Tail asymptotics of fluid queues in a distributed server system fed by a heavy-tailed ON-OFF flow. Journal of Industrial & Management Optimization, 2016, 12 (2) : 637-652. doi: 10.3934/jimo.2016.12.637

[9]

Ruiling Tian, Dequan Yue, Wuyi Yue. Optimal balking strategies in an M/G/1 queueing system with a removable server under N-policy. Journal of Industrial & Management Optimization, 2015, 11 (3) : 715-731. doi: 10.3934/jimo.2015.11.715

[10]

Dequan Yue, Wuyi Yue. Block-partitioning matrix solution of M/M/R/N queueing system with balking, reneging and server breakdowns. Journal of Industrial & Management Optimization, 2009, 5 (3) : 417-430. doi: 10.3934/jimo.2009.5.417

[11]

Sin-Man Choi, Ximin Huang, Wai-Ki Ching. Minimizing equilibrium expected sojourn time via performance-based mixed threshold demand allocation in a multiple-server queueing environment. Journal of Industrial & Management Optimization, 2012, 8 (2) : 299-323. doi: 10.3934/jimo.2012.8.299

[12]

Sofian De Clercq, Wouter Rogiest, Bart Steyaert, Herwig Bruneel. Stochastic decomposition in discrete-time queues with generalized vacations and applications. Journal of Industrial & Management Optimization, 2012, 8 (4) : 925-938. doi: 10.3934/jimo.2012.8.925

[13]

Hans Josef Pesch. Carathéodory's royal road of the calculus of variations: Missed exits to the maximum principle of optimal control theory. Numerical Algebra, Control & Optimization, 2013, 3 (1) : 161-173. doi: 10.3934/naco.2013.3.161

[14]

Shaojun Lan, Yinghui Tang, Miaomiao Yu. System capacity optimization design and optimal threshold $N^{*}$ for a $GEO/G/1$ discrete-time queue with single server vacation and under the control of Min($N, V$)-policy. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1435-1464. doi: 10.3934/jimo.2016.12.1435

[15]

Chanh Kieu, Quan Wang. On the scale dynamics of the tropical cyclone intensity. Discrete & Continuous Dynamical Systems - B, 2018, 23 (8) : 3047-3070. doi: 10.3934/dcdsb.2017196

[16]

Guangying Lv, Hongjun Gao, Jinlong Wei, Jiang-Lun Wu. The effect of noise intensity on parabolic equations. Discrete & Continuous Dynamical Systems - B, 2017, 22 (11) : 0-0. doi: 10.3934/dcdsb.2019248

[17]

Klaus Reiner Schenk-Hoppé. Random attractors--general properties, existence and applications to stochastic bifurcation theory. Discrete & Continuous Dynamical Systems - A, 1998, 4 (1) : 99-130. doi: 10.3934/dcds.1998.4.99

[18]

Zhongming Chen, Liqun Qi. Circulant tensors with applications to spectral hypergraph theory and stochastic process. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1227-1247. doi: 10.3934/jimo.2016.12.1227

[19]

Xiao-Qian Jiang, Lun-Chuan Zhang. A pricing option approach based on backward stochastic differential equation theory. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 969-978. doi: 10.3934/dcdss.2019065

[20]

Sandrine Anthoine, Jean-François Aujol, Yannick Boursier, Clothilde Mélot. Some proximal methods for Poisson intensity CBCT and PET. Inverse Problems & Imaging, 2012, 6 (4) : 565-598. doi: 10.3934/ipi.2012.6.565

 Impact Factor: 

Metrics

  • PDF downloads (11)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]