Consider I have $n$ mail boxes $\{m_1, m_2, \dots, m_n \}$. Messages come to each box at different rate/sec e.g., mail box $n$ has an arrival rate of messages equal say 5 per second. In general, let the set $a = \{a_1, a_2, a_3, \dots, a_n\}$ denotes the arrival rate of messages into each of the mail boxes respectively.
Now suppose that I have mail workers that can pick up and process messages at uniform rate of say $x$ message/sec (suppose for example $x=10 $ message/sec)?
How many (minimum) mail workers do I need, so that no message waiting time in the system is more than say 2 seconds (generally $s$ seconds)?
Constraint: every mail box should be assigned to only one mail worker, but a mail worker can be responsible of many mail boxes?
I believe the problem looks similar to bin packing (online)? if that is true what is the best known approximation algorithm for the online and offline bin packing cases?
Thank you.
This is indeed the offline bin packing problem. The "bins" here are the mail workers with size $x$, and the items are the mail boxes, with size $a_i$. The observation here is that if the total message rate of the mail boxes assigned to a given worker exceeded $x$, then the letters would start to pile up and sooner or later the waiting time would exceed $s$ seconds for some letter. In this way the condition that letters can wait some amount of time is immaterial. (Unless there is a point $t$ in time when letters stop arriving. But this does not change the problem in a substantial way: we only have to increase the bin sizes from $x$ to $x + s/t$.)
The wikipedia page has some nice tables to summarize various algorithms. It's difficult to say what the best algorithm is, because it depends on what your criterium is – "worst-case" or "asymptotic" approximation ratio? Additive gap? The "first-fit decreasing" algorithm is really simple and performs well.