0
$\begingroup$

I have a problem where I have a fixed number of N customers, and I have a number Q of queues and each queue serves the customers at different rates, so my question is, is there an algorithm, mathematical formula (or any method) to determine how many customers should I assign to each queue in order to minimize the serving time?

For example, let's say there are 1000 customers and Q1 with service rate of 2 customers per minute and Q2 with service rate of 3 customers per minute, in this case is easy to know that the fastest distribution is assign 400 customers to Q1 and 600 customers to Q2 and it will end in 20 minutes. But I need a way to determine the distribution when there is Q queues with different ratios.

Thank you.

$\endgroup$
0
$\begingroup$

The optimal solution occurs when each queue finishes processing its customers at the same time. To see why this is, consider the scenario where one queue finishes before another. The first queue could accommodate the latter's extra customers and finish faster than they would letting the customers stay in line. Suppose there are $k$ queues with a rate of $r_i$ customers per minute for the $i^{th}$ queue. If every queue works for one minute, then they can process $r_1+r_2+\cdots r_k$ customers. Let $R$ be this sum. Thus if you have $N$ customers, it will take $N/R$ minutes to process them if the queues work optimally. If $n_i$ is the number of customers assigned to the $i^{th}$ queue, then that queue will finish in $n_i/r_i$ minutes. Since the queue must finish at the same time as the others, we get $n_i/r_i = N/R$. Thus $$n_i = \frac{N\times r_i}{R}$$

is the number of customers assigned to queue $i$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.