I am trying to understand the solution of sum of completion times. I found the following stuff in the link:
Prompt Scheduling for Selfish Agents
Paper says:
Consider the case of a single queue, a selfish agent will simply join the queue immediately upon arrival, there is no reason to delay. Thus, jobs will be processed in first-in-first-out (FIFO) order. However, this may be quite bad in terms of the sum of completion times. Imagine a job with processing time L, arriving at time zero, followed by sqrt(L) jobs of length 1, all of which arrive immediately after the first. As the first job will only be done at time L, the sum of completion times for these 1 +sqrt(L) jobs is about L^(3/2)
I can’t understand how this value of L^(3/2) is obtained.
Is it simply:
L + L^(1/2)
Somebody please guide me.
Zulfi.
The length-$L$ job obviously has a turnaround time (enqueue-to-done-processing) of $L$. The first length-$1$ job has a turnaround time of $L+1$, the second $L+2$ and so on, up to $L+\sqrt L$ for the last job. The aforementioned sum of completion times is $$L+(L+1)+(L+2)+\dots+(L+\sqrt L)\sim L\sqrt L+\frac{\sqrt L(\sqrt L+1)}2\sim L^{3/2}$$