Chapter 37
An Inequality for the Variance of Waiting Time under a General Queueing Discipline

Operations Research, 25 (5) (1977), 879–884.

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 c37-math-0001 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 c37-math-0002 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 c37-math-0003; c37-math-0004 be given nonnegative numbers such that c37-math-0005, c37-math-0006. 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 c37-math-0007. 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 c37-math-0008 system, c37-math-0009, 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 c37-math-0010 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 c37-math-0011 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 c37-math-0012 system. Let the number of customers entering service during a period of nonempty queue be n, and denote by c37-math-0013 the waiting times under the discipline D. Let c37-math-0014 and c37-math-0015 be the waiting times under the FCFS and LCFS disciplines, respectively. Then for any convex function f on c37-math-0016,

1 equation

Moreover, the quantity c37-math-0018 does not depend on the queuing discipline.

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

Lemma. Let c37-math-0019, c37-math-0020 be two series of numbers such that c37-math-0021, c37-math-0022. Let c37-math-0023 be any permutation of c37-math-0024 such that

2 equation

Put c37-math-0026, c37-math-0027, where c37-math-0028; c37-math-0029], c37-math-0030. Let f be a convex function on c37-math-0031, and define c37-math-0032. Then c37-math-0033.

Proof. Let R be a permutation of c37-math-0034 such that (2) holds. If R = c37-math-0035, then c37-math-0036. Suppose then that c37-math-0037. Then there exist c37-math-0038 such that c37-math-0039, c37-math-0040. Define a permutation c37-math-0041 by c37-math-0042, c37-math-0043, c37-math-0044. Obviously, c37-math-0045, c37-math-0046. Then

3 equation

If c37-math-0048, then c37-math-0049. Let c37-math-0050, and put c37-math-0051. Write (3) as

4 equation

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

If c37-math-0055, then c37-math-0056. If c37-math-0057, then there must exist c37-math-0058 such that c37-math-0059, c37-math-0060. In that case, a new permutation can be defined by interchanging c37-math-0061 and c37-math-0062 with the value of V not smaller than c37-math-0063. This process can be repeated until permutation c37-math-0064 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 c37-math-0065.

Again, let R be a permutation such that (2) holds. If c37-math-0066, then c37-math-0067. Assume that c37-math-0068. Then there exist i, j such that c37-math-0069. Define a permutation c37-math-0070 by c37-math-0071, c37-math-0072, c37-math-0073. Clearly, c37-math-0074, c37-math-0075. But R is obtained from c37-math-0076 by an operation that has been shown not to decrease the value of V, and consequently c37-math-0077. Repeated construction of new permutations by interchanging inversions leads in a finite number of steps to c37-math-0078, and therefore c37-math-0079. This completes the proof of the lemma.

Proof of Theorem 1. Let c37-math-0080 be the arrival times of the n customers entering service during a period of nonempty queue, and let c37-math-0081 be the epochs of commencement of service under a queuing discipline D. Let c37-math-0082, c37-math-0083 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 c37-math-0084, and c37-math-0085 are all the same.

Let c37-math-0086 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 c37-math-0087, and c37-math-0088, c37-math-0089. By the lemma

equation

where c37-math-0091 and c37-math-0092 for c37-math-0093.

But c37-math-0094 are the orders of service under the FCFS and LCFS disciplines, respectively, given that the service commencement times are s1,…, sn. The quantities c37-math-0095, c37-math-0096 are the corresponding waiting times under D, FCFS, and LCFS, respectively. Since c37-math-0097 has the same distribution as c37-math-0098, the actual waiting times c37-math-0099 under FCFS have the same joint distribution as c37-math-0100, and c37-math-0101. Similarly, the actual waiting times c37-math-0102 under LCFS have the same distribution as c37-math-0103 (here c37-math-0104 is not necessarily the actual order of service), and c37-math-0105. This proves the inequalities (1). Now, since both c37-math-0106 and c37-math-0107 are convex functions, it follows that c37-math-0108. 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 c37-math-0109 system, and denote by c37-math-0110 the waiting times under D, FCFS, and LCFS, respectively. Then for any convex function f on c37-math-0111,

5 equation

Moreover

6 equation

Proof. Let W be the waiting time of a given customer. If the customer arrives while at least one service line is idle, then c37-math-0114 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 c37-math-0115 are the waiting times of these n customers, then c37-math-0116, 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 c37-math-0117 where c37-math-0118, we obtain:

Corollary 1. In a stationary c37-math-0119 system

7 equation

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 c37-math-0121 be the Laplace transforms of the waiting times in a stationary c37-math-0122 system under an arbitrary queuing discipline and under the FCFS, LCFS disciplines, respectively. Then for any c37-math-0123, c37-math-0124.

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.
..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
18.116.90.59