A Survey and Experimental Comparison of Service-Level-Approximation Methods for Nonstationary M(t)/M/s(t) Queueing Systems with Exhaustive Discipline

摘要

We compare the performance of seven methods in computing or approximating service levels for nonsta-tionary M(t)/M/s(t) queueing systems: an exact method (a Runge-Kutta ordinary-differential-equation solver), the randomization method, a closure (or surrogate-distribution) approximation, a direct infinite-server approximation, a modified-offered-load infinite-server approximation, an effective-arrival-rate approximation, and a lagged stationary approximation. We assume an exhaustive service discipline, where service in progress when a server is scheduled to leave is completed before the server leaves. We used all of the methods to solve the same set of 640 test problems. The randomization method was almost as accurate as the exact method and used about half the computational time. The closure approximation was less accurate, and usually slower, than the randomization method. The two infinite-server-based approximations, the effective-arrival-rate approximation, and the lagged stationary approximation were less accurate but had computation times that were far shorter and less problem-dependent than the other three methods.