# Estimating customer waiting time and server idle time on a finite horizon, stochastic, single-server queue

I am working on a problem of scheduling appointments for a stochastic, single-server queue. There are $n$ customers who each have independent, randomly distributed service durations $Z_i$. The customers are assigned appointment times $x_i$ where $x_i<x_j$ for $i<j$. An appointment schedule is some $\mathbf{x}=\langle x_1,\ldots,x_N\rangle$ where $x_i>0$.

Customer 1 arrives at time $x_i$ and is immediately served; the duration of his service is unknown until he is actually served and represented by $Z_1$. Customer 2 arrives at time $x_2>x_1$ and is served as soon as is available (after Customer 1 has been served); his service takes $Z_2$. Customer 3 arrives at $x_3>x_2$, etc.

The waiting time for customer $i$ is given by $W_i=\max\{X_{i-1}+W_{i-1}+Z_{i-1}-X_i,0\}$ and the server idle time immediate prior to Customer $i$ being served is $S_i=\max\{-X_{i-1}-W_{i-1}-Z_{i-1}+X_i,0\}$.

In my application, I need to approximate $\text{E}(W_i)$ and $\text{E}(S_i)$ for many (millions) of different schedules. The service time distributions ($Z_i$) are the same for every schedule.

Currently, I'm doing a naive Monte Carlo simulation: sample scenarios ($\mathbf{z}=\langle z_1,\ldots,z_N\rangle$) from the service distributions, compute the waiting time and idle times for each scenario, and average the results. However, this method has proven to be slower than I'd like. I can increase the speed by reducing the number of scenarios and increasing the number of estimates, but I haven't been able to find the right balance.

I'm looking for suggestions on speeding up this computation.

-
Since you're simulating, you must know all the distributions... what are they? Also, is your traffic intensity high (say, > 0.9?) –  jbowman Aug 20 '12 at 20:17
@jbowman: I'm interested in testing under a variety of distributions and intensities. Trying to keep this as general as possible. –  Tim Hopper Aug 21 '12 at 0:07
Ah, I see. Have you tried characterizing schedules by their mean and variance of interarrival time and using the G/G/1 heavy traffic approximations? (just a thought...) –  jbowman Aug 21 '12 at 1:30