Extreme values for the waiting time in large fork-join queues

Abstract We prove that the scaled maximum steady-state waiting time and the scaled maximum steady-state queue length among N GI/GI/1-queues in the N -server fork-join queue converge to a normally distributed random variable as $$N\rightarrow \infty $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>N</mml:mi> <mml:mo>→</mml:mo> <mml:mi>∞</mml:mi> </mml:mrow> </mml:math> . The maximum steady-state waiting time in this queueing system scales around $$\frac{1}{\gamma }\log N$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mfrac> <mml:mn>1</mml:mn> <mml:mi>γ</mml:mi> </mml:mfrac> <mml:mo>log</mml:mo> <mml:mi>N</mml:mi> </mml:mrow> </mml:math> , where $$\gamma $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>γ</mml:mi> </mml:math> is determined by the cumulant generating function $$\Lambda $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>Λ</mml:mi> </mml:math> of the service times distribution and solves the Cramér–Lundberg equation with stochastic service times and deterministic interarrival times. This value $$\frac{1}{\gamma }\log N$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mfrac> <mml:mn>1</mml:mn> <mml:mi>γ</mml:mi> </mml:mfrac> <mml:mo>log</mml:mo> <mml:mi>N</mml:mi> </mml:mrow> </mml:math> is reached at a certain hitting time. The number of arrivals until that hitting time satisfies the central limit theorem, with standard deviation $$\frac{\sigma _A}{\sqrt{\Lambda '(\gamma )\gamma }}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mfrac> <mml:msub> <mml:mi>σ</mml:mi> <mml:mi>A</mml:mi> </mml:msub> <mml:msqrt> <mml:mrow> <mml:msup> <mml:mi>Λ</mml:mi> <mml:mo>′</mml:mo> </mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>γ</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mi>γ</mml:mi> </mml:mrow> </mml:msqrt> </mml:mfrac> </mml:math> . By using the distributional form of Little’s law, we can extend this result to the maximum queue length. Finally, we extend these results to a fork-join queue with different classes of servers.