[isaacg]

There's a transition zone from "fast" to "slow" fluctuations around the mean waiting time that's more complicated and is an area of active research. If the fluctuations are 5x below the mean waiting time, I'd guess the effects of fluctuation will be gone.

Here's a recent paper on the topic, if you're interested in the cutting edge research: http://www.cs.cmu.edu/afs/cs.cmu.edu/user/harchol/www/Papers...

Thanks, I'm glad to hear you liked the Nudge result!

[mjb]

Thanks!

One more: my understanding is that in Nudge I need to know processing time, but in FCFS I don't. How sensitive is your optimality result to errors in processing time estimates (I don't recall this being covered in the paper, but if it is feel free to tell me).

In the cloud services and databases settings, we seldom have accurate processing time estimates until we're quite far down processing a request (post-auth, post-parse, at least, but also for databases post-query-plan).

[isaacg]

The only thing we use processing time for in the Nudge paper is to classify jobs as "Large", "Small" or "Other". If instead of exact processing times, we had estimates, the result would still work as long as a job that was estimated to large was typically longer than a job estimated to be small. So Nudge totally works in these more realistic settings.

If the estimates were super noisy, you might be better off using Nudge very sparingly, only when you're more confident about the relative sizes.