4.9.2 Important Optimization Result


        A question that naturally arises in the design of queueing systems with priorities is how these priorities should be assigned to accomplish some desirable objective with regard to the performance of the queueing system. Obviously, the answer to this question will depend on the characteristics of the queueing system at hand and on the nature of the desirable objective. In general, questions of this type are among the most difficult to deal with in queueing theory.

        A most useful result in this area has been obtained for the nonpreemptive M/G/1 priority system which we have just analyzed. We consider again r distinct classes of users with Poisson arrivals (at a rate lamda.gif (291 bytes)k, for class k) and general service times (with mean 1/mu.gif (189 bytes)k, for class k) and with the priority arrangement described through Figure 4.15. Let us assume that for each class of users there is a cost ck, (k = 1, 2, . . . , r) for each unit of time that a user from this class spends in the system (in queue or in service).

        Suppose, then, that the objective is to minimize the average cost to all users per unit of time (for steady-state conditions); that is, we wish to minimize

form4.109.gif (3727 bytes)              (4.109)

Then the following holds true:

Theorem: To minimize (4.109) compute for each class k, the ratio fk, = Ck/(1/mu.gif (189 bytes)k). Then assign priorities according to the relative magnitudes of the r ratios: specifically, the higher the value of the ratio, the higher the priority of the class.

         In other words, we reorder the subscripts of the ratios fk, so that


form4.110.gif (2523 bytes)


Then the class of users that corresponds to the ratio f1 (i.e., that incurs the highest cost per unit of service time) is assigned top priority for access to the server, the class corresponding to the ratio f2 second highest priority, and so on. Note that this result holds only for the case when the costs of system time (or of waiting time) increase linearly with system (or waiting) time for all classes of users.

        No formal proof of the theorem will be presented here (the reader may wish to consult [KLEI 76], for one). It is simple, however, to argue intuitively for the theorem's validity by recognizing that minimizing C in (4.109) is the same as minimizing the expected area between the "cost inflow" and "cost outflow" curves in Figure 4.16. This figure is a modified version of Figure 4.3 in which the vertical axis represents "cost" instead of "number of users." We have no control over the "cost inflow" curve whose expected rate of growth per unit of time is constant and equal to formpg238.gif (1420 bytes). However, we can maximize the expected rate of growth of the "cost outflow" curve by always

fig4.16.gif (24094 bytes)

selecting among the available users the one that "expels" expected cost from the system at the maximum rate per unit of time. This is equivalent to choosing the user with the maximum ck mu.gif (189 bytes)k, (= rate of cost "expulsion" per unit time resulting from serving a user of class k) which confirms the theorem. It should also be noted that the first of the two terms on the right-hand side of (4.109) is a constant that is independent of the priority assignments. Therefore, to minimize (4.109) one must minimize the second sum on the right.

The following corollary follows from the theorem.

Corollary: To minimize the average waiting time for all users in the system, assign priorities according to the expected service times for each user class: the shorter the expected service time, the higher the priority of the class.

        To prove the corollary, all we have to do is set ck = 1 for all k in the theorem (this is equivalent to assigning equal weight to a unit of time's waiting for all classes of users). Then
fk=mu.gif (189 bytes)k, and the result of the corollary follows.
        The corollary we have just discussed is sometimes referred to as the 'Ishortest-expected-processing-time-first" (SEPT) rule. Note that, contrary to FCFS, SIRO, and LCFS, SEPT affects the distribution of the number of users present in the queueing system and the expected waiting and total system times by using a characteristic of the length of service time as the criterion for sequencing.