Estimate average number of jobs in a dynamic system

Question

Suppose we have a system like this: We have one processor to process multiple tasks. The tasks keep arriving and the processor processes the tasks in parallel using a time-sharing manner. That is to say, if there is $n$ tasks in the system, then each task will share $\frac{1}{n}$ maximum processor's processing speed(using time-sharing technology). After finishing processing, the task will depart from the system.

Now suppose that the arrival of the tasks follows a poisson process with a parameter $\lambda$ in each time slot, and the processing time of each job follows a exponential distribution with parameter $n\mu$, where the $\mu$ is the mean of processing time and $n$ is the number of the tasks in the system(the more tasks you have in the system, the more time to finish one task). I want to do an estimation of the average number of tasks in the system.

It is like the $M/M/1$ queuing system but a little different. Though the serving rate is $\mu$ overall, but the tasks are processed in parallel so that there is no queue.

Let me know if you have any question.

Answer 1

It is a CTMC on the state space $\{ 0,1,\dots,n \}$ with transition rates $q_{i,i+1}=\lambda$ for $i<n$, $q_{i,i-1}=i\mu$ for $i>0$, else $q_{i,j}=0$ for $i \neq j$. The long time estimate of the average number of jobs in the system is just the average state under the invariant distribution i.e.

$$\sum_{i=0}^n i \pi_i$$

where $\pi$ is the normalized solution to $\pi Q=0$. This can be directly tackled numerically, for example in Matlab:

Q=zeros(n+1,n+1);
for i=2:n
  Q(i,i-1)=(i-1)*mu;
  Q(i,i+1)=lambda;
  Q(i,i)=-((i-1)*mu+lambda);
end
Q(1,2)=lambda;
Q(1,1)=-lambda;
Q(n+1,n)=n*mu;
Q(n+1,n+1)=-n*mu;
[V,E]=eig(Q');
k=find(abs(diag(E))<eps);
p=V(:,k)';
p=p/sum(p);
p*(0:n)'

It can also be handled analytically through the usual framework of birth-death processes. The idea here is to recursively solve the detailed balance equations $\pi_i \lambda_i = \pi_{i+1} \mu_{i+1}$ so that in this case $\pi_{i+1}=\frac{\lambda}{(i+1)\mu} \pi_i$ for $i=0,1,\dots,n-1$. Taking $\pi_0=1$ to start gives you the right quantity up to normalization, and then you normalize it after you finish solving the recurrence.

If I misunderstood the problem and it is possible for the system to have a queue if jobs arrive too fast (but the processing rate still maxes out at $n \mu$), then that can be handled too (it is just a birth-death process on countably many states).