I am currently studying about (non)preemptive priority queue, and below are some problems that I am getting stuck on. Hope somebody could give me some help on any of these problems.

  1. Customers arrive to a single customer service agent according to a Poisson process with arrival rate $\lambda = 9$ per hour. $80\%$ of customers complete a standard transaction that takes a fixed amount of time, $\frac{1}{12}$ hour. $20\%$ of customers require special handling and take an exponential amount of time with mean $\frac{1}{6}$ hours. Determine the average wait in queue for standard-transaction customers when customers are first-come, first served.

  2. A computer processer handles incoming jobs according to a non-preemptive priority queue discipline. Jobs arrive according to a Poisson process with rate 8 per minute. $80\%$ of jobs take $1/60$ min to process, $10\%$ take $1/12$ min to process, and $10\%$ take 1 minute to process. Determine the average time in queue for each class if the rule applied is Longest job first? How about the average time in queue if first-come, first-served is applied?

My thought: For $(1)$, what caused me a lot of difficulty is the fact that the two service distributions are not both exponential. I know that if both services are exponential, then we only need to compute $L_q = L_{q_1}+L_{q_2} = \lambda (\frac{\lambda_1}{u_1} + \frac{\lambda_2}{u_2})/(1- \frac{\lambda_1}{u_1} + \frac{\lambda_2}{u_2})$. Then dividing this by $\lambda_1$ (is this correct?) to get the result?

For $(2)$, I am completely stuck since I simply don't know the formula for the rule Longest job first. For shortest job first, the formula is: Average waiting in queue of class-x customer = $W_q^{x} = \frac{\lambda E[S^2]}{2(1-\sigma_x)^2}$ where $\sigma_x = \sum_{i=1}^{x} \rho_i$ = total load rate of all jobs less than $x$.

  • $\begingroup$ Do you know the M/G/1 queue formula? That is all that is needed for problem (1). For problem (2), you will need to use the extended formula for multi-class M/G/1 queues with nonpreemptive priority (in this specific case you have 3 classes of traffic, each class having deterministic service times with class-dependent durations). [For both problems, you will need to assume that successive job types are chosen in an i.i.d. manner with the given probabilities.] $\endgroup$ – Michael Apr 7 '17 at 20:18
  • $\begingroup$ @Michael: thank you very much for your help. Could you show me how you would determine the service rate in problem (1) (I don't think we can simply add the two service rates up, can we?) and the formula to find $L_q^{1}$ or $W_q^{1}$, where the exponent $1$ stands for queue of standard-transaction customers. For Problem (2)< the way I solved it is using $W_q^{i} = \frac{\lambda E[S^2]}{2(1-\sigma_i)(1-\sigma_{i-1})}$. Now, $\sigma_3 = \rho_3$ only, because longest job is processed first, $\sigma_2 =\rho_2 +\rho_3$, and $\sigma_1 =\rho_1 +\rho_2+\rho_3$. Is this a correct way to solve $(2)$? $\endgroup$ – user177196 Apr 8 '17 at 1:06
  • $\begingroup$ @Michael: you meant using P-K formula like: $W=\frac{\lambda E(S^2)}{2(1-\rho)}$, where $\rho = \rho_1 + \rho_2 = 7.2/12 + 1.8/6 = 0.9$? But how to find $W_q^{1}$ then? $\endgroup$ – user177196 Apr 8 '17 at 1:19
  • $\begingroup$ For problem 1, Poisson arrivals see time averages (PASTA). So both types of arrivals see, on average, the same unfinished work in the system when they arrive, and hence have the same average queueing delay (recall this is FCFS). Just compute $\overline{W}_q$ and it is the same for both type 1 and type 2. You can find the service time distribution by using the law of total probabilty. You are correctly approaching problem 2, but you need to compute the numerator. $\endgroup$ – Michael Apr 8 '17 at 2:12
  • 1
    $\begingroup$ Chapter 3 here is a good reference for queueing theory (see equations (3.41) and (3.42) for M/G/1): web.mit.edu/dimitrib/www/datanets.html $\endgroup$ – Michael Apr 8 '17 at 7:42

Your Answer

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

Browse other questions tagged or ask your own question.