Minimizing Delays in the GI/G/1 Queue

What service-time distribution minimizes delays in a GI/G/1 queue with given renewal arrival process and given mean service time? It is natural to conjecture that the deterministic service-time distribution with unit mass on the mean is optimal for all objective functions of the form Ef(W) where f is a nondecreasing function of the steady-state delay W. However, we show that this conjecture is false. In fact, for hyperexponential interarrival-time distributions (mixtures of two exponential distributions), the service-time distribution minimizing the average delay maximizes the proportion of customers delayed.