The last of three servers
Three jobs start at the same time on three machines. Their durations are independent and exponentially distributed with mean hour.
Find the expected time, in hours, until all three jobs are finished.
Fractions, decimals with at least 3 significant digits, and expressions such as sqrt(2)/2, e^-1 or pi/4.
Look at the times between consecutive finishes. While jobs are still running, how long until the next one finishes?
The minimum of independent exponentials with rate is exponential with rate . And because exponentials are memoryless, the jobs still running “restart” at each finish.
h
s Shown after a correct answer. Revealing it first marks the problem as seen, not solved.
Idea. Split the waiting time into the gaps between successive finishes. Thanks to the memoryless property, each gap is a fresh minimum of exponentials, whose mean is easy.
Step 1: the first gap. With jobs running, the first finish happens at the minimum of independent variables, which is , with mean .
Step 2: the next gaps. At that moment, the other two jobs have been running for a while, but by memorylessness their remaining durations are again independent . So the next gap is , with mean , and the last one is , with mean .
Step 3: add.
In general. The maximum of independent variables has mean . Waiting for the slowest of machines costs about times the mean job length.