Analysis of transient queues with semidefinite optimization (Q1935509)

Upper bounds on the tail distribution of the waiting time \(W_n\) of customer \(n\) in the \(\mathrm{GI}/\mathrm{GI}/1\) queueing system are derived, using a limited number of the moments of the service times and that of the interarrival times. In particular, it is proved (using two first moments) that the asymptotics of the probability \(\operatorname{P}(W_n>y)\) as \(y \to \infty\) is proportional to \(n\) and \(1/y^2\). The upper bound on the tail probability of the maximum waiting time in the first busy period depending on the initial state is obtained. This then is used to derive an upper bound on the expected maximum of the waiting time during the first busy period. This bound is agreed with the well-known Kingman's bound. The main contribution of the paper is the application of the semidefinite programming approach, which is well-know technique in the area of optimization. Thus, this approach is an alternative to the known methods for deriving the bounds, such as Markov inequality, large deviations, Wald martingales. Some illustrative numerical results are given as well.