Please Help Me ! This Is Really Important

[dendio]

Hi all ,
This problem is really important.
I have to solve it.

Question : We have n customers. Customer i, 1 ≤ i ≤ n, requires a known service time ti. Without loss of generality, suppose the customers are numbered so that t1 ≤ t2 ≤ …….. ≤ tn . If there are s identical servers, prove experimentally as well as analytically that to minimize the total (and hence the average) time spent in the system by the customers, server j, 1 ≤ j ≤ s, should serve customers j, j+s, j+2s,……. in that order. (n >> s)

Experimental Design

 Assume that duration of ti is i.
1. Schedule the tasks as the priority given by < t1 , t2 , t3 , ………. , tn >
2. Schedule the tasks by the order of their random permutation.
3. Compute the total time of customers spent in the system.
4. Repeat Step 2, four times.
5. Find the minimum total time and its order.

[Yves M]

Please do some reading (http://www.codeguru.com/forum/showthread.php?t=366302).

[dendio]

If you help me about this problem , i will solve a big project but first the company gave me this problem...
PLEASE SOMEONE HELP ME...

[Yves M]

Well the issue is that you don't seem to have done much on it yourself yet. What specific part do you have problems with?

[dendio]

The problem is i did not understand the problem...
Can you write down the pseudocode or algorithm of this problem please ???

[Yves M]

What part of the problem don't you understand?

[riscutiavlad]

Given a number (s) of servers and a number (n) of client requests, each taking t(i) time when run on a server, what is the optimum scheduling for processing the requests so that the total time it takes to process each request is minimum.

Take into account that the actual time a client waits until its request is processed is the time it takes to process the request plus the time it takes to process all the previous requests on that server. This is pretty obvious.

The total time clients spend on the server is the sum of the time needed for each request.

Now, how can we arrange those requests so that the total time is minimum? Of course, process the requests that take less time earlier.

For example: we have two requests on one server. t(1) = 10 sec, t(2) = 30 sec
If we process them in this order: 1, 2
1 waits t(1) time until processed
2 waits t(1) + t(2) time until processed
So total time is: t(1) + t(1) + t(2) = 50 sec

If we process them ordered as 2, 1
1 waits t(2) + t(1) until processed
2 waits t(2) until processed
Total time is: t(2) + t(1) + t(2) = 70 sec

I hope by now you understand the question.

Now the solution is given to you: if server j processes the requests j, j+s, j+2s and so on, the optimal solution is achieved, meaning the total time will be the smallest.

You have to prove that this actually is the optimal solution.
Experimentally, you try different arrangements for the requests (random scheduling) and calculate the total time for the system. Eventually you will see that the scheduling provided as an optimal solution will indeed have the smallest total time.
Analytically, you must prove mathematically that the given solution is the optimal one.