Journal Search Engine

ISSN : 2005-0461(Print)
ISSN : 2287-7975(Online)

Journal of Society of Korea Industrial and Systems Engineering Vol.40 No.3 pp.66-75
DOI : https://doi.org/10.11627/jkise.2017.40.3.066

(N, n)-Preemptive Repeat-Different Priority Queues

Kilhwan Kim†

Department of Management Engineering, Sangmyung University

Corresponding Author : khkim@smu.ac.kr

Received July 12, 2017 Finally Revised August 14, 2017 Accepted August 16, 2017

Abstract

Priority disciplines are an important scheme for service systems to differentiate their services for different classes of customers. (N, n)-preemptive priority disciplines enable system engineers to fine-tune the performances of different classes of customers arriving to the system. Due to this virtue of controllability, (N, n)-preemptive priority queueing models can be applied to various types of systems in which the service performances of different classes of customers need to be adjusted for a complex objective. In this paper, we extend the existing (N, n)-preemptive resume and (N, n)-preemptive repeat-identical priority queueing models to the (N, n)-preemptive repeat-different priority queueing model. We derive the queue-length distributions in the M/G/1 queueing model with two classes of customers, under the (N, n)-preemptive repeat-different priority discipline. In order to derive the queue-length distributions, we employ an analysis of the effective service time of a low-priority customer, a delay cycle analysis, and a joint transformation method. We then derive the first and second moments of the queue lengths of high- and low-priority customers. We also present a numerical example for the first and second moments of the queue length of high- and low-priority customers. Through doing this, we show that, under the (N, n)-preemptive repeat-different priority discipline, the first and second moments of customers with high priority are bounded by some upper bounds, regardless of the service characteristics of customers with low priority. This property may help system engineers design such service systems that guarantee the mean and variance of delay for primary users under a certain bounds, when preempted services have to be restarted with another service time resampled from the same service time distribution.

Key Words : Queueing Systems , Priority Queues , Preemption , Preemptive Repeat Different , N-Policy

(N, n)-선점 재샘플링-반복 우선순위 대기행렬

김 길 환†

상명대학교 경영공학과

초록

키워드 :

This article has been cited by 0 article in crossref

Cited-By

Funding:

Sangmyung University

1.Introduction

Priority disciplines are an important scheme for service systems to differentiate their services for different classes of customers. For this reason, many telecommunication, computer, and production systems employ various priority disciplines. Priority queueing models are typically utilized to analyze the performance of systems under various priority disciplines, and there have been a number of studies on priority queueing models [9, 10, 12, 21, 22, 24].

There are two fundamental classical priority disciplines [23] : One is the preemptive priority discipline, under which customers with high priority can interrupt the service of customers with lower priority, and the other is the nonpreemptive priority discipline, under which, once the service of customers with low priority has been started, it is not interrupted even though there are customers with high priority arriving in the system during the service. However, these two priority disciplines have their own drawbacks. Under the preemptive priority discipline, the quality of service (QoS) for customers with low priority may be severely degraded especially when preemption frequently occurs and the service interrupted has to be completely repeated. On the other hand, under the nonpreemptive priority discipline, the QoS for customers with high priority may be severely degraded especially when the service time of customers with low priority is relatively long and significantly varies in length.

In order to overcome these drawbacks of the classical priority disciplines, several hybrid-type priority disciplines have been introduced [1~4, 6~8, 11, 13~16, 18~20, 22~24]. See [13~16] for a brief review on these hybrid-type priority disciplines. The (N, n)-preemptive priority discipline is one of these hybrid-type priority discipline [14]. Under this discipline, the decision on whether or not to preempt the service of customers with low priority depends on the number of customers with high priority present in the system. Once the service of customers with low priority has started, it is preempted only when the number of customers with high priority reaches or exceeds a certain threshold N, N ≥ 1; the interrupted service is restored when the number of customers with high priority shrinks to another certain threshold n, 0 ≤ n ≤ N - 1. The advantage of the (N, n)-preemptive priority discipline is that it is easier than other hybrid-type priority disciplines to control the QoS for customers with high priority in a certain bound, regardless of the arrival and service characteristics of customers with low priority [14].

This paper extends Kim’s result [14] to a different variant of the (N, n) preemptive priority discipline. While Kim [14] assumes that the interrupted service is retained and resumed when the service is available again for the preempted lowpriority customer (which will be called the (N, n)-preemptive resume (PR) priority discipline) or it is repeated with the identical service time (which will be called the (N, n)-preemptive repeat-identical (PRI) priority discipline), this paper assumes that the interrupted service of the preempted low-class customer is repeated with a different service time from the same service distribution, which will be called the (N, n)- preemptive repeat-different (PRD) priority discipline). The (N, n)-PRD discipline is a natural extension of the classical preemptive repeat-different discipline and its variant [6, 17, 25] to the (N, n)-preemptive discipline. There are two contributions which extended Kim’s original (N, n)-preemptive models [18, 19] to discrete-time queueing models. However, these contributions only considered the models with geometric service times, where there are no differences between (N, n)-PR, PRD, and PRI disciplines due to the so-called memoryless property of the service time distribution. Here, we consider the models with general service-time distributions, and the types of the way of restoring interrupted services have different impact on the system overall performance.

This paper is organized as follows : In Section 2, we define the mathematical model considered in this paper; In Section 3, we analyze the effective service time structure of a low-priority customer. In Section 4, we derive the queuelength distributions for high-priority and low-priority customers. In Section 5, we present some numerical examples by using the result obtained in Sections 3 and 4. In Section 6, we conclude the paper with some comments.

2.Model

We consider the following M/G/1 queueing model under the (N, n)-preemptive repeat-different preemptive discipline : There are two classes of customers and class-i, i = 1,2, customers arrive at the system according to a Poisson process with rate λ_i. The total arrival rate λ is defined as λ = λ₁ + λ2. The service times S_i of class-i customers are independent and identically distributed, and follow an arbitrary general distribution. Let S_i (x) denote the distribution function of S_i, and $S_{i}^{*} (θ)$ denote the Laplace-Stieltjes transform (LST) of S_i (x) .

Under the (N, n)-PRD priority discipline, class-1 customers have priority over class-2 customers. If there are no preempted class-2 customers in the system, one of class-1 customers (if any) is first selected for the next service just after the service being process is completed. If there are no class-1 customers at the service completion time, one of class-2 customers (if any) can be selected for the next service. While the service of a class-2 customer is being processed, class-1 customers can preempt that service only when the number of class-1 customers reaches or exceeds a certain threshold N, N ≥ 1. Then, the interrupted service of the preempted class-2 customer is completely restarted from the beginning with a different service time resampled from the same service time distribution S₂ (x) , when the number of class-1 customers shrinks to another threshold n,0 ≤ n ≤N - 1. Note that, when N = 1 and n = 0, the (N, n)-PRD priority discipline become identical to the classical preemptive repeat-different priority discipline. Also, when N = ∞, the (N, n)-PRD prio rity discipline become identical to the classical nonpreemptive priority discipline.

Let $ρ_{i} = λ_{i} E [S_{i}]$ . We assume that the system is stable for class-1 customers. That is, ρ₁ < 1. Let also ρ = ρ₁ + ρ₂. Note that ρ < 1 is not the stability condition for class-2 customers because the service of class-2 customers can be repeated more than once. We assume that the system can be either stable or unstable for class-2 customers. We will assume the stability of the system for class-2 customers only when we derive the queue-length distribution of class-2 customers.

3.Analysis of Service Time Structure

The overall approach here is the same as that in [14]. Thus, the common derivation in both [14] and this study will not be repeated here, except when it is needed for the overall understanding of the system considered here. As with many studies on priority queueing models [5~7, 13, 14, 16], we employ a classical method in which the effective service time of a low-class customer is analyzed and the result obtained is plugged into a kind of M/G/1 vacation queueing models to derive the queue-length distributions of high- and low-class customers, respectively (see [23] for a brief review on the queue-length distribution of vacation queues). In this approach, three types of the effective service time of a class-2 customer are defined : the gross service time G of a class-2 customer is defined as the total time spent by the server for this class-2 customers (including all the service repetitions (if any)); the completion time C is defined as the time interval from the first service start time of the class-2 customer until the completion of that service; the occupation time R is defined as the time interval from the first service start time of the class-2 customer until the server is available for the next class-2 customer (if any).

We further divide the class-1 customers who arrived during G into two groups : some class-1 customers who arrive during G will preempt the service of the class-2 customer and complete their service before G ends. We will call those class-1 customers GP customers. Some other class-1 customers who arrive during G will not preempt the service of the class-2 customer and begin their service after G ends. We will call those class-1 customers GN customers. Let a^GP and a^GN denote the number of GP and GN customers during G, respectively. Let a^G denote the number of class-1 customers who arrive during G. Thus, a^G = a^GP + a^GN . We also define the following joint transform of G, a^GP and a^GN :(1)

G (θ; z, w) = E [e^{- G θ} z^{a^{G P}} w^{a^{G N}}]

(1)

If we let C^*(θ) and R^*(θ ) denote the LSTs of C and R , then we have from [14] :

C^{*} (θ) = G (θ; B^{*} (θ), 1)

(2)

and

R^{*} (θ) = G (θ; B^{*} (θ), B^{*} (θ))

(3)

where B^*(θ ) is the LST of the standard M/G/1 busy period with S₁ as the corresponding service time and λ₁ as the corresponding arrival rate, and B^*(θ ) is expressed as the following well-known equation (see [23]) :(4)

B^{*} (θ) = S_{1} (θ + λ_{1} - λ_{1} B^{*} (θ))

(4)

Under the (N, n)-PRD discipline, each time the number of class-1 customers in the system reaches N during the service time of a class-2 customer, the service of the class-2 customer is preempted. This preempted service will be completely repeated at the next service attempt with a different service time resampled from the same service-time distribution S₂ (x) , as soon as the number of class-1 customers shrinks to n.

Hence, if the service time S₂ of a class-2 customer at its first service attempt is shorter than the Erlang random variable E_N with parameters N and λ₁, the service of the class-2 customer will be completed at this service attempt. Otherwise, it will be preempted and repeated with a different service time resampled from the same distribution, when the number of class-1 customers shrinks to n. If the service time S₂ of a class-2 customer at each service attempt except the first service attempt is shorter than the Erlang random variable E_N-n with parameters (N - n) and λ₁, the service of the class-2 customer will be completed at this service attempt. Otherwise, it will be preempted again. It is because, at the beginning of each service attempt except the first service attempt, there are already n class-1 customers in the system.

In order to take into consideration this dependency of the service completion of a class-2 customer on S₂, E_N and E_N-n , we first define $a^{S_{2}}$ as the number of class-1 customers who arrive during S₂ at an arbitrary service attempt. We next define the following two joint transforms for r = 1, 2, ⋯ :(5)

\begin{matrix} S_{2}^{*} (θ; r) = Pr [a^{S_{2}} = r] E [e^{- θ S_{2}} | a^{S_{2}} = r] \\ = \int_{0}^{\infty} \frac{{(λ_{1} x)}^{r}}{r!} e^{- (λ_{1} + θ) x} d S_{2} (x) \end{matrix}

(5)

and

\begin{matrix} E_{r}^{*} (θ) = Pr [E_{r} < S_{2}] E [e^{- θ E_{r}} | E_{r} < S_{2}] \\ = \int_{0}^{\infty} (1 - S_{2} (x)) \frac{{(λ_{1} x)}^{r - 1}}{(r - 1)!} λ_{1} e^{- (λ_{1} + θ) x} d x \end{matrix}

where E_r denotes the Erlang random variable with parameters r and λ₁. By integrating by parts we have

\begin{matrix} E_{1}^{*} (θ) = \frac{λ_{1}}{λ_{1} + θ} (1 - S_{2}^{*} (θ; 0)) \\ E_{r}^{*} (θ) = \frac{λ_{1}}{λ_{1} + θ} (E_{r - 1}^{*} (θ) - S_{2}^{*} (θ; r - 1)), r \geq 2. \end{matrix}

Thus we have(6)

E_{r}^{*} (θ) = {(\frac{λ_{1}}{λ_{1} + θ})}^{r} - \sum_{k = 0}^{r - 1} {(\frac{λ_{1}}{λ_{1} + θ})}^{r - k} S_{2}^{*} (θ; k), r \geq 1,

(6)

which also yields(7)

1 - E_{r}^{*} (θ) = \sum_{k = 0}^{r - 1} S_{2}^{*} (0; k), r \geq 1.

(7)

To derive the joint transform $G^{*} (θ; z, w)$ , we also define $\tilde{G}$ to be the remaining gross service time at the beginning of the second service attempt of a class-2 customer, provided the service of the class-2 customer has not completed at its first service attempt. Let $a^{\tilde{G P}} (a^{\tilde{G N}})$ denote the numbers of class-1 customers who arrive during $\tilde{G}$ and preempt (do not preempt) the service of the class-2 customer. The corresponding joint transform ${\tilde{G}}^{*} (θ; z, w)$ is defined as

{\tilde{G}}^{*} (θ; z, w) = E [E^{- \tilde{G} θ} z^{a^{\tilde{G} P}} w^{a^{\tilde{G} N}}] .

Since the service order among class-1 customers does not affect the distribution of G, a^GP and a^GN , we will assume the Last-In-First-Out (LIFO) service order for class-1 customers in our derivation of the joint transformation $G^{*} (θ; z, w)$ . We now consider the following two events that can occur at the first service attempt of a class-2 customer. (Note that the service time of a class-2 customer is resampled from the same distribution function S₂ (x) at each service attempt) :

If $a^{S_{2}}$ ≥ N (i.e., E_N < S₂) : In this case, at least N class-1 customers arrive during the first service attempt, and the service of the class-2 customer gets preempted immediately after the N^th class-1 customer arrives at the system. Since we assume the LIFO service order for class-1 customers, only the last N - n class-1 customers are served before the preempted class-2 customer is restored again for its service. Also, the remaining n class-1 customers are not serviced until the service of the class-2 customer is completed. It is because, whenever the queue length of class-1 customers shrinks to n, the service of the class-2 customer is restored, and we assumed the LIFO service order for class-1 customers. Thus, we have

\begin{array}{l} Pr [a^{S_{2}} \geq N] \cdot E [e^{- G θ} z^{a^{G P}} w^{a^{G N}} | a^{S_{2}} \geq N] \\ = E_{N}^{*} (θ) z^{N - n} w^{n} \cdot \tilde{G^{*}} (θ; z, w) . \end{array}

If $a^{S_{2}}$ = r, 0 ≤ r ≤N - 1 : In this case, no preemption occurs and the service of the class-2 customer is completed at the first service attempt. Thus, all the r class-1 customers who have arrived during the first service attempt are GN customers, and we have

Pr [a^{S_{2}} = r] \cdot E [e^{- G θ} z^{a^{G P}} w^{a^{G N}} | a^{S_{2}} = r] = S_{2}^{*} (θ; r) w^{r} .

Combining the two cases above, we have

\begin{matrix} G (θ; z, w) = E_{N}^{*} (θ) z^{N - n} w^{n} \cdot {\tilde{G}}^{*} (θ; z, w) \\ + \sum_{r = 0}^{N - 1} S_{2}^{*} (θ; r) w^{r} . \end{matrix}

(8)

In order to derive the term $G^{*} (θ; z, w)$ , we consider the following two events at the second service attempt in a manner similar to the first service attempt.

If $a^{S_{2}}$ ≥ N - n (i.e., E_N-n < S₂) : In this case, at least N - n class-1 customers arrive during the second service attempt, and the service of the class-2 customer gets preempted immediately after the (N - n)^th class-1 customer arrives at the system and it makes N class-1 customers in the system. (Note that there are already n customers at the beginning of the second service attempt.) Since we assume the LIFO service order for class-1 customers, all the (N - n) class-1 customers who arrive during the second service attempt are served before the preempted class-2 customer is restored again for its service. Also, the probability structure at the third service attempt is the same as that at the second service attempt, except that the two service attempts have been already tried, because the arrival process is a Poisson process and the service time is resampled from the identical distribution. Thus, we have

\begin{array}{l} Pr [a^{S_{2}} \geq N - n] \cdot E [e^{- \tilde{G} θ} z^{a^{\tilde{G} P}} w^{a^{\tilde{G} N}} | a^{S_{2}} \geq N - n] \\ = E_{N - n}^{*} (θ) z^{N - n} \cdot \tilde{G^{*}} (θ; z, w) . \end{array}

If $a^{S_{2}} = r$ , 0 ≤ r ≤N - n - 1 : In this case, no preemption occurs and the service of the class-customer is completed at the second service attempt. Thus, all the r class-1 customers who have arrived during the second service attempt are GN customers, and we have

Pr [a^{S_{2}} = r] \cdot E [e^{- \tilde{G} θ} z^{a^{\tilde{G} P}} w^{a^{\tilde{G} N}} | a^{S_{2}} = r] = S_{2}^{*} (θ; r) w^{r} .

Combining the two cases, we have

\begin{matrix} \tilde{G^{*}} (θ; z, w) = E_{N - n}^{*} (θ) z^{N - n} \cdot \tilde{G^{*}} (θ; z, w) \\ + \sum_{r = 0}^{N - n - 1} S_{2}^{*} (θ; r) w^{r}, \end{matrix}

which yields

\tilde{G^{*}} (θ; z, w) = \frac{\sum_{r = 0}^{N - n - 1} S_{2}^{*} (θ; r) w^{r}}{1 - E_{N - n}^{*} (θ) z^{N - n}} .

(9)

Plug (9) in (8) we have

\begin{matrix} G (θ; z, w) = \sum_{r = 0}^{N - n - 1} S_{2}^{*} (θ; r) w^{r} \\ + \frac{E_{N}^{*} (θ) z^{N - n} w^{n}}{1 - E_{N - n}^{*} (θ) z^{N - n}} \cdot \sum_{r = 0}^{N - n - 1} S_{2}^{*} (θ; r) w^{r} . \end{matrix}

(10)

From (2), (3) and (10), we have

\begin{matrix} C^{*} (θ) = \sum_{r = 0}^{N - 1} S_{2}^{*} (θ; r) \\ + \frac{E_{N}^{*} (θ) B^{*} {(θ)}^{N - n}}{1 - E_{N - n}^{*} (θ) B^{*} {(θ)}^{N - n}} \cdot \sum_{r = 0}^{N - n - 1} S_{2}^{*} (θ; r) \end{matrix}

(11)

and

\begin{matrix} R^{*} (θ) = \sum_{r = 0}^{N - 1} S_{2}^{*} (θ; r) B^{*} {(θ)}^{r} \\ + \frac{E_{N}^{*} (θ) B^{*} {(θ)}^{N}}{1 - E_{N - n}^{*} (θ) B^{*} {(θ)}^{N - n}} \cdot \sum_{r = 0}^{N - n - 1} S_{2}^{*} (θ; r) B^{*} {(θ)}^{r} . \end{matrix}

(12)

Differentiating (10) with respect to θ , z , and w , respectively, and letting θ = 0, z = 1, and w = 1 gives

\begin{array}{l} E [G] = \frac{1}{λ_{1}} (N - \sum_{r = 0}^{N - 1} (N - r) S_{2}^{*} (0, r)) \\ + (1 - \sum_{r = 0}^{N - 1} S_{2}^{*} (0; r)) \frac{(N - n) - \sum_{r = 0}^{N - n - 1} (N - n - r) S_{2}^{*} (0, r)}{λ_{1} \sum_{r = 0}^{N - n - 1} S_{2}^{*} (0, r)} \\ E [a^{G P}] = \frac{(N - n) (1 - \sum_{r = 0}^{N - n - 1} S_{2}^{*} (0, r))}{\sum_{r = 0}^{N - n - 1} S_{2}^{*} (0, r)} \\ E [a^{G N}] = \sum_{r = 0}^{N - 1} r S_{2}^{*} (0; r) + (1 - \sum_{r = 0}^{N - 1} S_{2}^{*} (0; r)) {n + \frac{\sum_{r = 1}^{N - n - 1} r S_{2}^{*} (0; r)}{\sum_{r = 0}^{N - n - 1} S_{2}^{*} (0; r)}} \\ E [a^{G N} (a^{G N} - 1)] = \sum_{r = 0}^{N - 1} r (r - 1) S_{2}^{*} (0; r) + (1 - \sum_{r = 0}^{N - 1} S_{2}^{*} (0; r)) \\ \times n (n - 1) + 2 n \frac{\sum_{r = 1}^{N - n - 1} r S_{2}^{*} (0; r)}{\sum_{r = 0}^{N - n - 1} S_{2}^{*} (0; r)} + \frac{\sum_{r = 2}^{N - n - 1} r (r - 1) S_{2}^{*} (0; r)}{\sum_{r = 0}^{N - 1} S_{2}^{*} (0; r)}} \end{array}

\begin{array}{l} E [a^{G N} (a^{G N} - 1) (a^{G N} - 2)] \\ = \sum_{r = 0}^{N - 1} r (r - 1) (r - 2) S_{2}^{*} (0; r) + (1 - \sum_{r = 0}^{N - 1} S_{2}^{*} (0; r)) \\ \times {n (n - 1) (n - 2) + 3 n (n - 1) \frac{\sum_{r = 1}^{N - n - 1} r S_{2}^{*} (0, r)}{\sum_{r = 0}^{N - n - 1} S_{2}^{*} (0, r)} \\ + 3 n \frac{\sum_{r = 2}^{N - n - 1} r (r - 1) S_{2}^{*} (0, r)}{\sum_{r = 0}^{N - 1} S_{2}^{*} (0, r)} + \frac{\sum_{r = 3}^{N - n - 1} r (r - 1) (r - 2) S_{2}^{*} (0, r)}{\sum_{r = 0}^{N - n - 1} S_{2}^{*} (0, r)}} . \end{array}

Differentiating (11) and (12) with respect to θ and letting θ = 0 gives

\begin{matrix} E [C] = \frac{(N - N) (1 - \sum_{r = 0}^{N - 1} S_{^{2}}^{*} (0; r))}{λ_{1} (1 - ρ_{1}) \sum_{r = 0}^{N - 1} S_{^{2}}^{*} (0; r)} + \frac{1}{λ_{1}} (N - \sum_{r = 0}^{N - 1} (N - r) S_{^{2}}^{*} (0, r)) \\ - \frac{(1 - \sum_{r = 0}^{N - 1} S_{^{2}}^{*} (0; r)) \sum_{r = 0}^{N - n - 1} (N - n - r) S_{^{2}}^{*} (0; r)}{λ_{1} \sum_{r = 0}^{N - n - 1} S_{^{2}}^{*} (0; r)} \end{matrix}

and

E [R] = E [G] / (1 - ρ_{1})

In a similar way, expressions for E [C²], E [R²], and E [R³], which are needed for the moments of the class-2 queue length, can be calculated by taking the appropriate derivatives of the respective PGFs as well. (The expressions are omitted because they are too elaborate, but we can derive them using a computer algebra system such as Mathematica or Maxima. In order to show this, we demonstrate some figures of the second moment of the class-2 queue length in Section 5).

4.Queue-Length Distributions

Let ρ_G denote the total utilization factor of the server for class-2 customers. Then, it is expressed as $ρ_{G} = λ_{2} E [G]$ from Little's formula. Let ρ_T denote the total utilization factor for both class-1 and class-2 customers. Then it is expressed as ρ_T = ρ₁ + ρ_G . Since the stability of the system is only assumed for class-1 customers (i.e., ρ₁ < 1), ρ_T may equal or exceed 1, and in that case, the system is unstable for class-2 customers.

Since the (N, n)-PRD priority queue has the same structure of the general cycle as those in the other (N, n)-preemptive priority queue (see [14]), we have the same PGF form of the queue-length distributions of both classes of customers, except that the distributions of G, C, and R are different. Thus, from [14], the PGF $Π_{1} (z)$ of the queue-length distribution of class-1 customers is expressed as :

Π_{1} (z) = V (z) \cdot Π_{1, M / G / 1} (z),

(13)

where

\begin{matrix} V (z) = max [0, \frac{1 - ρ_{T}}{1 - ρ_{1}}] + min [1, \frac{ρ_{G}}{1 - ρ_{1}}] \\ \times {\frac{E [a^{G P}] (z^{n} - z^{N})}{E [a^{G}] (N - n) (1 - z)} + \frac{1 - G^{*} (0, 1, z)}{E [a^{G}] (1 - z)}} \end{matrix}

and

Π_{1, M / G / 1} (z) = \frac{(1 - ρ_{1}) (1 - z) S_{1}^{*} (λ_{1} - λ_{1} z)}{S_{1}^{*} (λ_{1} - λ_{1} z) - z} .

We now derive the moments of the queue length of class-1 customers explicitly, which was omitted in [14]. If we let L₁ and $L_{1}^{(2)}$ be the first and second moments of the queue length of class-1 customers in the system in a steady state, we have from (13)

\begin{array}{l} L_{1} = lim_{z \to 1} Π_{1^{'} (z)} = V_{1} + L_{1, M / G / 1} \\ L_{1}^{(2)} = lim_{z \to 1} Π_{1}^{(2)} (z) + Π_{1^{'} (z)} = V_{1}^{(2)} + 2 V_{1} \cdot L_{1, M / G / 1} + L_{1, M / G / 1}^{(2)} \end{array}

where

\begin{array}{l} \begin{array}{l} V_{1} = \frac{λ_{2} E [a^{G P}] (N + n - 1) + λ_{2} E [a^{G N} (a^{G N} - 1)]}{2 λ_{1} (1 - ρ_{1})} \\ V_{1}^{(2)} = \frac{λ_{2} E [a^{G P}] {(N + n - 1) (2 (N + n) - 1) - 2 N n}}{6 λ_{1} (1 - ρ_{1})} \end{array} \\ + \frac{λ_{2} E [a^{G N} (a^{G N} - 1) (2 a^{G N} - 1)]}{6 λ_{1} (1 - ρ_{1})} \end{array}

and

\begin{array}{l} L_{1, M / G / 1} = \frac{λ_{1}^{2} E [S_{1}^{2}]}{2 (1 - ρ_{1})} + ρ_{1} \\ L_{1, M / G / 1}^{(2)} = \frac{λ_{1}^{3} E [S_{1}^{3}]}{3 (1 - ρ_{1})} + \frac{{(λ_{1}^{2} E [S_{1}^{2}])}^{2}}{2 {(1 - ρ_{1})}^{2}} + \frac{3 λ_{1}^{2} E [S_{1}^{2}]}{2 (1 - ρ_{1})} + ρ_{1} . \end{array}

Similarly, if we assume that ρ_T < 1, then, from [14], the PGF $Π_{2} (z)$ of the queue-length distribution of class-2 customers is expressed as :

\begin{matrix} Π_{2} (z) = \frac{λ_{1} (1 - B^{*} (λ_{2} - λ_{2} z)) + λ_{2} (1 - z)}{λ_{2} (1 - z) / (1 - ρ_{1})} \\ \times \frac{(1 - E [R]) (1 - z) C^{*} (λ_{2} - λ_{2} z)}{R^{*} (λ_{2} - λ_{2} z) - z} . \end{matrix}

(14)

We also derive the moments of the queue length of class-2 customers explicitly, which was also omitted in [14]. From (14), we have

L_{2} = lim_{z \to 1} Π_{2^{'} (z)} = \frac{λ_{1} λ_{2} E [S_{1}^{2}]}{2 {(1 - ρ_{1})}^{2}} + \frac{λ_{2}^{2} E [R^{2}]}{2 {(1 - λ_{2} E [R])}^{2}} + λ_{2} E [C]

and

\begin{matrix} L_{2}^{(2)} = lim_{z \to 1} Π_{2}^{(2)} (z) + Π_{2^{'}} (z) \\ = \frac{λ_{1} λ_{2}^{2} E [S_{1}^{3}]}{3 {(1 - ρ_{1})}^{3}} + {(\frac{λ_{1} λ_{2} E [S_{1}^{2}]}{{(1 - ρ_{1})}^{2}})}^{2} + \frac{λ_{2}^{3} E [R^{3}]}{3 (1 - λ_{2} E [R])} + \frac{{(λ_{2}^{2} E [R^{2}])}^{2}}{2 {(1 - λ_{2} E [R])}^{2}} \\ + \frac{λ_{1} λ_{2} E [S_{1}^{2}]}{2 {(1 - ρ_{1})}^{2}} (1 + \frac{λ_{2}^{2} E [R^{2}]}{1 - λ_{2} E [R]} + 2 λ_{2} E [C]) \\ + \frac{λ_{2}^{2} E [R^{2}] (1 + 2 λ_{2} E [C])}{2 (1 - λ_{2} E [R])} + λ_{2}^{2} E [C^{2}] + λ_{2} E [C] . \end{matrix}

Even though we omit the proof, Lemma 1 and Theorem 2 in [14] on the upper bounds of L₁ and $L_{1}^{(2)}$ also hold for the (N, n)-PRD queueing model. Refer to the last two paragraphs in [14] for an intuitive explanation of why the same upper bounds hold for different types of (N, n)-preemptive priority queues.

5.Numerical Examples

In this section, we present a numerical example of the first and second moments of the queue lengths of class-1 and class-2 customers. <Figure 1> shows how the moments of the queue lengths are influenced as the upper threshold N changes, when the lower threshold n = 0, for three different squared coefficients of variation (SCVs) of S₂ (which is denoted by h in <Figure 1>). Note that, if N = 1,n = 0, the (N, n)-PRD queue is identical to the classical PRD queue, and if N = ∞, the (N, n)-PRD queue is identical to the classical nonpreemptive queue. In <Figure 1>, we can see that the shapes of the first and second moments of the class-1 queue length in the (N, n)-PRD priority queue are very similar to those in other (N, n)-preemptive queues in [14]. Actually, the upper bounds of the moment of the class-1 queue length in this (N, n)-PRD example are exactly the same as those in the previous (N, n)-preemptive example in [14] because we use the identical arrival processes and the service time distributions for the both examples, in order to make it easy to compare the effect of N for different (N, n)-preemptive disciplines. There is a single remarkable difference between the shapes of the moments of the class-1 queue lengths between the (N, n)-PRD queue and the other (N, n)-preemptive queues : While, for the other (N, n)-preemptive priority queues, the smaller the SCV is (i.e., the relative variance of the service time of class-2 customers is lower), the smaller are the first and second moments of the class-2 queue lengths regardless of the value of N , for the (N, n)-PRD priority queue, this tendency holds only for a sufficiently large N . For the (N, n)-PRD priority discipline, for several small values of N , the smaller the SCV is, the larger are the first and second moments of the class-2 queue length. The reason for this is that, for the case of a large variance of the service time of a class-2 customer, a long service time of a class-2 customer can have a chance to be replaced with a relatively shorter service time by preemption of class-1 customers, and this can positively affect the performance measures of class-2 customers.

In <Figure 2>, the first and second moments of the class-1 and class-2 queue lengths are shown as functions of the threshold n, given N - n = 1, in the (N, n)-PRD priority queue, for three different SCVs (denoted by h in the figure) of the service time of a class-2 customer.

While, for a sufficiently large n, the shapes of the first and second moments of the class-1 queue length are very similar to the other (N, n)-preemptive priority queue in [14], for a small n, the shapes are different. Interestingly, for the cases of h = 2 and 3, as n increases, the first and second moments of the class-1 queue length first increase, and then decrease, and finally converge to the first and second moment in the corresponding nonpreemptive queue. These tendencies are also different from the shapes of the first and second moments of the class-1 queue length in <Figure 1>, where the threshold N increase with n = 0.

The reason of these rising and fall shapes of the first and second moments of the class-1 queue length in the (N, n)-PRD priority queue is that, for the case of N - n = 1, as n increases, class-1 customers have less chance to preemption, and even if they preempt the service of a class-2 customer, the service of the class-2 customer has to be completely restarted, which is a very severely negative effect on the class-1 customers’ performance. However, when n becomes too high, hence N also high, class-1 customers almost never preempt class-2 customers, which avoids the repetition of services of class-2 customers, therefore a better performance for class-1 customers.

In <Figure 3>, the first and second moments of the class-1 and and class-2 queue lengths are shown as functions of the threshold n and the difference of N and n in the (N, n)-PRD priority queue, for the case of h = 2. For a given n, as N - n increases, the first and second moments of the class-1 queue length increase, while the first and second moments of the class-2 queue length decrease. Also, for a given N - n, as n increases, the first and second moments of the class-1 queue length increase, while the first and second moments of the class-2 queue length decrease.

6.Conclusion

In this paper, we derived the queue-length distributions of high-class and low-class customers in the (N, n)-preemptive repeat-different queueing model, and presented a numerical example for this queueing model. As shown in the numerical example, the first and second moments of the class-1 queue length are bounded by the upper bounds, regardless of the characteristics of the service time of class-1 customers and the preemptive mode, as in the other (N, n)-preemptive priority queue in [14]. This property helps system engineers design such service systems that guarantee the mean and variance of delay for primary users under a certain bounds, when preempted services have to be restarted with another service time resampled from the same service time distribution. The property may be very useful, especially when the stochastic characteristic of low-priority customers easily varies or it cannot be easily determined.

Acknowledgement

This research was supported by a 2016 Research Grant from Sangmyung University.

Figure

<Figure 1>.

The Moments of the Queue Lengths in the (N, n)-PRD Priority Queue (n = 0)

<Figure 2>.

The Moments of the Queue Lengths in the (N, n)-PRD Priority Queue (N - n = 1)

<Figure 3>.

The Moments of the Queue Lengths in the (N, n)-PRD Priority Queue (h = 2)

Table

Reference

Adiri I. , Domb I. (1982) A Single Server Queueing System Working under Mixed Priority Disciplines , Oper. Res, Vol.30 (1) ; pp.97-115
Adiri I. , Domb I. (1984) Mixing of Non-Preemptive and Preemptive Repeat Priority Disciplines , Eur. J. Oper. Res, Vol.18 (1) ; pp.86-97
Avi-Itzhak B. , Brosh I. , Naor P. (1964) On Discretionary Priority Queueing, ZAMM- , J. Appl. Math. Mech, Vol.44 (6) ; pp.235-242
Cho Y.Z. , Un C.K. (1993) Analysis of the M/G/1 Queue under a Combined Preemptive/Nonpreemptive PriorityDiscipline , IEEE Trans. Commun, Vol.41 (1) ; pp.132-141
Conway R.W. , Maxwell W.L. , Miller L.W. (1967) Theory of scheduling, Addison-Wesley,
Drekic S. , Stanford D.A. (2001) Reducing Delay in Preemptive Repeat Priority Queues , Oper. Res, Vol.49 (, 1) ; pp.145-156
Drekic S. , Stanford D.A. (2000) Threshold-Based Interventions to Optimize Performance in Preemptive Priority Queues , Queueing Syst, Vol.35 (1) ; pp.289-315
Drekic S. (2003) A Preemptive Resume Queue with an Expiry Time for Retained Service , Perform. Eval, Vol.54 (1) ; pp.59-74
Dudin A. , Lee M.H. , Dudina O. , Lee S.K. (2017) Analysis of Priority Retrial Queue with Many Types of Customers and Servers Reservation as a Model of Cognitive Radio System , IEEE Trans. Commun, Vol.65 (1) ; pp.186-199
Gao S. (2015) A Preemptive Priority Retrial Queue with Two Classes of Customers and General Retrial Times , Oper. Res, Vol.15 (2) ; pp.233-251
Gay T.W. (1975) IBM J. Res. Develop, Vol.19 (1) ; pp.78-81
Jouini O. , Roubos A. (2014) On Multiple Priority Multi- Server Queues with Impatience , J. Oper. Res. Soc, Vol.65 (5) ; pp.616-632
Kim K. , Chae K.C. (2010) Discrete-Time Queues with Discretionary Priorities , Eur. J. Oper. Res, Vol.200 (2) ; pp.473-485
Kim K. (2011) Preemptive Priority Queues , Perform. Eval, Vol.68 (7) ; pp.575-585
Kim K. (2012) The Analysis of an Opportunistic Spectrum Access with a Strict T-preemptive Priority Discipline , Journal of Society of Korea Industrial and Systems Engineering, Vol.35 (4) ; pp.162-170
Kim K. (2012) T-Preemptive Priority Queue and Its Application to the Analysis of an Opportunistic Spectrum Access in Cognitive Radio Networks , Comput. Oper. Res, Vol.39 (7) ; pp.1394-1401
Lee Y. , Lee K-S. (2003) Discrete-Time Queue with Preemptive Repeat Different Priority , Queueing Syst, Vol.44 (4) ; pp.399-411
Ma Z. , Hao Y. , Wang P. , Cui G. (2015) Analysis of the Geom/Geom/1 Queue under (N, n)-Preemptive Priority Discipline , J. Inf. Comput. Sci, Vol.12 (3) ; pp.1029-1036
Ma Z. , Zheng X. , Xu M. , Wang W. (2016) Performance Analysis and Optimization of the (N, n)-Preemptive Priority Queue with Multiple Working Vacation , ICIC Express Lett, Vol.10 (11) ; pp.2735-2741
Paterok M. , Ettl M. (1994) Sojourn Time and Waiting Time Distributions for M/GI/1 Queues with Preemption- Distance Priorities , Oper. Res, Vol.42 (6) ; pp.1146-1161
Sharif A.B. , Stanford D.A. , Taylor P. , Ziedins I. (2014) A Multi-Class Multi-Server Accumulating Priority Queue with Application to Health Care , Oper. Res. Health Care, Vol.3 (2) ; pp.73-79
Stanford D.A. , Taylor P. , Ziedins I. (2014) Waiting Time Distributions in the Accumulating Priority Queue , Queueing Syst, Vol.77 (3) ; pp.297-330
Takagi H. (1991) Vacation and Priority Systems, Part 1, North-Holland, Vol.1
Walraevens J. , Maertens T. , Bruneel H. (2013) A Semi- Preemptive Priority Scheduling Discipline : PerformanceAnalysis , Eur. J. Oper. Res, Vol.224 (2) ; pp.324-332
Walraevens J. , Steyaert B. , Bruneel H. (2006) A Preemptive Repeat Priority Queue with Resampling : Performance Analysis , Ann. Oper. Res, Vol.146 (1) ; pp.189-202