The M/PH 2/1 Queue: Explicit Distributions, Sojourn Times and Numerical Benchmarks

summary

The gist

Two-phase phase-type (P H2) service distributions are widely used in call center, healthcare and manufacturing models…

In short

The paper derives explicit closed-form formulas for steady-state queue-length distributions ($p_n = A_1r^{n_1} + A_2r^{n_2}$) and sojourn-time densities ($f_{Ws}(t) = c_1e^{\alpha_1t} + c_2e^{\alpha_2t}$) for the complete M/PH 2/1 family of service systems. This provides ready-to-use analytical tools, enabling exact sensitivity analysis and optimization that are difficult to obtain using only numerical simulations.

Key concepts

Phase-Type (PH) Distributions
These distributions model service times that can take on a variety of specific, discrete values rather than just continuous ones. They are used in complex systems like call centers or manufacturing where service processes have distinct stages or patterns, allowing for more detailed statistical modeling.
Pollaczek–Khinchine (PK) Formula
This is a foundational formula used to find the generating function for the steady-state queue-length distribution in queueing theory. It links the system's arrival and service rates to how many customers are waiting in line at any given time.
Matrix–Spectral Tradition
This approach uses linear algebra, specifically eigenvalue decomposition of a rate matrix (R), to derive the same results as the PK formula. It provides an alternative mathematical framework for analyzing phase-type queues by focusing on the system's rate structure.

Terminology used across episodes

This episode discusses

The paper

The M/PH 2/1 Queue: Explicit Distributions, Sojourn Times and Numerical Benchmarks · Read on arXiv

Yossi Luzon

School of Industrial Engineering and Management, AFEKA – The Tel Aviv Academic College of Engineering

Two-phase phase-type (PH 2) distributions are among the service-time models used most often in applied queueing, because they capture coefficients of variation above and below one with few parameters. This note collects, in one place and in ready-to-use form, the stationary queue-length distribution p n = A 1 r 1 n + A 2 r 2 n and the sojourn-time density f W s(t) = c 1 e α 1 t + c 2 e α 2 t for the M/E 2/1, M/Hypo 2/1, M/Hyper 2/1 and M/Coxian 2/1 queues, with every coefficient written in the parameters that a fitting procedure returns. None of these results is new in substance; however, obtaining them from the general theory takes work that each user would otherwise have to repeat. The formulas are obtained from the Pollaczek-Khinchine transforms, related to the matrix-geometric and phase-type representations of the same queues, and verified numerically in 40-digit arithmetic. The note also gives the matrices needed to reproduce the results in standard software, a comparison with the matrix-analytic library BuTools, formulas for tail and threshold quantities and their derivatives, and a worked example calibrated to published surgical-time data.

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: We're looking at the paper: "The M/PH 2/1 Queue".

Paper summary: Tom: So to summarize this paper, "The M/PH two/one Queue: Explicit Distributions, Sojourn Times and Numerical Benchmarks," the main thesis is that they provide explicit closed-form distributions for all four two-phase phase-type service models: Erlang-two hypoexponential-two hyperexponential-two and Coxian-two > <ref:2608.06414#pg1,Erlang-2, hypoexponential-2, hyperexponential-2, and Coxian-2>

Jane: They claim to derive the queue length distribution as pn equals A1 r to n one plus A2 r to n two and the sojourn time density as fWs t equals c1 e alpha one t plus c2 e alpha two t >

Lu: The authors argue that they achieve this by combining both the scalar transform tradition, using the Pollaczek–Khinchine formula, with a matrix-spectral approach based on eigenvalue decomposition of the rate matrix >

Meng: They claim this results in ready-to-use formulas where every coefficient is given as an explicit function of system parameters and consolidated in reference tables >

Tom: The real significance they point to is that because these are functions rather than just numerical values, they support analytical operations like exact sensitivity derivatives and closed-form threshold optimization >

Jane: So, instead of just running a simulation to guess how sensitive the results are to a parameter change, you can calculate it exactly using these formulas >

Lalam: They also prove that the two-phase phase-type queues mark the boundary of algebraic tractability >

Conclusion: Tom: Looking at "The M/PH two/one Queue: Explicit Distributions, Sojourn Times and Numerical Benchmarks," the authors Yossi Luzon put out these explicit formulas for the queue length distribution and sojourn times for all four models > <ref:2608.06414#pg1>

Jane: What does that mean in simple terms for someone listening? It means that if you are designing a system where service times can be described by those two-phase behaviors—like a patient waiting in a hospital or a call center agent being busy—you have the math to calculate exactly what the queue looks like and how long things will take >

Lu: The implication is that researchers and practitioners who model service systems with these two-phase distributions now have access to ready-to-use formulas for queue length, sojourn times, tail probabilities, and sensitivity measures >

Meng: For me at the operational level, it means we can move beyond just running models to having a mathematical backbone for designing better capacity sizing based on exact distribution properties >

Lalam: The work essentially serves as that reference point because it gives these people the formulas they need when they are trying to model service systems with two-phase distributions >

More episodes

← Home