Minimum total waiting time for arrivals/durations

Question

I have come up with the following problem, and cannot seem to find an effective way of solving it:

Consider $n$ clients arriving at a service point at time moments $\{a_i\}_{i=1}^n$ whose duration of service (by a single employee, let's say) is known to be $\{d_i\}_{i=1}^n$. Choose the turn of servicing them, such that the total sum of waiting times (i.e. if we consider $\{s_i\}_{i=1}^n$ the start-of-service time for each client, then the total waiting time would be $\sum\limits_{i=1}^n\{s_i-a_i\}$) is minimized.

The only difference in this problem to the Interval Scheduling that has a greedy method of selecting the earliest finish time first, is that here all clients have to be serviced. (whereas in the Interval Scheduling, some intervals may not be selected)

Is there an efficient greedy algo for this problem? Or isn't there? Many obvious or less obvious approaches do not seem to work, example with this:

• Client 1: arrival at 1, duration of 9
• Client 2: arrival at 2, duration of 13
• Client 3: arrival at 15, duration of $\epsilon$

The above example hints at choosing the smallest $a_i+d_i$ first, but I seem to be unable to prove this on an exchange argument... Is perhaps the problem NP-Complete?

Answer 1

Yes, this is NP-hard. Since neither the $a_i$ nor the $d_i$ depend on the solution, the problem is equivalent to the problem of minimizing the sum of the completion times of the requests, which is known in the scheduling literature as "$1|r_i|\sum C_i$" and is NP-hard. Reference:

J.K. Lenstra, A.H.G. Rinnooy Kan, and P. Brucker. Complexity of machine scheduling problems. Ann. of Discrete Math., 1:343-362, 1977.

Also, I disagree with the statement that "the only difference to Interval Scheduling is that here all clients have to be serviced". There is one more important difference: in Interval Scheduling, the algorithm can just accept or reject the clients, while in this problem, even after the algorithm accepts a client, it has to choose when to start it.