I am very beginner in Queueing Theory and I am learning in my own. I am struggling in the following situation.

Suppose in a service center if a job arrives it will immediately being processed if a server in the center is available. It is assumed that the center can place only up to three jobs in a queue to be processed when a server is available. If all the places in the queue are full then any new jobs are lost. Suppose that jobs arrive according to a Poisson process with intensity $\lambda=4$ per hour. Let the processing time of a server is exponentially distributed with parameter $\mu=2$. The cost of the server is $\$2$/hour to run a job when it is processing a job and cost nothing when the server is not processing any job. The cost of being a job in the queue is $\$s$/hour which is waiting to be served and if the job is processing then only the machine cost is charged (i.e., $\$2$/hour).

Consider $X(t)$ be the process denoting the number of jobs either being processed or waiting in the queue.

Now my confusions are:

  1. It is assumed that the center can place only up to three jobs in a queue. Does it mean in total the center can place four jobs where 3 are in queue and one is being processed? Or, does it mean the center can place just three jobs either being processed or in the queue? I mean whether there gonna be 4 states $(0,1,2,3)$ or 5 states $(0,1,2,3,4)$?

  2. How do we draw a diagram for the number of jobs at the center including the transition rates between the states (what are the states here) and what is the transition rate matrix for this model?

  3. How do we fix the stationary distribution of $X$?

  4. What is the long-term average total cost (machine cost + queue cost) for this model?

Thanks a lot!


It sounds like you are describing a $M/M/1/3$ system.

  1. Three in the queue and one in service sounds correct.

  2. State space is the total number in the system: (0,1,2,3,4), where 0 means no customers, 1 means one in service and empty queue, 2 means one in service and one in the queue and so on.

  3. This is a finite state, (0,1,2,3,4), birth and death process with constant rates $\lambda$ and $\mu$. Solving the balance equations is straightforward after you write them down. This can be found in any introductory book or lectures notes on continuous time Markov chains (such as Ross - Stochastic Processes).

  4. You know the cost of each of the possible five states, so after you compute the stationary distribution you can derive the long term expected cost.

  • $\begingroup$ @ Liron: Regarding the total cost I still do have some confusions. The cost of a job to be in queue is $\$s$/hour and while in processing it does cost $\$2$/hour. So, Cost of state $0=0$/hour; Cost of state $1=2$/hour; Cost of state $2=(2+s)$/hour; Cost of state $3=(2+2s)$/hour; Cost of state $4=(2+3s)$/hour; Then how do we compute the total cost? $\endgroup$ – user176667 Dec 12 '14 at 16:30
  • 1
    $\begingroup$ If $\pi_0,\ldots,\pi_4$ are the stationary probabilities then the expected long term cost is given by $\sum_{s=0}^4 \pi_s c(s)$, where $c(s)$ is the cost function as you specified it. $\endgroup$ – QQQ Dec 13 '14 at 18:09

Your Answer

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