7
$\begingroup$

I have a system with customers waiting in a queue to be serviced. Each customer will be serviced by a server out of a pool of servers $s$ which takes a fixed amount of time $r$ and I wish to calculate the size of the queue I will need to cope with all the customers.

At time $t=0$ the rate of customers arriving is 0 and the rate of customer arrivals will accelerate to $\lambda_{max}$ at $t=1$. After this point in time no further customers will be accepted into the queue.

All the resources I've been able to find have the average rate of customer arrivals being uniform over time with some sort of distribution. However the system I'm dealing with there is a deadline point and the rate of customers entering the system accelerates up to that point in time.

My question is three fold.

Is there a formulae for this problem?

What is the correct terminology to describe this sort of increasing traffic (so I can search for it and ask better questions)?

Are there reference materials (books/journals/papers etc) for queuing theory where a point in time is special?

$\endgroup$
  • $\begingroup$ What do you mean by deadline point? Does it mean that you have to serve all current customers queue in a certain time frame, or current as well as ongoing? $\endgroup$ – Teg Louis Jan 1 '18 at 0:06
  • $\begingroup$ Is this essentially the same as modelling Black Friday at Best Buy before the day ends? $\endgroup$ – Teg Louis Jan 1 '18 at 0:15
  • 1
    $\begingroup$ @TegLouis yes very simmilar to Best Buy before the day ends. Basically there is a point where all the customers want to get into the queue because after that point they will not get served. $\endgroup$ – Q the Platypus Jan 1 '18 at 6:27
  • $\begingroup$ This is an M/D/c queue with a nonhomogeneous $\lambda = \lambda(t)$ (You call this $\mu$). $\endgroup$ – Frank Vel Jan 1 '18 at 10:43
  • 1
    $\begingroup$ I am starting to wonder if I can get an approximate solution by treating this as a continuous problem. Consider the queue as being a tank with a fluid entering at one rate and draining at another. That way I can integrate both process to discover the volume and the difference between the two is the maximum queue size we will need. $\endgroup$ – Q the Platypus Jan 1 '18 at 23:52
0
$\begingroup$

You have not specified according to which law the customers arrive. Arrival rate $\lambda(t)$ is not enough.

I will give an answer to your question if the arrival flow is Poisson with rate $\lambda(t)$. This answer is not the best one in the sense that you can improve the estimations made below.

Let $A_{(0,1)}$ denote the number of arrivals in $(0,1)$. Then the probability $a_k=$ that during the time interval $(0,1)$ exactly $k$ customers arrive is $$ a_k=\mathbf{P}(A_{(0,1)}=k)= {1 \over k!} \left (\int_0^1 \lambda(t)dt \right )^k e^{- \int_0^1 \lambda(t)dt}, \ k \ge 0. $$

It is straighworward to check that the mean and variance of the number of arrivals in the interval $(0,1)$ is equal to $\int_0^1 \lambda(t)dt$. Recall the three-sigma rule: $$ \mathbf{P}(|A_{(0,1)}-\mathbf{E}[A_{(0,1)}]|<3\sqrt{\mathbf{Var}[A_{(0,1)}]})>{8\over 9}. $$

Note: since you know $ \int_0^1 \lambda(t)dt$ you can calculate the exact (not the lower bound) for the probaiblity on the left side of the inequality above.

Thus in practice the number of arrivals in $(0,1)$ is most likely to be less than $$ s^*=\mathbf{E}[A_{(0,1)}]+3\sqrt{\mathbf{Var}[A_{(0,1)}]}= \int_0^1 \lambda(t)dt+ 3 \sqrt{\int_0^1 \lambda(t)dt}. $$

Suppose that you system consists of $s$ servers and a queue o infinite capacity. Then in order not to have a queue (but only busy servers) at time $t=1$ you need $s\ge \left \lceil{s^*}\right \rceil $ servers. If $r>1$ then it is a reasonable answer. If $r<1$ then this answer may greatly overestimate the required number of servers.

$\endgroup$
  • $\begingroup$ You are solving the wrong problem. I don't want to know how many servers in order to get a 0 length queue. I want to know what the size of the queue will be given a number of servers and an r greatly lower then 1. $\endgroup$ – Q the Platypus Nov 7 '18 at 10:22
  • $\begingroup$ It is wrong to say "size of the queue at time t=1". The size of the queue is the random variable and thus you have only a probability that it takes some value at time t=1. Anyway, your new question is simpler than the one I answered. Just take the time-dependent solution for the number in the system in the M(t)/D/s queue and calculate any performance measure related to the queue size. $\endgroup$ – rrv Nov 7 '18 at 16:16

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.