American Institute of Mathematical Sciences

Advanced
January  2014, 10(1): 193-206. doi: 10.3934/jimo.2014.10.193

A continuous-time queueing model with class clustering and global FCFS service discipline

Willem Mélange 1, , Herwig Bruneel 2, , Bart Steyaert 1, , Dieter Claeys 1, and  Joris Walraevens 2,

1. 

Department of Telecommunications and Information Processing, Ghent University - UGent, Sint-Pietersnieuwstraat 41, 9000 Ghent, Belgium, Belgium, Belgium
2. 

Department of Telecommunications and Information Processing, Ghent University, St-Pietersnieuwstraat 41, 9000 Gent

Received  September 2012 Revised  June 2013 Published  October 2013

In this paper the focus is on ``class clustering" in a continuous-time queueing model with two classes and dedicated servers. ``Class clustering" means that customers of any given type may (or may not) have a tendency to ``arrive back-to-back". We believe this is a concept that is often neglected in literature and we want to show that it can have a considerable impact on multiclass queueing systems, especially on the system considered in this paper. This system adopts a ``global FCFS" service discipline, i.e., all arriving customers are accommodated in one single FCFS queue, regardless of their types. The major aim of our paper is to quantify the intuitively expected (due to the service discipline) negative impact of ``class clustering" on the performance measures of our system. The motivation of our work are systems where this kind of inherent blocking is encountered, such as input-queueing network switches, road splits or security checks at airports.
Keywords: Queueing theory, class clustering, continuous time., global FCFS.
Mathematics Subject Classification: Primary: 60K25, 90B20; Secondary: 60J2.
Citation: Willem Mélange, Herwig Bruneel, Bart Steyaert, Dieter Claeys, Joris Walraevens. A continuous-time queueing model with class clustering and global FCFS service discipline. Journal of Industrial & Management Optimization, 2014, 10 (1) : 193-206. doi: 10.3934/jimo.2014.10.193
References:
[1]

I. Adan, T. de Kok and J. Resing, A multi-server queueing model with locking, EJOR, 116 (2000), 16-26. Google Scholar

[2]

I. J. B. F. Adan, J. Wessels and W. H. M. Zijm, A compensation approach for two-dimensional markov processes, Advances in Applied Probability, 25 (1993), 783-817. doi: 10.2307/1427792.  Google Scholar

[3]

P. Beekhuizen and J. Resing, Performance analysis of small non-uniform packet switches, Performance Evaluation, 66 (2009), 640-659. Google Scholar

[4]

Z. Berdowski, F. van den Broek-Serlé, J. Jetten, Y. Kawabata, J. Schoemaker and R. Versteegh, Survey on standard weights of passengers and baggage, Survey. EASA 2008.C.06/30800/R20090095/30800000/FBR/RLO, (2009). Google Scholar

[5]

D. Bertsimas, An exact fcfs waiting time analysis for a general class of G/G/s queueing systems, Queueing Systems Theory Appl., 3 (1988), 305-320. doi: 10.1007/BF01157853.  Google Scholar

[6]

D. Bertsimas, An analytic approach to a general class of G/G/s queueing systems, Operations Research, 38 (1990), 139-155. doi: 10.1287/opre.38.1.139.  Google Scholar

[7]

P. P. Bocharov and C. D'Apice, "Queueing Theory," Walter de Gruyter, 2004. Google Scholar

[8]

W. Grassmann, Real eigenvalues of certain tridiagonal matrix polynomials, with queueing applications, Linear Algebra and its Applications, 342 (2002), 93-106. doi: 10.1016/S0024-3795(01)00462-1.  Google Scholar

[9]

M. Karol, M. Hluchyj and S. Morgan, Input versus output queueing on a space-division packet switch, IEEE Transactions on Communications, 35 (1987), 1347-1356. Google Scholar

[10]

K. Laevens, A processor-sharing model for input-buffered ATM-switches in a correlated traffic environment, Microprocessors and Microsystems, 22 (1999), 589-596. Google Scholar

[11]

S. Liew, Performance of various input-buffered and output-buffered ATM switch design principles under bursty traffic: Simulation study, IEEE Transactions on Communications, 42 (1994), 1371-1379. Google Scholar

[12]

W. Mélange, H. Bruneel, B. Steyaert and J. Walraevens, A two-class continuous-time queueing model with dedicated servers and global fcfs service discipline, In "Analytical and Stochastic Modeling Techniques and Applications," Lecture Notes in Computer Science, Springer Berlin / Heidelberg, 6751 (2011), 14-27. Google Scholar

[13]

M. F. Neuts, "Matrix-Geometric Solutions in Stochastic Models: An Algorithmic Approach," Corrected reprint of the 1981 original. Dover Publications, Inc., New York, 1994.  Google Scholar

[14]

D. Ngoduy, Derivation of continuum traffic model for weaving sections on freeways, Transportmetrica, 2 (2006), 199-222. Google Scholar

[15]

R. Nishi, H. Miki, A. Tomoeda and K. Nishinari, Achievement of alternative configurations of vehicles on multiple lanes, Physical Review E, 79 (2009), 066119. Google Scholar

[16]

A. Stolyar, MaxWeight scheduling in a generalized switch: State space collapse and workload minimization in heavy traffic, Annals of Applied Probability, 14 (2004), 1-53. doi: 10.1214/aoap/1075828046.  Google Scholar

[17]

T. Van Woensel and N. Vandaele, Empirical validation of a queueing approach to uninterrupted traffic flows, 4OR, A Quarterly Journal of Operations Research, 4 (2006), 59-72. Google Scholar

[18]

T. Van Woensel and N. Vandaele, Modeling traffic flows with queueing models: A review, Asia-Pacific Journal of Operational Research, 24 (2007), 435-461. Google Scholar

show all references

References:
[1]

I. Adan, T. de Kok and J. Resing, A multi-server queueing model with locking, EJOR, 116 (2000), 16-26. Google Scholar

[2]

I. J. B. F. Adan, J. Wessels and W. H. M. Zijm, A compensation approach for two-dimensional markov processes, Advances in Applied Probability, 25 (1993), 783-817. doi: 10.2307/1427792.  Google Scholar

[3]

P. Beekhuizen and J. Resing, Performance analysis of small non-uniform packet switches, Performance Evaluation, 66 (2009), 640-659. Google Scholar

[4]

Z. Berdowski, F. van den Broek-Serlé, J. Jetten, Y. Kawabata, J. Schoemaker and R. Versteegh, Survey on standard weights of passengers and baggage, Survey. EASA 2008.C.06/30800/R20090095/30800000/FBR/RLO, (2009). Google Scholar

[5]

D. Bertsimas, An exact fcfs waiting time analysis for a general class of G/G/s queueing systems, Queueing Systems Theory Appl., 3 (1988), 305-320. doi: 10.1007/BF01157853.  Google Scholar

[6]

D. Bertsimas, An analytic approach to a general class of G/G/s queueing systems, Operations Research, 38 (1990), 139-155. doi: 10.1287/opre.38.1.139.  Google Scholar

[7]

P. P. Bocharov and C. D'Apice, "Queueing Theory," Walter de Gruyter, 2004. Google Scholar

[8]

W. Grassmann, Real eigenvalues of certain tridiagonal matrix polynomials, with queueing applications, Linear Algebra and its Applications, 342 (2002), 93-106. doi: 10.1016/S0024-3795(01)00462-1.  Google Scholar

[9]

M. Karol, M. Hluchyj and S. Morgan, Input versus output queueing on a space-division packet switch, IEEE Transactions on Communications, 35 (1987), 1347-1356. Google Scholar

[10]

K. Laevens, A processor-sharing model for input-buffered ATM-switches in a correlated traffic environment, Microprocessors and Microsystems, 22 (1999), 589-596. Google Scholar

[11]

S. Liew, Performance of various input-buffered and output-buffered ATM switch design principles under bursty traffic: Simulation study, IEEE Transactions on Communications, 42 (1994), 1371-1379. Google Scholar

[12]

W. Mélange, H. Bruneel, B. Steyaert and J. Walraevens, A two-class continuous-time queueing model with dedicated servers and global fcfs service discipline, In "Analytical and Stochastic Modeling Techniques and Applications," Lecture Notes in Computer Science, Springer Berlin / Heidelberg, 6751 (2011), 14-27. Google Scholar

[13]

M. F. Neuts, "Matrix-Geometric Solutions in Stochastic Models: An Algorithmic Approach," Corrected reprint of the 1981 original. Dover Publications, Inc., New York, 1994.  Google Scholar

[14]

D. Ngoduy, Derivation of continuum traffic model for weaving sections on freeways, Transportmetrica, 2 (2006), 199-222. Google Scholar

[15]

R. Nishi, H. Miki, A. Tomoeda and K. Nishinari, Achievement of alternative configurations of vehicles on multiple lanes, Physical Review E, 79 (2009), 066119. Google Scholar

[16]

A. Stolyar, MaxWeight scheduling in a generalized switch: State space collapse and workload minimization in heavy traffic, Annals of Applied Probability, 14 (2004), 1-53. doi: 10.1214/aoap/1075828046.  Google Scholar

[17]

T. Van Woensel and N. Vandaele, Empirical validation of a queueing approach to uninterrupted traffic flows, 4OR, A Quarterly Journal of Operations Research, 4 (2006), 59-72. Google Scholar

[18]

T. Van Woensel and N. Vandaele, Modeling traffic flows with queueing models: A review, Asia-Pacific Journal of Operational Research, 24 (2007), 435-461. Google Scholar

[1]

Zaidong Zhan, Shuping Chen, Wei Wei. A unified theory of maximum principle for continuous and discrete time optimal control problems. Mathematical Control & Related Fields, 2012, 2 (2) : 195-215. doi: 10.3934/mcrf.2012.2.195
[2]

Hideaki Takagi. Unified and refined analysis of the response time and waiting time in the M/M/m FCFS preemptive-resume priority queue. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1945-1973. doi: 10.3934/jimo.2017026
[3]

Wei Feng, Xin Lu. Global periodicity in a class of reaction-diffusion systems with time delays. Discrete & Continuous Dynamical Systems - B, 2003, 3 (1) : 69-78. doi: 10.3934/dcdsb.2003.3.69
[4]

Hal L. Smith, Horst R. Thieme. Persistence and global stability for a class of discrete time structured population models. Discrete & Continuous Dynamical Systems, 2013, 33 (10) : 4627-4646. doi: 10.3934/dcds.2013.33.4627
[5]

Nan Chen, Cheng Wang, Steven Wise. Global-in-time Gevrey regularity solution for a class of bistable gradient flows. Discrete & Continuous Dynamical Systems - B, 2016, 21 (6) : 1689-1711. doi: 10.3934/dcdsb.2016018
[6]

Zsolt Saffer, Wuyi Yue. A dual tandem queueing system with GI service time at the first queue. Journal of Industrial & Management Optimization, 2014, 10 (1) : 167-192. doi: 10.3934/jimo.2014.10.167
[7]

Sofian De Clercq, Koen De Turck, Bart Steyaert, Herwig Bruneel. Frame-bound priority scheduling in discrete-time queueing systems. Journal of Industrial & Management Optimization, 2011, 7 (3) : 767-788. doi: 10.3934/jimo.2011.7.767
[8]

Yoshiaki Kawase, Shoji Kasahara. Priority queueing analysis of transaction-confirmation time for Bitcoin. Journal of Industrial & Management Optimization, 2020, 16 (3) : 1077-1098. doi: 10.3934/jimo.2018193
[9]

Astridh Boccabella, Roberto Natalini, Lorenzo Pareschi. On a continuous mixed strategies model for evolutionary game theory. Kinetic & Related Models, 2011, 4 (1) : 187-213. doi: 10.3934/krm.2011.4.187
[10]

Luis Barreira, César Silva. Lyapunov exponents for continuous transformations and dimension theory. Discrete & Continuous Dynamical Systems, 2005, 13 (2) : 469-490. doi: 10.3934/dcds.2005.13.469
[11]

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
[12]

Wei Feng, Xin Lu. Global stability in a class of reaction-diffusion systems with time-varying delays. Conference Publications, 1998, 1998 (Special) : 253-261. doi: 10.3934/proc.1998.1998.253
[13]

Tomáš Gedeon. Attractors in continuous –time switching networks. Communications on Pure & Applied Analysis, 2003, 2 (2) : 187-209. doi: 10.3934/cpaa.2003.2.187
[14]

Vladimir V. Chepyzhov, Monica Conti, Vittorino Pata. A minimal approach to the theory of global attractors. Discrete & Continuous Dynamical Systems, 2012, 32 (6) : 2079-2088. doi: 10.3934/dcds.2012.32.2079
[15]

Joon Kwon, Panayotis Mertikopoulos. A continuous-time approach to online optimization. Journal of Dynamics & Games, 2017, 4 (2) : 125-148. doi: 10.3934/jdg.2017008
[16]

Alain Bensoussan, Sonny Skaaning. Base stock list price policy in continuous time. Discrete & Continuous Dynamical Systems - B, 2017, 22 (1) : 1-28. doi: 10.3934/dcdsb.2017001
[17]

Simone Göttlich, Stephan Martin, Thorsten Sickenberger. Time-continuous production networks with random breakdowns. Networks & Heterogeneous Media, 2011, 6 (4) : 695-714. doi: 10.3934/nhm.2011.6.695
[18]

Hanqing Jin, Xun Yu Zhou. Continuous-time portfolio selection under ambiguity. Mathematical Control & Related Fields, 2015, 5 (3) : 475-488. doi: 10.3934/mcrf.2015.5.475
[19]

Ellen Baake, Michael Baake, Majid Salamat. The general recombination equation in continuous time and its solution. Discrete & Continuous Dynamical Systems, 2016, 36 (1) : 63-95. doi: 10.3934/dcds.2016.36.63
[20]

Ludovic Tangpi. Efficient hedging under ambiguity in continuous time. Probability, Uncertainty and Quantitative Risk, 2020, 5 (0) : 6-. doi: 10.1186/s41546-020-00048-9

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (210)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences