Abstract

We show that the expected value of any convex function of the waiting time (such as the variance) in a general queuing system under any queuing discipline independent of the service times does not exceed that under the last-come-first-served discipline, and is not less than that under the first-come-first-served discipline.

Introduction

It has been noted (see, for instance, Cohen (1969), Riordan (1962), Vaulot (1954)) that the variance of the waiting time in the and M/G/1 queuing systems under the last-come-first-served (LCFS) discipline exceeds that under service in the order of arrivals, first-come-first-served (FCFS). This observation has been made by comparison of explicit expressions for the variance. Moreover, in the cases when the waiting-time variance has been determined under service in random order (SIRO), it was found to attain an intermediate value (see Riordan 1962). The expected waiting times in all three cases are, of course, equal.

This has led to an interpretation of the FCFS discipline as more “fair” than either the SIRO or LCFS: While the expected waiting time of a given customer is not influenced, the total waiting time of all customers is more equally divided under FCFS than under SIRO, while the LCFS discipline is the least “egalitarian” of the three.

Vasicek (1965) has shown that in the system the variance of the waiting time actually attains its minimum and maximum for the FCFS and LCFS disciplines, respectively, within the following class of queueing disciplines: Let ; be given nonnegative numbers such that , . If the queue length at the instant of completion of service is n and the waiting customers are enumerated in the order of their arrivals, then the k-th customer is selected for service with probability . Obviously, the three previously mentioned queuing disciplines are special cases of this scheme. The proof of the proposition was specific for the Markov character of the system.

In this paper, we give a proof of a general statement that similar inequalities hold in any queuing system with an arbitrary arrival process and any service time distribution, as long as the service times are independent of each other and of the process of arrivals. The queuing discipline can be any rule of selection among the customers present in the system at that moment that is independent of their (future) service times. Such a rule can, however, depend on the past experience of the system. Actually, a more general result is proven, establishing inequalities for the expectation of any convex function of the waiting times.

Assumptions and Definitions

Consider a system, , with a queuing capacity. The arrival process is arbitrary. It could be temporally and spatially nonhomogeneous, and the interarrival times need not be independent. Group arrivals are possible. The queuing capacity can be limited or unlimited, and balking based on queue length is permitted. It is assumed that the service times are independent identically distributed variables that are independent of the arrival process. We assume further that each period of nonempty queue (“queue” meaning the customers in the system that are not in service) is finite with probability 1. The symbol will be used to denote a system with a homogeneous renewal process of arrivals and independent identically distributed service times.

We will restrict the use of the term queuing discipline to any rule of selection for service from the queue that is independent of the service times of the customers in queue at the instant of selection. In other words, it is required that the selection rule does not anticipate the service times. Such a rule may, however, depend on any other aspect of the system, such as the arrival times of the customers in the queue.

The disciplines FCFS and LCFS (as well as SIRO) are obviously admissible under the definition. On the other hand, consider a system with several classes of customers, each class having a different service time distribution but independent Poisson arrivals. Such a system can be viewed as a single-class system with a service time distribution that is a mixture of the distributions for individual classes. A priority assignment to the classes will not constitute a queuing discipline in the previous sense.

The Main Results

Theorem 1. Let D be a queuing discipline in a system. Let the number of customers entering service during a period of nonempty queue be n, and denote by the waiting times under the discipline D. Let and be the waiting times under the FCFS and LCFS disciplines, respectively. Then for any convex function f on ,

1

Moreover, the quantity does not depend on the queuing discipline.

The proof of the theorem is based on the following lemma:

Lemma. Let , be two series of numbers such that , . Let be any permutation of such that

2

Put , , where ; ], . Let f be a convex function on , and define . Then .

Proof. Let R be a permutation of such that (2) holds. If R = , then . Suppose then that . Then there exist such that , . Define a permutation by , , . Obviously, , . Then

3

If , then . Let , and put . Write (3) as

4

Since , it follows from the convexity of f that the right-hand side of (4) is nonnegative, and consequently .

If , then . If , then there must exist such that , . In that case, a new permutation can be defined by interchanging and with the value of V not smaller than . This process can be repeated until permutation is reached. This will happen in a finite number of steps because each new permutation contains more inversions than the previous one, so that they are all distinct. This establishes the inequality .

Again, let R be a permutation such that (2) holds. If , then . Assume that . Then there exist i, j such that . Define a permutation by , , . Clearly, , . But R is obtained from by an operation that has been shown not to decrease the value of V, and consequently . Repeated construction of new permutations by interchanging inversions leads in a finite number of steps to , and therefore . This completes the proof of the lemma.

Proof of Theorem 1. Let be the arrival times of the n customers entering service during a period of nonempty queue, and let be the epochs of commencement of service under a queuing discipline D. Let , be the epochs of commencement of service under the disciplines FCFS and LCFS, respectively. Since the selection from the queue under a queuing discipline is independent of the service times of the customers in queue, the distributions of , and are all the same.

Let be the order in which the customers are served under the discipline D; that is, the customer selected for the k-th service is the R(k)-th arrived. Obviously, R is a permutation of , and , . By the lemma

where and for .

But are the orders of service under the FCFS and LCFS disciplines, respectively, given that the service commencement times are s₁,…, s_n. The quantities , are the corresponding waiting times under D, FCFS, and LCFS, respectively. Since has the same distribution as , the actual waiting times under FCFS have the same joint distribution as , and . Similarly, the actual waiting times under LCFS have the same distribution as (here is not necessarily the actual order of service), and . This proves the inequalities (1). Now, since both and are convex functions, it follows that . Consequently, the sum of expected waiting times in a period of nonempty queue is independent of the queuing discipline. This completes the proof of Theorem 1.

The proof of Theorem 1 did not in fact require that the service times be independent identically distributed variables. All that was necessary was that the epochs of commencement of service had the same joint distribution under any queuing discipline. Thus the inequalities (1) will hold as long as the distribution of the service time does not depend on the particular customer served. If a barber doubles his speed when the queue is long, the FCFS and LCFS disciplines still distribute the total waiting time in the most equitable and least equitable fashion, respectively. On the other hand, the theorem does not hold when customers are selected for service based on the knowledge of their service times. If that customer is served first whose service time is the shortest among those waiting (the shortest remaining processing time rule), the total waiting time over a period of nonempty queue in fact decreases (see Schrage 1968).

In the special case when the waiting times are identically distributed we have

Theorem 2. Let D be a queuing discipline in a stationary system, and denote by the waiting times under D, FCFS, and LCFS, respectively. Then for any convex function f on ,

5

Moreover

6

Proof. Let W be the waiting time of a given customer. If the customer arrives while at least one service line is idle, then independently of the queuing discipline. Assume that the customer arrives while all service lines are busy. Because the system is stationary, such a customer is equally likely to be any of the (say) n customers entering service during that period of nonempty queue. If are the waiting times of these n customers, then , where the expectation on the left is conditional on n. Theorem 1 then implies the relations (5) and (6) conditionally on n. Since this is true for any n, the theorem follows.

By choosing where , we obtain:

Corollary 1. In a stationary system

7

The variance has been singled out for historical reasons. Obviously, inequalities similar to (7) hold for any moment of order at least 1, and for any absolute moment around the mean of order at least 1 (such as the mean absolute deviation). Another special case is given by

Corollary 2. Let be the Laplace transforms of the waiting times in a stationary system under an arbitrary queuing discipline and under the FCFS, LCFS disciplines, respectively. Then for any , .

References

1. Cohen, J. (1969). The Single Server Queue. Amsterdam: North-Holland, 1969.
2. Riordan, J. (1962). Stochastic Service Systems. New York: John Wiley & Sons.
3. Schrage, L. (1968). “A Proof of the Optimality of the Shortest Remaining Service Time Discipline.” Opns. Res., 16, 687–690.
4. Vasicek, O. (1965). “Poznámka k čekací disciplíně v systémech hromadné obsluhy.” Aplikace Matematiky, 10, 423–427.
5. Vaulot, E. (1954). “Delais d'attente des appels telephoniques dans l'ordre inverse de leur arrivee.” C. R. Acad. Sci. Paris, 238, 1188–1189.