2
$\begingroup$

Well I have a problem with a Christmas assignment and my teacher is not responding(maybe he is skiing somewhere now) so I will need some help.

The algorithm is about an office and the waiting time of the customers. We have one office that has to serve $n$ customers $a_1, a_2,\cdots ,a_n$. We assume that serving time $t(a_j)$ for each customer $a_j$ is known. Let $a_j$ to be served after $k$ customers $a_{i_{1}},a_{i_{2}},\cdots ,a_{i_{k}}$. His waiting time $T(a_j)$ is equal to

$T(a_j) = t(a_{i_{1}})+t(a_{i_{2}})+\cdots +t(a_{i_{k}})+t(a_{j})$

I want to an efficient algorithm that will compute the best way to serve in order to reduce the total waiting time.

$\sum_{j=1}^nT(a_j)$

My first thought is that the customers with the smallest serving time have to go first and the obvious solution is apply a sorting algorithm.

Am I wrong?

  • 0
    @Ilmari Karonen, thanks for the clarification.2011-12-29

2 Answers 2

2

Yes, serving the customers in ascending order of serving time is optimal.

To prove this, note that, if the customers are served in the order $a_{i_1}, a_{i_2}, \dotsc, a_{i_n}$ and if $t(a_{i_j}) > t(a_{i_{j+1}})$ for any $1 \le j < n$, then swapping the order of the customers $a_{i_j}$ and $a_{i_{j+1}}$ reduces the total waiting time by $t(a_{i_j}) - t(a_{i_{j+1}}) > 0$ time units.

  • 1
    This is a special case of [rearrangement inequality](http://en.wikipedia.org/wiki/Rearrangement_inequality) (where $y_i = i$)2011-12-30
1

Problems of this kind belong to the area of operations research known as scheduling problems (scheduling theory). Here is a short bibliography of books that deal with this topic: http://www.york.cuny.edu/~malk/biblio/scheduling2-biblio.html There is a lot of nice mathematics involved.