• Editorial Board +
• For Contributors +
• Journal Search +
Journal Search Engine
ISSN : 1598-7248 (Print)
ISSN : 2234-6473 (Online)
Industrial Engineering & Management Systems Vol.21 No.2 pp.267-276
DOI : https://doi.org/10.7232/iems.2022.21.2.267

# On the Largest-Group-First Priority Rule in Queueing

Nam K. Kim, Won Seok Yang, Kilhwan Kim*, Mohan L. Chaudhry
Department of Industrial Engineering, Chonnam National University, Republic of Korea
Department of Management Engineering, Sangmyung University, Republic of Korea
Department of Mathematics and Computer Science, Royal Military College of Canada, Canada
*Corresponding Author, E-mail: khkim@smu.ac.kr
November 11, 2021 ; April 28, 2022 ; April 28, 2022

## Abstract

In this paper, we consider a group-arrival group-service single-server queue, where customers arrive in groups, get served, and leave, group by group. We consider, in particular, what we call the “Largest Group First (LGF)” priority rule. Under a certain condition, we show that the expected waiting time of an individual customer of a group under LGF is always less than its FIFO (First In First Out) counterpart and that the system under LGF can earn more profit than the same under FIFO by giving priorities to larger groups while giving discounts to smaller groups. This is demonstrated with a numerical example.

## 1. INTRODUCTION

In service systems, such as a restaurant, a taxi stand, and an amusement ride, customers arrive in groups get service together and leave the system in groups. When the service is not available upon their arrivals, they join the queue (physical or virtual one), and wait for service. When the service becomes available, they are served, naturally in the order of their arrivals, the so-called First In First Out (FIFO) order. Suppose, however, that they are served not in the order of their arrivals, but in the order of their group sizes, which we call the Largest Group First (LGF) order; i.e., the largest group in size among those groups waiting in line gets service first even if it arrived later than the others. Of course, serving the largest group first is not fair, particularly when it is seen by those who arrived earlier but are overtaken by larger groups; however, it has some considerable advantages. This paper is about the advantages that LGF can bring in at the cost of the fairness ensured by FIFO.

We, particularly, focus on the individual-wise average of the waiting time (rather than the group-wise one). Suppose a situation, in which a group of size four, for example, is waiting in line, right next to a group of size two and only one group can escape from the waiting line to get service. Giving a group of size four a priority over the other, even though it arrived later, obviously reduces the overall individual waiting times; as far as the individual waiting time is concerned, a unit time spent in waiting by four is two times greater than the same by two. In this regard, LGF can possibly reduce the total sum of individual waiting costs, thus increasing the overall social welfare (for the concept of the social welfare, see Hassin and Haviv, 2003). However, this may not be always true, particular when the service time of a large group is likely to be longer than that of a small group. In fact, it is wellknown in queueing as well as in scheduling that serving the customer with the shortest service time before all the others in queue minimizes the average waiting time of customers (see, e.g., Wolff, 1989;Pinedo, 2016). In this paper, we discuss whether serving the largest group first – even if its service time is longer – is nevertheless favorable compared with FIFO, as far as the individual waiting time is concerned.

To this end, we consider a stable single-server queue, where customers arrive in groups, get service together, and leave in group and the customers from the same group never break apart during the whole queueing process (this is not always the case in group-arrival group-service queues; see, e.g., Chaudhry and Templeton, 1983). Under a certain sufficient condition, we show that the expected individual waiting time under LGF is always less than its FIFO counterpart. Further, we discuss that by giving certain benefits to customers of smaller groups in return for being overtaken by larger groups, the increased social welfare (resulting from the reduced total sum of the individual waiting costs) can be shared out. As a result, we show that the system under LGF can earn more profit than the same under FIFO, while individual customers of larger groups spend less time in waiting and those of smaller groups benefit from considerable discounts. This is demonstrated with a numerical example.

Queues with priority customers have been widely discussed in the literature (see, e.g., Wolff (1989) and Takagi (1991) and the references therein; for their applications to telecommunications and manufacturing, see, e.g., Oh et al. (2013) and Doh et al. (2016), respectively). In such a queue, a customer with a higher priority gets service earlier than those with lower priorities even if she arrives later. The priority can be given, for example, to the customer who has the shortest service time, the highest waiting cost, the highest revenue, or even otherwise. To the best of authors’ knowledge, LGF is not discussed the way we explicitly do in this paper.

The paper is organized as follows: In Section 2, we present a sufficient condition, under which the expected individual waiting time under LGF is always less than its FIFO counterpart. In Section 3, we present a cost and benefit analysis to show that the system can earn more profit under LGF than under FIFO by giving priorities to larger groups while giving discounts to smaller groups, which is demonstrated with a numerical example. In Section 4, we discuss further advantages that LGF can bring in and conclude the paper.

## 2. INDIVIDUAL WAITING TIMES UNDER FIFO AND LGF

In this section, we make use of the so-called work conservation law to obtain a preliminary relation between the expected waiting time of a group of customers under LGF and its FIFO counterpart. Then we present a sufficient condition, under which the expected waiting time of an individual customer under LGF is always less than its FIFO counterpart.

Before bringing in group arrivals and group services, we first consider a stable single-server (single-arrival single- service) queue with K classes of customers under the following assumptions: Interarrival times of customers are a sequence of random variables (not necessarily independent and identically distributed (shortly, i.i.d.) ones) with finite mean 1/ λ . The probability that an arriving customer is an i-class customer, independent of all else, is given by pi for i=1,2,⋯,K (such that the arrival rate of i-class customers is given by $λ i = λ p i$). The queue has a priority rule, in which K-class customers have the highest priority and then (K−1) -class, and so on, and the 1-class customers have the lowest priority; customers within the same class are served under FIFO; hence, at each service completion, the next customer to get service will be the first one from the highest-class customers among those waiting in queue. By the single server, i - class customers are served and they have i.i.d. service times (independent of the arrival process) denoted by Si . Once a service begins, each customer is served to completion without interruption (this is called the nonpreemptive service) and she leaves the system upon completion of her service. Finally, the server is busy, whenever there is a customer to serve (this is an essential assumption for work conserving).

Let Ni and Wi be the number of i-class customers in queue (excluding the one in service, if any) and the time an i-class customer waits in queue (excluding her time in service), respectively. Also, let V be the work (in work hours) associated with the customers waiting in queue (excluding the work associated with the customer in service, if any). Since the priority rule is workconserving, we have

(1)

where $ρ i = λ i E [ S i ]$ and $ρ = ∑ i = 1 K ρ i < 1$ (see, e.g., Federgruen and Groenevelt, 1988;Wolff, 1989). To represent quantities under FIFO (LGF) in this paper, we use a subscript FIFO (LGF), e.g., $E [ W ] F I F O ( E [ W ] L G F )$. Note that the first equality of Eq. (1) follows from the fact that V is the sum of the (independent) service times of all the customers in queue and the second equality from the Little’s formula (Little, 1961). Note also that under FIFO, $E [ W i ] F I F O = E [ W ] F I F O$ for all for i =1,2,⋯,K, since every customer – independent of her class – would experience a stochastically identical waiting-time situation under FIFO. Eq. (1) is called a work-conservation law.

Now, we bring in group arrivals and group services, where a group of customers of size i corresponds to an i-class priority customer (i =1,2,⋯,K) discussed above; hence, a larger group has a priority over a smaller group, which we call LGF. It is assumed that group sizes are i.i.d. positive random variables. Under either LGF or FIFO, we consider a stable single-server non-preemptive queue, where customers arrive in groups, get served in groups, and leave the system in groups. Note that customers move always in group and customers from the same group never break apart during the whole queueing process.

For such a queue, we have from Eq. (1)

$∑ i = 1 K ( ρ i ρ ) E [ W i ] L G F = E [ W ] F I F O$
(2)

Since a group (whether large or small) arrives to find a stochastically identical queueing situation, we have under LGF

$E [ W 1 ] L G F ≥ E [ W 2 ] L G F ≥ ⋯ ≥ E [ W K ] L G F$
(3)

that is, ${ E [ W i ] L G F , i = 1 , 2 , ⋯ , K }$ is a (monotonically) decreasing sequence. (Equality holds in such a trivial case as a queue with infinitely many servers; otherwise it does not, so long as overtakes can happen in queue waiting).

We now consider the waiting time in terms of an individual customer of a group. Note that a group of size i consists of i individual customers. Under LGF, the expected time that an individual customer spends waiting in queue, denoted by $E [ W I ] L G F$ is represented by the following weighted average:

$E [ W I ] L G F = ∑ i = 1 K ( i λ i λ I ) E [ W i ] L G F$
(4)

where $λ I = ∑ i = 1 K i λ i$ is the number of individual customers in total that arrive during a unit time. Under FIFO, on the other hand, we have

$E [ W I ] F I F O = ∑ i = 1 K ( i λ i λ I ) E [ W i ] F I F O = E [ W ] F I F O$
(5)

The last equality of Eq. (5) follows from $E [ W i ] F I F O = E [ W ] F I F O$ for all i =1,2,⋯,K . Hereafter, we use E[Wi ]FIFO , $E [ W I ] F I F O$ and E[W]FIFO interchangeably.

Our focus, in this paper, is on whether $E [ W I ] L G F$ is less than $E [ W I ] F I F O$ , in order to find out whether LGF is more favorable, compared with FIFO, in terms of the waiting time of an individual customer. We first consider a simple case, in which E[Si]= E[S] for all i =1,2,⋯,K ; that is, the expected service time is a constant, independent of the group size. In this case, Eq. (2) specializes to

$∑ i = 1 K ( λ i λ ) E [ W i ] L G F = E [ W I ] F I F O$
(6)

where $λ = ∑ i = 1 K λ i$ is the number of groups that arrive during a unit time. From Eqs. (3), (4), and (6), we have

(7)

The equality of ≤ in the middle of Eq. (7), in particular, follows from the fact that more weights are given to larger values in the left-hand-side convex combination of the decreasing sequence ${ E [ W i ] L G F }$, compared with the righthand- side counterpart (equality holds only in trivial cases, where λi >0 for a certain i and λj =0 for ji).

Practically, the E[Si]= E[S] discussed above is rather a confining one. We further consider whether $E [ W I ] L G F$ is still less than $E [ W I ] F I F O$ even if the service time gets larger as the group size grows. As a result, we find out a sufficient condition as follows:

### Theorem 1.

Under the condition that

$E [ S 1 ] 1 ≥ E [ S 2 ] 2 ≥ ⋯ ≥ E [ S K ] K$
(8)

it follows that

$E [ W I ] L G F ≤ E [ W I ] F I F O$
(9)

### Proof.

Let $x i = ρ i / ρ$, and $y i = i λ i / λ I$ for $i = 1 , 2 , ⋯ , K$. Then, Eqs. (2) and (4) are rewritten, respectively, as follows:

$E [ W I ] F I F O = ∑ i = 1 K x i E [ W i ] L G F$
(10)

$E [ W I ] L G F = ∑ i = 1 K y i E [ W i ] L G F$
(11)

Note that {xi} and {yi} are coefficients of the convex combinations given by Eqs. (10) and (11), respectively: xi > 0 , yi , $∑ i = 1 K x i = 1$ and $∑ i = 1 K y i = 1$ = (meaningless terms, such as xi =0 , yi =0 , i.e., E[Si]=0 , λi =0 , are ruled out in these convex combinations). Then, we have, for i=1, 2,⋯, K,

$y i x i = ρ λ I · i E [ S i ]$
(12)

Thus, from Eqs. (8) and (12), we have

$y 1 x 1 ≤ y 2 x 2 ≤ ⋯ ≤ y K x K$
(13)

That is, ${ y i / x i }$ is a (monotonically) increasing sequence. From Eq. (13), combined with the fact that {xi} and {yi} are coefficients of the convex combinations, there exists j ∈{1, 2,⋯, K −1} such that

$y i x i ≤ 1 for all i ≤ j , and y i x i ≥ 1 for all i > j .$
(14)

Then, from Eqs. (3), (10), (11), and (14), we have

$E [ W I ] F I F O − E [ W I ] L G F = ∑ i = 1 K ( x i − y i ) E [ W i ] L G F = ∑ i = 1 K ( x i − y i ) { E [ W i ] L G F − E [ W j ] L G F } ≥ 0$
(15)

The second equality of Eq. (14) follows from the fact that $∑ i = 1 K ( x i − y i ) E [ W j ] L G F = 0$ and its last inequality follows from Eqs. (3) and (14), such that for ij, both terms (xiyi) and ${ E [ W i ] L G F − E [ W j ] L G F }$ are non-negative, while for all i>j, both terms are non-positive. From Eq. (14), we have the desired result.□

The equality of Eq. (9) holds in case of $E [ S i ] = i ⋅ E [ S 1 ]$ for $i = 1 , 2 , ⋯ , K$; that is, the expected service time for a group of size i increases in exact proportion to the group size. In this case, Eq. (2) specializes to $∑ i = 1 K ( i λ i / λ I ) E [ W i ] L G F = E [ W I ] F I F O$. From this and Eq. (4), we have the equality: $E [ W I ] L G F = ∑ i = 1 K ( i λ i / λ I ) E [ W i ] L G F = E [ W I ] F I F O$. In this case, it is interesting to note that the disadvantage, resulting from the increased group-wise waiting time, caused by serving first the group with the longest service time, balances out the advantage, resulting from the decreased individual-wise waiting time under LGF.

### Remark 1.

In many group-arrival group-service queueing situations, where groups of customers arrive, get served, and depart, group by group, their expected service times tend to be large when their group sizes are large, i.e., $E [ S 1 ] ≤ E [ S 2 ] ≤ ⋯ ≤ E [ S K ]$. (Think of an ice cream stand, for example, where groups of customers line up to buy ice creams. Here, a service time of a group can be considered to be the time it takes for the group to place an order and then to get ice screams for all the individual customers of the group.) If the service time of a group grows explosively as the group size increases, does $E [ W I ] L G F$$E [ W I ] F I F O$ still follows? Theorem 1 shows that it follows so long as the individual-wise average ($E [ S i ] / i$) of the service time diminishes (resulting from a sort of the economies of scale). Consider an extreme case, for example, where $E [ S i ] = i × E [ S 1 ]$; in this case, note that the condition (8) is just satisfied so that $E [ W I ] L G F$$E [ W I ] F I F O$ still follows (in fact, the equality holds in this case, as discussed earlier). Beyond this outermost case, $E [ W I ] L G F$$E [ W I ] F I F O$ does not necessarily follows. Consider a more general case, for example, where $E [ S i ] = E [ S i − 1 ] + m × E [ S 1 ]$, i≥2, i.e., an additional customer in a group increases the expected group service time by m×E[S1] . Then it is easy to see that the condition (8) is satisfied when m≤1 . (It may be noted that it is also the case even when m is negative, i.e., an additional customer in a group decreases the expected service time of the group, provided that E[Si]>0 for all i =1,2,⋯,K; in such an unusual case, the waiting time of an individual customer of a group under LGF is reduced not only by the effect of serving the largest group first but also by the effect of serving the shortest job first.) The condition (8) can be satisfied in a variety of group-arrival group-service queueing situations; under this condition, it can be (socially) profitable to serve the largest group first at the cost of fairness ensured by FIFO. This is further discussed in the following section.

### Remark 2.

Theorem 1 can be viewed as the well-known cμ rule, which means that the total expected cost can be minimized when customers are served in the order of values of , where c represents the cost per unit time of the waiting time of a customer (in our case, the group size i) and μ the service rate of a customer (in our case, the reciprocal of an expected group service time, i.e., 1/ E[Si] ); see, e.g., Wolff (1989) and Van Mieghem (1995). It can also be viewed as the WSEPT rule, namely, Weighted Shortest Expected Processing Time First rule, in stochastic scheduling (see, e.g., Koole and Righter, 2001;Pinedo, 2016). Note that the rule and the WSEPT rule are not necessarily optimal, particularly when more than two priority classes arrive to the system and they are not Poisson (Wolff, 1989;Pinedo, 2016); see Appendix for such an example. Nevertheless, Theorem 1 shows that for an arbitrary number of priority classes, LGF under the condition (8), a sort of rule, is superior to the conventional FIFO, at the very least.

## 3. COST-BENEFIT ANALYSIS

In this section, we evaluate the benefit of LGF against its cost, compared with its FIFO counterpart, and discuss its economic operation. To this end, for group size i =1,2,⋯,K, we let ri ≥0 denote the average revenue brought in from an individual customer of a group of size i and c≥0 denote the cost brought about per unit time of the waiting time of an individual customer. We assume that revenues and costs other than ri and c are negligible, and that they are independent of the priority rule; that is, {ri} and c under LGF is the same as those under FIFO. Then the total profit that the system earns per unit time (under either LGF or FIFO) is given by

$∑ i = 1 K i λ i { r i − c E [ W i ] }$
(16)

and from Eqs. (4) and (5), the difference per unit time between the total profit of the system under LGF and that under FIFO is given by

$c λ I { E [ W I ] F I F O − E [ W I ] L G F } .$
(17)

From Theorem 1, Eq. (17) is non-negative under the condition given by Eq. (8). Let us call this difference (17), which arises due to unfair treatment favorable to large groups, an unfairness benefit. Employing LGF rather than the conventional FIFO brings in this unfairness benefit.

Under LGF, in order to compensate customers of small groups for their extended waiting times, suppose discounts are given to them, such that $r 1 ≤ r 2 ≤ ⋯ ≤ r K = r$; that is, (rri) is an amount of the discount given to an individual customer of a group of size i (it is reasonable to assume $r 1 ≤ r 2 ≤ ⋯ ≤ r K$, such that the smaller a group size is, the more amount of discount each individual customer gets, although this assumption is not really necessary in the analysis below). Then, the difference (17) between the total profit per unit time under LGF and that under FIFO now reduces to

$c λ I { E [ W I ] F I F O − E [ W I ] L G F } − ∑ i = 1 K − 1 i λ i ( r − r i )$
(18)

Let us call the last summation of Eq. (18), or $∑ i = 1 K i λ i ( r − r i )$, a discount cost. Note that the difference (18) between the total profit under FIFO and that under LGF is now represented by the difference between the unfairness benefit and the discount cost.

Consider, for example, a linear discount in accordance with the size of a group: (rri)=(Ki)⋅d for i=1, 2,⋯,K−1 , that is, every individual from a group of size i gets an amount of (Ki)⋅d for a discount. Then the difference (18) specializes to

$c λ I { E [ W I ] F I F O − E [ W I ] L G F } − d ∑ i = 1 K − 1 i λ i ( K − i )$
(19)

When this linear discount is used, the maximum amount of d, say d* , which can be allowed for the system under LGF to achieve as much profit as that under FIFO, is determined by balancing the unfairness benefit with the discount cost in Eq. (19); as a result, we have

$d * = c λ I { E [ W I ] F I F O − E [ W I ] L G F } ∑ i = 1 K − 1 i λ i ( K − i )$
(20)

In order to compensate customers of small groups, consider now another discount method, in which the amount of the discount is not predetermined, but increases experientially in proportion to the number of overtakes a customer has gone through while waiting in queue. That is, a fixed amount of discount, say δ, is given to each individual customer every time she is overtaken by a larger group, such that if a customer is overtaken n times, she will get nδ off the regular price (thus, the amount of the discount she will collect is now a random variable, depending on the number of overtakes). Under the additional assumption of Poisson arrivals, the expected number of overtakes a customer of a group of size i has gone through while waiting in queue is given by $E [ W i ] L G F ⋅ λ ≥ i + 1$ on average, where $λ ≥ i + 1 = λ i + 1 + λ i + 2 + ⋯ + λ K$; as a result, we have $( r − r i ) = E [ W i ] L G F ⋅ λ ≥ i + 1 ⋅ δ$. Then the difference (18) specializes to

$c λ I { E [ W I ] F I F O − E [ W I ] L G F } − δ ∑ i = 1 K − 1 i λ i λ ≥ i + 1 E [ W i ] L G F$
(21)

When the experiential discount method is used, the maximum amount of δ, say δ* , which can be allowed for the system under LGF to earn as much profit as that under FIFO, is similarly determined as follows:

$δ * = c λ I { E [ W I ] F I F O − E [ W I ] L G F } ∑ i = 1 K − 1 i λ i λ ≥ i + 1 E [ W i ] L G F$
(22)

We remark that when the linear discount is employed with 0≤dd* , the system under LGF earns more profit than the same under FIFO; at the same time, individual customers of large groups benefit from lesser waiting times while those of small groups benefit from considerable discounts. The same is true when the experiential discount is employed with 0≤δδ* . In this regard, LGF can be socially preferable, since all the members of the society (the system owner and individual customers from any groups, whether large or small) can share out all the benefits obtained from LGF at the cost of fairness ensured by FIFO. This is demonstrated with the following numerical example.

For a numerical example, we present a group-arrival group-service M/G/1 queue with K =10 , λ =0.1 , pi = 0.1 , and an Erlang service time having the rate parameter being 2 / 9 and the shape parameter being 2, for all i=1, 2,⋯,10; as a result, E[Si]=9 and ρi =0.09 for all i=1, 2,⋯,10 and $ρ = ∑ i = 1 K ρ i = 0.9$. For FIFO, $E [ W ] F I F O$ =60.75 is obtained from the standard M/G/1 results; for LGF, $E [ W i ] L G F$ is obtained for all i =1,2,⋯,10 from the corresponding results for the non-preemptive priority M/G/1 queue (see, e.g., (2.24a) of Takagi, 1991); See Figure 1 below for their display. (Hereafter, we round off the numerical values, if needed to the second decimal place.) Consequently, $E [ W I ] L G F = ( i λ i / λ I ) E [ W i ] L G F$ = 25.50 and $E [ W I ] F I F O − E [ W I ] L G F =$ = 35.25 are obtained, which are the quantities of primary interest. It is confirmed that the work conservation given by Eq. (2) holds. Note that $E [ W 1 ] L G F = 319.74$ is about 50 times greater than $E [ W 10 ] L G F$ = 6.68 and about 5 times greater than $E [ W ] F I F O = 60.75$. Suppose a linear discount is employed with c=1. Then, from Eq. (20), we have d* =11.75 ; as a result, a customer from a group of size 1, say a solo customer, for example, gets a discount of 105.74. Suppose, on the other hand, an experiential discount with c = 1 is employed. Then, from Eq. (22), we have δ* = 23.31 ; as a result, a solo customer collects a discount of 670.82 in total (on average) in return for being overtaken 28.78 times (on average). Compared with her (expected) waiting cost $c E [ W 1 ] L G F = 319.74$, it is interesting to see that a solo customer is compensated less from the linear discount (105.74), whereas more from the experiential discount (670.82). Although the amounts of the discounts may differ according to the discount methods employed, one can see that customers of small groups can get substantial discounts by sharing out the social welfare obtained from the reduced expected individual waiting time under LGF (25.50 in this example).

## 4. CONCLUSIONS

In this paper, we discuss what we call the “Largest Group First” priority rule for queueing systems with group arrivals and group services. Under the condition (8), we show that the expected individual waiting time under LGF is always less than its FIFO counterpart. We show, in addition, that a queueing system under LGF can bring in more profit than the same under FIFO by giving priorities to larger groups while giving discounts to smaller groups.

In addition to the advantages discussed above, LGF has further considerable advantages as follows: First, LGF can reduce the loss of customers. Note that LGF results in a shorter waiting line by making smaller groups wait in line instead of larger ones (this can be easily seen from Little’s formula: $E [ N I ] = λ I E [ W I ]$, where Ni is the number of individual customers waiting in queue) Evidently, a long waiting line is likely to discourage incoming customers from joining the crowded line and it is also likely to discourage customers already waiting in line from withstanding the long line ahead of them. Thus, a shorter line under LGF is likely to invite more potential customers to join the system and to keep customers waiting in queue from withdrawing (which is also called reneging in queueing terminology). As such, LGF is likely to serve more customers than FIFO, bringing in larger sales as a result. Moreover, since a large group, which is likely to bring in a higher volume of sales, enjoys better treatment, there is more chance to invite and keep such a large group in the system, resulting in even larger sales. Thus, in addition to the profit discussed in Section 3, LGF can substantially increase the profit of the system further more. Finally, the longer the customers line, the larger space is required for them to wait. Hence, the service system needs to invest more in such a waiting space; otherwise, it can be filled up so quickly that the possibility of incoming customers being blocked can be too high. Such a blocking due to the finite waiting capacity can be detrimental particularly in telecommunication, manufacturing system and other related areas. Since the waiting line under LGF is shorter than its FIFO counterpart, blocking is less likely; thus, less waiting capacity is required, resulting in less investment in such a waiting capacity.

As we discuss in this paper, LGF has substantial advantages at the cost of fairness ensured by FIFO. In queueing systems, particularly where customers are not so much concerned about the fairness (as humans), such as jobs in the production and inventory systems, packets in the computer and telecommunication systems, LGF can be an even more considerable alternative for their economic designs and efficient operations.

## Appendix. An Example in which the cμ Rule is not Optimal

It is well known that the rule is optimal for nonpreemptive M/G/1 queues with an arbitrary number of priority classes (and their generalizations) and for the non-preemptive GI/G/1 queue with two priority classes (see, e.g. Wolff, 1989). Along these lines, one may jump to a conclusion that Theorem 1 is a special case of the rule. Under the setting we present in Section 2, however, rule is not necessarily optimal, as is demonstrated with a counter example in this Appendix .

In this example, we consider a queue with three priority classes, namely, class 1, 2, and 3 (representing a group of size 1, 2, and 3, respectively), and compare the (fixed) priority policy S321 and S312 , where the priority is given in the order of 3, 2, 1 and of 3, 1, 2, respectively (note that S321 corresponds to what we call the LGF policy). For this queue under the condition (8), we now derive $E [ W I ] S 312 < E [ W I ] S 321$ to show that S312 is a better one than S321 (a sort of rule); thus the rule is not optimal in this case.

Specifically, we assume pi (the probability that an arriving customer is an i -class customer or a group of size i) as follows:

$p 1 = p 2 = ϵ , p 3 = 1 − 2 ϵ □$
(A.1)

where ε is a sufficiently small positive number. We also assume that service times Si of i-class customers are deterministic as follows:

$S 1 = 1 + ϵ , ​ S 2 = 1 − 2 ϵ , S 3 = ϵ$
(A.2)

Note that the condition (8) holds for a sufficiently small positive ε.

We assume that an i-class customer (a group of size i) arrives to find the system empty at t0 = 0 and let tn be the arrival epoch of the n-th arrival, n = 1,2,3, ⋯. We also let An = tn - tn-1, n = 1,2,3, ⋯, to denote the interarrival time between the (n - 1)-th and n-th arrivals and assume

$A 4 k + 1 = A 4 k + 2 = ϵ / 4 , A 4 k + 3 = 1 , A 4 k + 4 = 4 , k = 0 , 1 , 2 , ⋯$
(A.3)

(Interarrival time can be generalized to have uniform distributions or even other ones.) From (A.2) and (A.3), it is obvious to see that $[ t 4 k , t 4 ( k + 1 ) )$, k = 0,1,2⋯, are regenerative cycles (see, e.g., Wolff, 1989). Note that there are exactly 4 arrivals during each cycle, whose length is $ϵ 2 + 5$. Hence, if we let LI and XI denote the number of individual customers who arrive during a cycle $[ t 4 k , t 4 ( k + 1 ) )$ and the sum of their waiting times, respectively, then the expected waiting time E[WI] of an individual customer in a steady state is given by

$E [ W I ] = E [ X I ] E [ L I ]$
(A.4)

where $E [ L I ] = 4 ∑ i = 1 3 i p i = 12 ( 1 − ϵ )$.

If we let Jl denote the class of the arrival at time t4k+l , l =0,1, 2, 3 , then E[X] can be expressed as follows:

$E [ X I ] = ∑ ( j 0 , j 1 , j 2 , j 3 ) ∈ { 1 , 2 , 3 } 4 P r ( J 0 = j 0 , J 1 = j 1 , J 2 = j 2 , J 3 = j 3 ) E [ X I | J 0 = j 0 , J 1 = j 1 , J 2 = j 2 , J 3 = j 3 ]$
(A.5)

Let M denote the number of arrivals during a cycle that are of either class 1 or class 2, i.e., $M = ∑ l = 0 3 1 { J l ≠ 3 }$, and let Im , m=0,1, 2, 3, 4 , denote the set of all possible combinations of $( J 0 , J 1 , J 2 , J 3 )$ when M = m , i.e., $I m = { ( j 0 , j 1 , j 2 , j 3 ) ∈ { 1 , 2 , 3 } 4 | M = m }$. Then from (A.1), we have

(A.6)

From (A.5) and (A.6), we have

(A.7)

Now, we let $E [ X I ] S 321$ and $E [ X I ] S 312$ denote E[XI] under S321 and S312 , respectively. When M =0 or 1 (i.e., either one 1-class or one 2-class customer, at most, during the cycle), it is obvious to see that no differences between S321 and S312 arise with respect to the order of service; differences arise only when M ≥ 2 ; as a result, we have from (A.7)

(A.8)

When M=2 , we work out all the possible sequences to find out that differences in the order of servic es arise only in the following two sequences: $( J 0 , J 1 , J 2 , J 3 )$ =(3,1, 2, 3) or (3, 2,1, 3) . To figure out the differences, we let $t 4 k + l '$, l =0,1, 2, 3 , denote the service completion epoch of the (4k +l) -th served customer. In these two sequences, since the first (3-class) customer arrives to find no customers in the system (at the regenerative epoch t4k ), she enters service immediately; as a result, $t 4 k ' − t 4 k = ϵ$. During her service time, note that two customers (namely, one 1-class customer and one 2- class customer) have arrived and they are waiting in the system at her service completion epoch $t 4 k ' − t 4 k = ϵ$. At this epoch, a difference arises between S321 and S312 with respect to which customer will be the next one to serve: under S321 , the 2-class customer will be the next to serve, whereas the 1-class customer will be the next under S312 . This initial difference in the order of service in turn brings about even more significant differences as follows. Under S321 , note that during the (rather shorter) service time of this “next” (2-class) customer, no customer has arrived. Thus the 1-class customer will be the next to serve and then finally, the 3-class customer. Under S312 , on the other hand, during the (rather longer) service time of this “next” (1-class) customer, note that 3-class customer (having the highest priority) has already arrived and she will be served next even though 2-class customer arrived even earlier than she did.

Consequently, under S321 , we have

$t 4 k ' − t 4 k = S 3 = ϵ , t 4 k + 1 ' − t 4 k = S 3 + S 2 = 1 − ϵ , t 4 k + 2 ' − t 4 k = S 3 + S 2 + S 1 = 2 , t 4 k + 3 ' − t 4 k = S 3 + S 2 + S 1 + S 3 = 2 + ϵ$
(A.9)

and from (A.3),

$t 4 k + 1 − t 4 k = ϵ / 4 , t 4 k + 2 − t 4 k = ϵ / 2 , t 4 k + 3 − t 4 k = 1 + ϵ / 2$
(A.10)

Hence, from (A.9) and (A.10), we have

$E [ X I | J 0 = 3 , J 1 = 1 , J 2 = 2 , J 3 = 3 ] S 321 = E [ X I J 0 = 3 , J 1 = 2 , J 2 = 1 , J 3 = 3 ] S 321 = ∑ l = 0 3 t 4 k + l ' − ∑ l = 0 3 t 4 k + l = 4 + O ( ϵ )$
(A.11)

Under S312 , on the other hand, we have

$t 4 k ' − t 4 k = S 3 = ϵ , t 4 k + 1 ' − t 4 k = S 3 + S 1 = 1 + 2 ϵ , t 4 k + 2 ' − t 4 k = S 3 + S 1 + S 3 = 1 + 3 ϵ , a n d t 4 k + 3 ' − t 4 k = S 3 + S 1 + S 3 + S 2 = 2 + ϵ$
(A.12)

Hence, from (A.12) and (A.10), we have

$E [ X I | J 0 = 3 , J 1 = 1 , J 2 = 2 , J 3 = 3 ] S 312 = E [ X I | J 0 = 3 , J 1 = 2 , J 2 = 1 , J 3 = 3 ] S 312 = ∑ l = 0 3 t 4 k + l ' − ∑ l = 0 3 t 4 k + l = 3 + O ( ϵ )$
(A.13)

Hence, from (A.8), (A.11), and (A.13), we have

(A.14)

Finally, from (A. 4) and (A.14), we have, for a sufficiently small positive ∊,

(A.15)

When a VIP customer is about to come (suppose this can be somewhat anticipated), it would be cost-effective to serve ordinary classes of customers (who has already been waiting in the system) in such an order that the costly VIP can be served as early as possible. Such an order is not necessarily the one from the rule. As is demonstrated in this Appendix, serving a customer with a longer service time (smaller , accordingly) earlier than one with a shorter service time (larger , accordingly) can significantly reduce the costly delay of the VIP and can be more cost-effective overall than the rule.

## ACKNOWLEDGMENTS

The authors are deeply indebted to Professor Bara Kim of Korea University for helping them out with Theorem 1 and the example in the Appendix.

## Figures

E[Wi ]LGF vs E[W]FIFO .

## References

1. Chaudhry, M. L. and Templeton, J. G. C. (1983), A First Course in Bulk Queues, John Wiley & Sons.
2. Doh, H. H. , Yu, J. M. , Kwon, Y. J. , Lee, D. H. , and Suh, M. S. (2016), Priority scheduling for a flexible job shop with a reconfigurable manufacturing cell, Industrial Engineering & Management Systems, 15(1), 11-18.
3. Federgruen, A. and Groenevelt, H. (1988), M/G/c queueing systems with multiple customer classes: Characterization and control of achievable performance under nonpreemptive priority rules, Management Science, 34(9), 1121-1138.
4. Hassin, R. and Haviv, M. (2003), To Queue or Not to Queue: Equilibrium Behavior in Queueing Systems, Springer Science & Business Media.
5. Koole, G. and Righter, R. (2001), A stochastic batching and scheduling problem, Probability in the Engineering and Informational Sciences, 15(4), 465-479.
6. Little, J. D. C. (1961), A Proof for the Queueing Formula: L = λW, Operations Research, 9, 383-387.
7. Oh, Y. , Kim, C. , and Melikov, A. (2013), A space merging approach to the analysis of the performance of queueing models with finite buffers and priority jumps, Industrial Engineering & Management Systems, 12(3), 274-280.
8. Pinedo, M. (2016), Scheduling:Theory, Algorithms, and Systems (5th ed.), Springer, New York.
9. Takagi, H. (1991), Queueing Analysis: A Foundation of Performance Analysis, Vol. 1: Vacation and Priority Systems. Amsterdam: North-Holland.
10. Van Mieghem, J. A. (1995), Dynamic scheduling with convex delay costs: The generalized c mu rule, The Annals of Applied Probability, 5(3), 809-833.
11. Wolff, R. W. (1989), Stochastic Modeling and the Theory of Queues, New Jersey: Prentice Hall.
 Do not open for a day Close