Second Derivative Sample Path Estimators for the GI/G/m Queue

Applying the technique of smoothed perturbation analysis (SPA) to the GI/G/m queue with first-come, first-served (FCFS) queue discipline, we derive sample path estimators for the second derivative of mean steady-state system time with respect to a parameter of the service time distribution. Such estimators provide a possible means for speeding up the convergence of gradient-based stochastic optimization algorithms. The derivation of the estimators sheds some new light on the complications encountered in applying the technique of SPA. The most general cases require the simulation of additional sample subpaths; however, an approximation procedure is also introduced which eliminates the need for additional simulation. Simulation results indicate that the approximation procedure is reasonably accurate. When the service times are exponential or deterministic, the estimator simplifies and the approximation procedure becomes exact. For the M/M/2 queue, the estimator is proved to be strongly consistent.