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

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.
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.   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.  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.   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.  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.  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.  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.   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.   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.   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, 6751 (2011), 14.   Google Scholar

[13]

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

[14]

D. Ngoduy, Derivation of continuum traffic model for weaving sections on freeways,, Transportmetrica, 2 (2006), 199.   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).   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.  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, 4 (2006), 59.   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.   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.   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.  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.   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.  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.  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.  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.   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.   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.   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, 6751 (2011), 14.   Google Scholar

[13]

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

[14]

D. Ngoduy, Derivation of continuum traffic model for weaving sections on freeways,, Transportmetrica, 2 (2006), 199.   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).   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.  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, 4 (2006), 59.   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.   Google Scholar

[1]

Antonio Rieser. A topological approach to spectral clustering. Foundations of Data Science, 2021  doi: 10.3934/fods.2021005

[2]

Guillaume Bal, Wenjia Jing. Homogenization and corrector theory for linear transport in random media. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1311-1343. doi: 10.3934/dcds.2010.28.1311

[3]

Felix Finster, Jürg Fröhlich, Marco Oppio, Claudio F. Paganini. Causal fermion systems and the ETH approach to quantum theory. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : 1717-1746. doi: 10.3934/dcdss.2020451

[4]

Vieri Benci, Sunra Mosconi, Marco Squassina. Preface: Recent progresses in the theory of nonlinear nonlocal problems. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : i-i. doi: 10.3934/dcdss.2020446

[5]

Rafael Luís, Sandra Mendonça. A note on global stability in the periodic logistic map. Discrete & Continuous Dynamical Systems - B, 2020, 25 (11) : 4211-4220. doi: 10.3934/dcdsb.2020094

[6]

Lakmi Niwanthi Wadippuli, Ivan Gudoshnikov, Oleg Makarenkov. Global asymptotic stability of nonconvex sweeping processes. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1129-1139. doi: 10.3934/dcdsb.2019212

[7]

Jaume Llibre, Luci Any Roberto. On the periodic solutions of a class of Duffing differential equations. Discrete & Continuous Dynamical Systems - A, 2013, 33 (1) : 277-282. doi: 10.3934/dcds.2013.33.277

[8]

Lekbir Afraites, Abdelghafour Atlas, Fahd Karami, Driss Meskine. Some class of parabolic systems applied to image processing. Discrete & Continuous Dynamical Systems - B, 2016, 21 (6) : 1671-1687. doi: 10.3934/dcdsb.2016017

[9]

Graziano Crasta, Philippe G. LeFloch. Existence result for a class of nonconservative and nonstrictly hyperbolic systems. Communications on Pure & Applied Analysis, 2002, 1 (4) : 513-530. doi: 10.3934/cpaa.2002.1.513

[10]

W. Cary Huffman. On the theory of $\mathbb{F}_q$-linear $\mathbb{F}_{q^t}$-codes. Advances in Mathematics of Communications, 2013, 7 (3) : 349-378. doi: 10.3934/amc.2013.7.349

[11]

Carlos Gutierrez, Nguyen Van Chau. A remark on an eigenvalue condition for the global injectivity of differentiable maps of $R^2$. Discrete & Continuous Dynamical Systems - A, 2007, 17 (2) : 397-402. doi: 10.3934/dcds.2007.17.397

[12]

Bernold Fiedler, Carlos Rocha, Matthias Wolfrum. Sturm global attractors for $S^1$-equivariant parabolic equations. Networks & Heterogeneous Media, 2012, 7 (4) : 617-659. doi: 10.3934/nhm.2012.7.617

[13]

Manoel J. Dos Santos, Baowei Feng, Dilberto S. Almeida Júnior, Mauro L. Santos. Global and exponential attractors for a nonlinear porous elastic system with delay term. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2805-2828. doi: 10.3934/dcdsb.2020206

[14]

Jianping Gao, Shangjiang Guo, Wenxian Shen. Persistence and time periodic positive solutions of doubly nonlocal Fisher-KPP equations in time periodic and space heterogeneous media. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2645-2676. doi: 10.3934/dcdsb.2020199

[15]

Zhouxin Li, Yimin Zhang. Ground states for a class of quasilinear Schrödinger equations with vanishing potentials. Communications on Pure & Applied Analysis, 2021, 20 (2) : 933-954. doi: 10.3934/cpaa.2020298

[16]

Jean-François Biasse. Improvements in the computation of ideal class groups of imaginary quadratic number fields. Advances in Mathematics of Communications, 2010, 4 (2) : 141-154. doi: 10.3934/amc.2010.4.141

[17]

Samir Adly, Oanh Chau, Mohamed Rochdi. Solvability of a class of thermal dynamical contact problems with subdifferential conditions. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 91-104. doi: 10.3934/naco.2012.2.91

[18]

Shiqiu Fu, Kanishka Perera. On a class of semipositone problems with singular Trudinger-Moser nonlinearities. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : 1747-1756. doi: 10.3934/dcdss.2020452

[19]

John Leventides, Costas Poulios, Georgios Alkis Tsiatsios, Maria Livada, Stavros Tsipras, Konstantinos Lefcaditis, Panagiota Sargenti, Aleka Sargenti. Systems theory and analysis of the implementation of non pharmaceutical policies for the mitigation of the COVID-19 pandemic. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021004

[20]

Cécile Carrère, Grégoire Nadin. Influence of mutations in phenotypically-structured populations in time periodic environment. Discrete & Continuous Dynamical Systems - B, 2020, 25 (9) : 3609-3630. doi: 10.3934/dcdsb.2020075

2019 Impact Factor: 1.366

Metrics

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

[Back to Top]