Algorithm to process jobs with same priority

Question

Hi Guys,

I am solving exercise problems from a book called Algorithms by Papadimitrou and Vazirani.

The following is the question:

A server has n customers waiting to be served. The service time required by each customer is known in advance: it is ti minutes for customer i. So if, for example, the customers are served in order of increasing i, then the ith customer has to wait for Sum(j = 1 to n) tj minutes.

We wish to minimize the total waiting time. Give an efficient algorithm for the same.

My Attempt:

I thought of a couple of approaches but couldnt decide which is best or any other approach that beats mine.

Approach 1:

Serve them in Round Robin fashion with time slice as 5. However, when i need to be more careful when deciding the time slice. It shouldnt be too high or low. So, i thought of selecting the time slice as the average of serving times.

Approach 2: Assume jobs are sorted according to the time they take and are stored in an array A[1...n]

First serve A[1] then A[n] then A[2] then A[n-1] and so on.

I cant really decide which will be a more optimal solution for this problem. Am i missing something.

Thanks, Chander

Answer 1

Let me assume the "total waiting time" is the sum of the time each customer waits before the server finish serving him/her, and assume the customers are served in order of increasing i, so customer C1 waits t1 minutes, customer C2 waits t1+t2 minutes, and customer C3 waits t1+t2+t3 minutes, and ... customer Cn waits t1+t2+...+t{n-1}+tn minutes.

or:

C1 waits: t1
C2 waits: t1+t2
C3 waits: t1+t2+t3
...
Cn waits: t1+t2+t3+...tn

The total waiting time is n*t1+(n-1)*t2+...n*tn

Again, this is based on the assumption that the customers are served in order of increasing i.

Now, which customer do you want to server first?

Answer 2

You can solve this problem by adding the sorting part and improvising on your Round robin approach,

First sort the customers based on service time

Now instead of just giving each customer a time slice t in round robin manner, you can also check if the customer has less than t/2 remaining time, if so complete his task

So for each customer in sorted list from first server customer for time t if his remaining time is < t/2 then complete his service now else move to next customer