Question

Consider the priority queueing model of Section \(8.6 .2\) but now suppose that if a type 2 customer is being served when a type 1 arrives then the type 2 customer is bumped out of service. This is called the preemptive case. Suppose that when a bumped type 2 customer goes back in service his service begins at the point where it left off when he was bumped. (a) Argue that the work in the system at any time is the same as in the nonpreemptive case. (b) Derive \(W_{Q}^{1}\) Hint: How do type 2 customers affect type 1 s? (c) Why is it not true that $$ V_{Q}^{2}=\lambda_{2} E\left[S_{2}\right] W_{Q}^{2} $$ (d) Argue that the work seen by a type 2 arrival is the same as in the nonpreemptive case, and so \(W_{Q}^{2}=W_{Q}^{2}\) (nonpreemptive) \(+E[\) extra time \(]\) where the extra time is due to the fact that he may be bumped. (e) Let \(N\) denote the number of times a type 2 customer is bumped. Why is $$ E[\text { extra time } \mid \mathrm{N}]=\frac{N E\left[S_{1}\right]}{1-\lambda_{1} E\left[S_{1}\right]} $$ Hint: When a type 2 is bumped, relate the time until he gets back in service to a "busy period." (f) Let \(S_{2}\) denote the service time of a type \(2 .\) What is \(E\left[N \mid S_{2}\right] ?\) (g) Combine the preceding to obtain $$ W_{Q}^{2}=W_{Q}^{2} \text { (nonpreemptive) }+\frac{\lambda_{1} E\left[S_{1}\right] E\left[S_{2}\right]}{1-\lambda_{1} E\left[S_{1}\right]} $$

Short answer

The waiting time for type 2 customers in the preemptive case is given by: $$ W_{Q}^{2} = W_{Q}^{2} \text{ (nonpreemptive)} + \frac{\lambda_{1} E[S_{1}] E[S_{2}]}{1-\lambda_{1} E[S_{1}]} $$

Step-by-step solution

(a) Work in the system comparison

Initially, we can observe that the total work in the system doesn't change, because preempting type 2 customer service doesn't alter the fact that this customer will have to complete the service at some point. Therefore, the total amount of work within the system remains the same in the nonpreemptive and preemptive cases.

(b) Deriving waiting time for type 1 customers \(W_{Q}^{1}\)

Since type 1 customers always have a higher priority and preempt type 2 customer service, the waiting time for them is not influenced by the presence of type 2 customers. Therefore, the waiting time for type 1 customers will be the same as in the case without type 2 customers.

(c) Equation validity

The equation $$ V_{Q}^{2}=\lambda_{2} E\left[S_{2}\right] W_{Q}^{2} $$ relates the average number of customers in queue to the product of arrival rate, average service time, and waiting time. However, this equation does not take into account the effect of type 1 customers preempting type 2 customer service. Therefore, it is not valid in this case.

(d) Type 2 work seen by arrivals

The work seen by a type 2 arrival in a preemptive case would be the same as the nonpreemptive case plus the extra time incurred due to preemption by type 1 customers. Mathematically, this would give us: $$ W_{Q}^{2}=W_{Q}^{2}\text{ (nonpreemptive)} + E[\text{extra time}] $$

(e) Extra time and busy period

The extra time a type 2 customer experiences due to preemption can be computed by factoring in the number of times a type 2 customer is bumped (denoted by N) and the time until the customer gets back in service. Now, when a type 2 customer is bumped, the time until they get back in service can be seen as a "busy period" for type 1 customers. Therefore, the extra time can be calculated as: $$ E[\text{extra time} | N]=\frac{N E[S_{1}]}{1-\lambda_{1} E[S_{1}]} $$

(f) Expected number of bumps given \(S_{2}\)

To compute the expected number of bumps given the service time of a customer of type 2 (\(S_2\)), we need to review how the service time of a type 1 customer affects this. The probability that a type 2 customer is not bumped during its service time is given by the probability of not having any type 1 customer arriving during this service time. Therefore, $$ E[N | S_{2}] = 1 - e^{-\lambda_1 S_{2}} $$

(g) Waiting time for type 2 customers

Finally, combining the results from previous steps, we obtain the waiting time for type 2 customers in the preemptive case as: $$ W_{Q}^{2} = W_{Q}^{2} \text{ (nonpreemptive)} + \frac{\lambda_{1} E[S_{1}] E[S_{2}]}{1-\lambda_{1} E[S_{1}]} $$

Key concepts

Queueing Theory

Queueing theory is the mathematical study of waiting lines, or queues. In the context of a preemptive priority queueing model, we are particularly interested in analyzing how customers are served based on varying levels of urgency. The model considers different types of customers, often prioritizing some over others, such as medical emergencies in a hospital being attended before minor ailments.

The preemptive priority queue can disrupt the service of lower-priority tasks, which differentiates it from a nonpreemptive system where once a service begins, it must be completed before another starts. A classic example of a preemptive system is an operating system where a high-priority process can interrupt a lower-priority one. Understanding the dynamics in these models helps in planning and resource allocation for systems like telecommunication networks, computer operating systems, and customer service centers.

Waiting Time Analysis

Waiting time analysis is integral to understanding queueing models. It deals with predicting how long a customer, or job, might have to wait before its service begins. In the problem at hand, the focus lies on determining the waiting time for two types of customers in a preemptive priority queueing model.

For type 1 customers, their priority means they can essentially 'cut in line', which minimizes their waiting time. Type 2 customers, on the other hand, have to not only wait their turn but also risk being bumped by incoming type 1 customers, adding complexity to their waiting time analysis. The equation for waiting time has to reflect these dynamics to be accurate, and methodologies like Little's Law, which links the number of customers, arrival rate, and average waiting time, may not apply without adjustments for the preemptive nature of the queue. Hence, for a comprehensive understanding, it’s essential to consider these nuances while modeling waiting times.

Service Discipline

Service discipline defines the rules for how customers are selected for service in a queueing model. It's a policy that can significantly affect the performance and efficiency of the system. The preemptive priority service discipline in queueing models prioritizes some customers over others, thus altering the flow of service from the 'first come, first served' principle.

It is important to note that while this discipline can improve the service for high-priority customers, it may increase the waiting time for others. In the exercise, it is highlighted that type 2 customers' service is interrupted if a type 1 customer arrives, and they will resume service only after all type 1 customers have been served. Understanding the impacts of such disciplines on all customers in the system is crucial for designing fair and effective queueing systems.

Busy Period Analysis

Busy period analysis examines the periods of time when the queuing system is continuously occupied. In the preemptive scenario, it's valuable to assess busy periods to calculate the 'extra time' for type 2 customers due to service interruptions. Whenever a type 2 customer is bumped, the queue enters a busy period dominated by servicing type 1 customers.

This analysis involves examining the arrival rates and service times because during busy periods, new arrivals are still being processed, even as currently served customers might have been interrupted. By understanding the busy period dynamics, organizations can better predict and manage the time resources needed to serve all customers according to the defined priorities. It's an essential component for holistic analysis, allowing management to fine-tune operations and reduce inefficiencies within queueing systems.