# Minimum total waiting time for arrivals/durations

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?

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: