Multi-server $ M/M/c $ queueing systems exhibit the overtaking phenomenon, in which the randomness of service times causes the departure order to differ from the arrival order. The distribution of the number of overtakings is well known, and it is also well established that the mean number of customers being overtaken equals the mean number of overtakings. However, for the number of customers being overtaken, except for the case $ c = 2 $, neither its distribution nor even its variance has been reported in the literature. In this work, we derive the joint probability generating function for the number of times a customer overtakes others and is overtaken in an $ M/M/c $ queue with arbitrary $ c \ge 2 $. This joint probability generating function enables the derivation of formulas for higher-order joint moments of these two quantities and also allows numerical computation of their joint distribution via numerical inversion. In particular, we present recursive formulas for computing their variances and covariance and provide numerical examples illustrating both the joint moments and the joint distribution.
Citation: Wonjoong Kim, Bara Kim, Sung-Seok Ko. Joint Distribution of Overtaking and Being Overtaken in the M/M/c Queue[J]. Journal of Industrial and Management Optimization, 2026, 22(1): 486-503. doi: 10.3934/jimo.2026018
Multi-server $ M/M/c $ queueing systems exhibit the overtaking phenomenon, in which the randomness of service times causes the departure order to differ from the arrival order. The distribution of the number of overtakings is well known, and it is also well established that the mean number of customers being overtaken equals the mean number of overtakings. However, for the number of customers being overtaken, except for the case $ c = 2 $, neither its distribution nor even its variance has been reported in the literature. In this work, we derive the joint probability generating function for the number of times a customer overtakes others and is overtaken in an $ M/M/c $ queue with arbitrary $ c \ge 2 $. This joint probability generating function enables the derivation of formulas for higher-order joint moments of these two quantities and also allows numerical computation of their joint distribution via numerical inversion. In particular, we present recursive formulas for computing their variances and covariance and provide numerical examples illustrating both the joint moments and the joint distribution.
| [1] | G. Fayolle, R. A. Iasnogorodski, I. Mitrani, The distribution of sojourn times in a queueing network with overtaking: Reduction to a boundary problem, In Proceedings of the 9th International Symposium on Computer Performance Modelling, Measurement and Evaluation, 1983,477–486. https://dl.acm.org/doi/10.5555/647410.724711 |
| [2] |
W. Whitt, The Amount of Overtaking in a Network of Queues, Networks, 14 (1984), 411–426. https://doi.org/10.1002/net.3230140305 doi: 10.1002/net.3230140305
|
| [3] |
D. Bertsimas, G. Mourtzinou, A unified method to analyze overtake free queueing systems, Adv. Appl. Probab., 28 (1996), 588–625. https://doi.org/10.2307/1428073 doi: 10.2307/1428073
|
| [4] |
W. S. Kim, D. E. Lim, Analysis of overtaking in M/M/c queues, Comput. Ind. Eng., 101 (2016), 177–183. https://doi.org/10.1016/j.cie.2016.09.005 doi: 10.1016/j.cie.2016.09.005
|
| [5] |
H. Baumann, B. A. Neumann, The number of overtakes in an M/M/2 queue, Oper. Res. Perspect., 5 (2018), 280–287. https://doi.org/10.1016/j.orp.2018.09.001 doi: 10.1016/j.orp.2018.09.001
|
| [6] |
S. D. Clercq, B. Steyaert, S. Wittevrongel, H. Bruneel, Analysis of a discrete-time queue with time-limited overtake priority, Ann. Oper. Res., 238 (2016), 69–97. https://doi.org/10.1007/s10479-015-2000-8 doi: 10.1007/s10479-015-2000-8
|
| [7] | J. Erlichman, R. Hassin, Equilibrium solutions in the observable M/M/1 queue with overtaking, Proceedings of the fourth international ICST conference on performance evaluation methodologies and tools, 2009, 1–9. https://doi.org/10.4108/ICST.VALUETOOLS2009.8039 |
| [8] |
J. Erlichman, R. Hassin, Strategic overtaking in a monopolistic M/M/1 queue, IEEE Trans. Autom. Control, 60 (2015), 2189–2194. https://doi.org/10.1109/TAC.2015.2419151 doi: 10.1109/TAC.2015.2419151
|
| [9] | W. Sandmann, A discrimination frequency based queueing fairness measure with regard to job seniority and service requirement, Proceedings of the 1st EuroNGI Conference on Next Generation Internet, 2005,106–113. https://doi.org/10.1109/NGI.2005.1431654 |
| [10] |
B. A. Neumann, H. Baumann, The expected discrimination frequency for two-server queues, Oper. Res. Perspect., 5 (2018), 145–149. https://doi.org/10.1016/j.orp.2018.06.001 doi: 10.1016/j.orp.2018.06.001
|
| [11] |
J. Abate, W. Whitt, Numerical inversion of probability generating functions, Oper. Res. Lett., 12 (1992), 245–251. https://doi.org/10.1016/0167-6377(92)90050-D doi: 10.1016/0167-6377(92)90050-D
|
| [12] |
X. Jia, W. Hou, S. Z. Cao, W. J. Yan, C. Papadimitriou, Analytical hierarchical Bayesian modeling framework for model updating and uncertainty propagation utilizing frequency response function data, Comput. Meth. Appl. Mech. Eng., 447 (2025), 118341. https://doi.org/10.1016/j.cma.2025.118341 doi: 10.1016/j.cma.2025.118341
|
 jimo-22-01-018-s001.pdf |
 |
Figures(7)
Wonjoong Kim, Bara Kim, Sung-Seok Ko. Joint Distribution of Overtaking and Being Overtaken in the M/M/c Queue[J]. Journal of Industrial and Management Optimization, 2026, 22(1): 486-503. doi: 10.3934/jimo.2026018
DownLoad: