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
    Please clarify what is the difference between $t(a_{i_{2}})$ and $t(a_{{2}})$? does the (i) subscript denote the serving clerk or queue for example?2011-12-29
  • 0
    @Emmad: I'd assume that the labels $a_1$ to $a_n$ have been assigned to the customers in advance, and we're to choose a permutation $i_1, \dotsc, i_n$ of $1, \dotsc, n$ so as to minimize the total waiting time as defined above.2011-12-29
  • 0
    @Ilmari Karonen, thanks for the clarification.2011-12-29

2 Answers 2