Admission Policies for a Two Class Loss System with General Interarrival Times

ADMISSION POLICIES FOR A TWO CLASS LOSS SYSTEM WITH GENERAL INTERARRIVAL TIMES

¨ E. Lerzan Ormeci Department of Industrial Engineering Ko¸c University Rumeli Feneri Yolu ˙ 34450 Sarıyer-Istanbul-Turkey Tel: (90-212) 338 15 34 Fax: (90-212) 338 15 48 e-mail: [email protected]

Jan van der Wal Department of Mathematics Technical University of Eindhoven Den Dolech 2 Postbus 513 5600 MB Eindhoven, The Netherlands Tel: (31-40) 243 29 19 Fax: (31-40) 243 66 85 e-mail: [email protected] / [email protected]

1

ADMISSION POLICIES FOR A TWO CLASS LOSS SYSTEM WITH GENERAL INTERARRIVAL TIMES

ABSTRACT This paper considers the problem of dynamic admission control in a loss queueing system with two classes of jobs. The classes require an exponential amount of service time with different means and bring different revenues, whereas the arrivals occur according to a general distribution. We establish the existence of optimal acceptance thresholds for both job classes and show that under certain conditions there exists a preferred class. We also provide an example that demonstrates that for a Markov modulated Poisson arrival process there may be states in which both classes are rejected.

2

1 INTRODUCTION In this paper, we consider the problem of dynamic admission control in a two class loss system with c identical parallel servers, and no waiting room. Interarrival times of jobs are independent and identically distributed according to a probability distribution function G with a finite mean. An arriving job is of class j with probability λj , j = 1, 2, where λ1 + λ2 = 1. Immediately upon arrival it has to be decided to accept or reject the job. Class-j jobs demand an exponential service time with mean 1/µj . If a class-j job is admitted, a reward of Rj > 0

1

is gained upon its arrival.

Without loss of generality, we assume µ1 ≤ µ2 , so class-1 jobs require longer service. Our objective is to find dynamic admission policies that maximize the total expected discounted revenue over an infinite horizon as well as the long-run average revenue. We prove that an optimal admission policy can be generally described as follows: An arriving job of class j is admitted to the system if and only if the number of available servers exceeds a certain threshold, which depends on the number of class-k jobs already being served, with k = j. In addition, we develop a set of sufficient conditions which ensures that a job class is preferred, in the sense that its jobs are always admitted if there are free servers, regardless of the system congestion level. We note that a system may have only one preferred class so that jobs of the other class are rejected in certain states, or it can have both classes preferred so that all jobs are always admitted whenever the system has at least one idle server. We also show that for systems with two servers there can be no state in which both classes are rejected and we conjecture that to be true for more than two servers as well. However, we also present a system with Markov modulated Poisson arrivals, that has a state in which it is optimal to reject both classes. ¨ This paper generalizes and extends the results obtained in Ormeci, Burnetas and van der Wal [1] for Poisson arrivals. Ziedins [2] is the only other paper we are aware of which considers non-Poisson arrivals in an admission control problem with identical 1

Rewards collected at the end can be translated to rewards collected upon acceptance.

3

parallel servers, where interarrival times are of phase type and service times for all ¨ admitted jobs are exponential with identical service rates. Ormeci et al. [1] provides a comprehensive literature review on the dynamic admission control of loss systems with identical servers receiving Poisson arrivals. Since then, there have been a number ¨ of studies in the area such as Savin, Cohen, Gans and Katalan [3], Ormeci and Burnetas [4], Ku and Jordan [5], and Ku and Jordan [6]. On the other hand, Righter [7] and Rykov [8] consider the problem of admission control in loss systems with heterogeneous parallel servers. This paper is organized as follows. In section 2, we present the Markov decision process model of the system. The third section proves the existence of optimal thresholds. Section 4 presents sets of sufficient conditions for each class to be preferred. In section 5 we discuss systems with no guaranteed preferred class: We consider the 2-server case and we present the example for Markov modulated Poisson arrivals.

2 THE SEMI-MARKOV DECISION MODEL 2.1 Markov Decision Model in Discrete Time for Finite Horizon The original process of the system described above evolves in continuous time. Since the interarrival times are general, the complete state of the system is (x, s) = (x1 , x2 , s), where s is the time passed since the last arrival, and xj is the number of class-j jobs in the system. However, as decisions are taken at arrival instants only, we can concentrate on the process embedded at these arrival epochs. It is useful to distinguish two kinds of states. The state just after the arrival of a type-j job is denoted as (x; j) = (x1 , x2 ; j), and the state immediately after the accept/reject decision is denoted by x = (x1 , x2 ). Further we define S = {x | 0 ≤ x1 + x2 ≤ c}. We define a value function for each type of state: vn (x; j) is the maximal expected β-discounted reward of a system in state (x; j) when, after the present arrival, there will be still n arrivals in the future. un (x) is the same quantity immediately after the 4

accept/reject decision has been taken. We define an (x; j) as the optimal action in state (x; j) with an (x; j) equal to 1 if it is optimal to accept the arriving job of class j and equal to 0 otherwise. In the sequel, we will use the terms period n and nth arrival interchangably. To describe the transition probabilities, we need a bit more notation. We denote by qj (t) = 1 − e−µj t the probability that a class-j job finishes its service before time t. Further, qxy (t) is the probability that exactly yj class-j jobs out of xj class-j in service, j = 1, 2, remain in the system till time t, so: 2

qxy (t) = j=1





 xj  

yj

 qj (t)

xj −yj

(1 − qj (t))yj

For two state vectors x and y, y ≤ x means that yj ≤ xj for j = 1, 2. We write e0 = (0, 0) and denote by ej the vector which has a 1 at the jth coordinate, and 0 at the other place. Then, for x1 + x2 < c we get the dynamic programming equations: vn (x; j) = max{Rj + un (x + ej ), un (x)} f or j = 1, 2 un+1 (x) =

∞ 0

(1)

2

e−βt

λj j=1

qxy (t)vn (y; j)dG(t) .

(2)

e0 ≤y≤x

For x1 + x2 = c we have an (x; j) = 0, so vn (x; j) = un (x). Further we define u0 (x) = 0 ,

x∈S .

2.2 Coupling In the proofs we frequently use coupling to show certain properties of the value function. Coupling is a widely used method in Markov decision models; see Righter [9]. When comparing two systems, we explicitly couple all the random variables for the two systems. Specifically, both systems will have the same arrival stream. The service times of jobs in the two systems are coupled as follows. If the coupled jobs are of the same class, they depart at the same time. If they belong to different classes we 5

use µ1 ≤ µ2 : If t is the next interarrival time, then with probability q1 (t) both jobs leave the system, with probability q2 (t)−q1 (t) the class-2 job departs from the system while the coupled class-1 job stays in the system, and with probability 1 − q2 (t) both jobs remain in the system. Thus, coupling never allows a coupled class-1 job to leave the system while the coupled class-2 job is still there. 2.3 Discounting In the sequel, we treat discounting as exponential failures: The system closes down after an exponentially distributed time with rate β, so at time t the system will still exist with probability e−βt , and will be shut down (with no future returns) with probability 1 − e−βt . 2.4 Infinite Horizon Models We prove all our results via dynamic programming (DP) for the objective of maximizing total expected β-discounted reward for a finite number of arrivals. Thus, finite horizon problems are pseudo finite problems. DP provides the powerful tool of induction to prove our results for any number of periods n. All the results proven for finite n are true for the limit n → ∞, so the corresponding conclusions are valid when total expected β-discounted reward over an infinite horizon is maximized (see e.g. Puterman [10]). Moreover, since the state and action spaces are finite, we have the same conclusions for maximizing the long-run average reward, i.e., β = 0 (see e.g. Puterman [10]). 2.5 Effect of an Additional Job If both accepting and rejecting a job is optimal we accept, so an (x; j) = 1

⇐⇒

un (x) − un (x + ej ) ≤ Rj .

(3)

The difference un (x) − un (x + ej ) is just the expected burden that an additional classj job brings to the system in state x when there are n more arrivals. The optimal 6

policy accepts a class-j job only if this burden is not more than its reward. These differences play a crucial role in determining the preferred class(es). Therefore, we define Dn (kj)(x) as the difference in the total expected discounted rewards between system A and system B if A starts in state x + ek and B starts in x + ej , when there are n more arrivals in the horizon (x + e0 = x). The four Dn (kj) functions of interest are Dn (01), Dn (02), Dn (12) and Dn (21) given by Dn (01)(x) = un (x) − un (x + e1 ), Dn (02)(x) = un (x)−un (x+e2 ) and Dn (21)(x) = −Dn (12)(x) = un (x+e2 )−un (x+e1 ). The difference Dn (21)(x) is the expected burden of changing a class-2 job in state x + e2 into a class-1 job, i.e., making the job larger. Now, we can relate a class being preferred to the Dn (kj). Since an (x; j) = 1 if and only if Dn (0j)(x) ≤ Rj , class-j jobs are preferred if and only if Dn (0j)(x) ≤ Rj for all x ∈ S. 3 EXISTENCE OF AN OPTIMAL THRESHOLD POLICY In this section we show that there exists an optimal policy which can be determined by optimal thresholds. Intuitively, we expect that the benefit of the system due to an additional job should decrease with the number of jobs in the system. Hence, it should be more difficult to accept jobs when there are many jobs already in the system. The following lemma establishes part of this intuition: The expected burden due to an additional job, is increasing in the number of jobs of the other class. Lemma 1 For all x ≥ 0 with x1 + x2 + 2 ≤ c (or equivalently for all x + e1 + e2 ∈ S): un (x) − un (x + e2 ) − un (x + e1 ) + un (x + e1 + e2 ) ≤ 0 ∀n ≥ 0 .

(4)

Proof. Clearly u0 = 0 satisfies the above inequality. We prove the statement by induction on the number of remaining arrivals, so assume that inequality (4) holds for n. Note that (4) implies and is in fact equivalent to: un (x) − un (x + b1 e1 ) ≤ un (x + b2 e2 ) − un (x + b1 e1 + b2 e2 ), 7

(5)

for all x + b1 e1 + b2 e2 ∈ S with b1 ≥ 1 and b2 ≥ 1 or even b1 ≥ 0 and b2 ≥ 0. Now, let A, B, C and D be the systems starting from states x, x + e1 , x + e2 and x + e1 + e2 , respectively, in period n + 1. We first show that vn (x; j) also satisfies this monotonicity. Consider a class-1 arrival. Let systems A and D take the optimal actions, let system B imitate the decision of system D and let system C imitate the decision of A. Setting aA = an (x; 1) and aD = an (x + e1 + e2 ; 1), we have: vn (x; 1) − vn (x + e1 ; 1) − vn (x + e2 ; 1) + vn (x + e1 + e2 ; 1) ≤ un (x + aA e1 ) − un (x + e1 + aD e1 ) − un (x + aA e1 + e2 ) + un (x + e1 + aD e1 + e2 ) ≤ 0, where the first inequality follows from the optimality of vn , and the second inequality is a special case of inequality (5). Similarly one may show that vn (x; 2) satisfies (4) as well. Now consider un+1 . Couple systems A, B, C, and D, so that, except for the additional jobs, they all behave in the same way. Moreover, pairwise couple the additional class-1 jobs in B and D, and the additional class-2 jobs in C and D. Let t be the time till the next arrival. Then, we have four different outcomes depending on the behavior of these additional jobs: With probability (1 − q1 (t))(1 − q2 (t)), both of them remain in the system, with probability q1 (t)(1−q2 (t)), the class-1 jobs leave and the class-2 jobs remain, with probability (1−q1 (t))q2 (t), the class-2 jobs leave and the class-1 jobs stay, and finally both additional jobs leave the system with probability q1 (t)q2 (t). So un+1 (x) − un+1 (x + e2 ) − un+1 (x + e1 ) + un+1 (x + e1 + e2 ) ∞

= 0

2

−βt

e

j=1



λj 

qxy (t)×

e0 ≤y≤x

(1 − q1 (t))(1 − q2 (t)) (vn (y; j) − vn (y + e2 ; j) − vn (y + e1 ; j) + vn (y + e1 + e2 ; j)) +q1 (t)(1 − q2 (t)) vn (y; j) − vn (y + e2 ; j) − vn (y; j) + vn (y + e2 ; j) +(1 − q1 (t))q2 (t) vn (y; j) − vn (y; j) − vn (y + e1 ; j) + vn (y + e1 ; j) 8

+q1 (t)q2 (t) vn (y; j) − vn (y; j) − vn (y; j) + vn (y; j)

dG(t) ≤ 0,

for x + e1 + e2 ∈ S. The first term in the integral is less than or equal to 0 since vn satisfies inequality (4), and all other terms are 0. Thus un , satisfies inequality (4) for all n.

2

Lemma 1 immediately implies the existence of an optimal threshold policy: Theorem 1 There exist numbers {lni (0), . . . , lni (c − 1)}, i = 1, 2 such that: an (x; 1) = 1 if x2 ≤ ln1 (x1 ) and 0 otherwise, an (x; 2) = 1 if x1 ≤ ln2 (x2 ) and 0 otherwise. One might expect that the optimal thresholds are also monotone, i.e., that the burden of an additional job is also increasing in the number of jobs of its own class. We have constructed 7200 examples with uniformly distributed interarrival times and 2700 examples with exponentially distributed interarrival times. In all these examples, we have observed monotone thresholds. However, we were not able to prove it technically because of disturbing effects at the boundary of S. 4 EXISTENCE OF A PREFERRED CLASS In this section, we show that for certain parameter values there exists a preferred class, i.e., a class that is admitted whenever there is an idle server. For this purpose, we first define G∗ (µj + β) =

∞

e−(µj +β)t dG(t) .

0

∗

In the sequel, we denote G (µj + β) by Gj . Note that Gj is just the probability that an arrival occurs before a class-j service completion and a system failure. The main results of this section are summarized in two theorems, each presenting a condition for one of the classes to be preferred. To derive these conditions, we need to 9

analyze the burden of an additional class-j job as well as the effect of changing a classk job to a class-j job. Subsection 4.1 gives lower bounds on Dn (01)(x), Dn (02)(x) and Dn (21)(x), while subsections 4.2 and 4.3 present sufficient conditions for class 1 and 2 to be preferred, respectively, using upper bounds on the same quantities. 4.1 Lower Bounds on the Differences Dn (0j)(x) and Dn (21)(x) The system collects the rewards upon arrival, so that the jobs already in the system bring no benefit, but only the burden of preventing us accepting new arrivals. So, un (x) contains only rewards obtained from future jobs. Hence, it is always preferable to be in a state where there are less or faster jobs, which is just what is stated in Lemma 2. Lemma 2 For j = 1, 2, for all x ∈ S and n ≥ 0: (1)

Dn (0j)(x) ≥ 0.

(2)

Dn (21)(x) = −Dn (12)(x) ≥ 0.

These statements can be proven by a straightforward sample path argument, which is essentially the same as for Poisson arrivals (see [1]). Hence, the proofs are omitted. 4.2 A Sufficient Condition for Class 1 to be Preferred We first derive a sufficient condition for class 1 to be preferred. For this purpose, we consider an upper bound on Dn (21)(x) simultaneously with an upper bound on Dn (01)(x): Lemma 3 For all x ∈ S and for all n, if (1)

Dn (01)(x) ≤ R1 and

(2)

Dn (21)(x) ≤ R1

Proof.

G1 −G2 G1 (1−G2 )

λ2 G1 (1−G2 ) (1−λ1 G2 )(1−G1 )

≤

R1 , R2

then

=: U.

Assuming the given condition to hold, we use induction on the number of

arrivals, n. Both statements hold for u0 (x) = 0 for all x ∈ S. Assume that both are 10

true for n. Now we have to consider two pairs of systems, one for Dn+1 (01)(x) and one for Dn+1 (21)(x). (1) Consider the pair for Dn+1 (01)(x): Assume that system A is in state x and system B is in x + e1 in period n + 1, and couple the two systems in such a way that except for the additional job in B, all service and interarrival times in both systems are the same. Moreover, A follows the optimal policy, whereas B rejects all jobs in period n + 1 unless the systems are already coupled. Let t be the next interarrival time. Then A will move to state y with probability qxy (t). If the additional job in B leaves the system before an arrival occurs, so with probability q1 (t), then B also moves to state y and the two systems couple. Otherwise, B moves to state y + e1 . Then three different outcomes are possible: System A may reject the incoming job, then the difference between the two systems due to the additional job in B, is preserved. If a class-1 job is accepted by A, the two systems couple with a difference of R1 in the value functions, and finally, acceptance of a class-2 job in A leads the two systems to two different states y + e2 and y + e1 with a difference of R2 in reward. Thus: Dn+1 (01)(x) ≤

≤

∞

e−βt

0

y≤x

∞ 0

qxy (t) (1 − q1 (t)) λ1 max{R1 , Dn (01)(y)} +λ2 max{R2 + Dn (21)(y), Dn (01)(y)} + q1 (t) · 0 dG(t)

e−βt y≤x

qxy (t)(1 − q1 (t)) (λ1 R1 + λ2 max {R2 + U, R1 }) dG(t)

= G1 · (λ1 R1 + λ2 max {R2 + U, R1 }) , where the first inequality is due to coupling, the second due to the induction hypotheses for Dn (01)(x) and Dn (21)(x), and the rest follows from

y≤x qxy (t)

= 1 and

1 − q1 (t) = e−µ1 t . If R1 ≥ R2 + U , we have Dn+1 (01)(x) < R1 trivially. Otherwise: Dn+1 (01)(x) ≤ G1 · λ1 R1 + λ2 R2 + λ2 R1 ≤

G1 − G2 G1 (1 − G2 )

R1 (λ1 G1 (1 − G2 ) + (1 − G1 )(1 − λ1 G2 ) + λ2 (G1 − G2 )) = R1 (1 − G2 ) 11

which follows by the assumption of the theorem, λ1 + λ2 = 1 and some algebra. (2) Now let system A be in state x + e2 and system B in x + e1 in period n + 1. Let t be the next interarrival time. Couple the additional class-2 job, say job J2 , in A with the additional class-1 job, say job J1 in B , as well as all other service and interarrival times. Then, with probability q1 (t) both J1 and J2 leave and the systems couple. The departure of J2 alone takes the systems to two different states, y and y + e1 , with probability qxy (t)(q2 (t) − q1 (t)). In this case, we let B reject all jobs, and A follow the optimal policy, which has exactly the same consequences as in part (1), the previous part of the proof. Finally, both J1 and J2 may remain in the system, so that the difference between the two systems is preserved. In this case we let A follow the optimal policy and B imitate the decisions of A , which is always possible since both systems have the same number of free servers. Hence: Dn+1 (21)(x) ≤

∞

e−βt

0

y≤x

qxy (t) q1 (t) × 0 +

(q2 (t) − q1 (t)) (λ1 R1 + λ2 max{R2 + U, R1 }) + (1 − q2 (t))U dG(t) ≤ (G1 − G2 ) (λ1 R1 + λ2 max{R2 + U, R1 }) + G2 U, where the first inequality is obtained from coupling, and the second one follows from y≤x qxy (t)

= 1, 1 − qi (t) = e−µi t and the induction hypotheses for both Dn (01)(x)

and Dn (21)(x). If R1 ≥ R2 + U , then Dn+1 (21)(x) ≤ otherwise

G1 − G2 G1 − G2 R1 (G1 + G2 (1 − G1 )) ≤ R1 , G1 (1 − G2 ) G1 (1 − G2 )

Dn+1 (21)(x) ≤ (G1 − G2 ) λ1 R1 + λ2 R2 + R1

G1 − G2 G1 (1 − G2 )

+ G2 R1

G1 − G2 G1 (1 − G2 )

G1 − G2 ((G1 + λ1 G2 (1 − G1 ))R1 + λ2 G1 (1 − G2 )R2 ) G1 (1 − G2 ) G1 − G2 ≤ ((G1 + λ1 G2 (1 − G1 ))R1 + (1 − G1 )(1 − λ1 G2 )R1 ) G1 (1 − G2 ) G1 − G2 = R1 , G1 (1 − G2 ) =

12

where the second inequality follows from the assumption of the theorem, and the rest is some algebra which uses λ1 + λ2 = 1 in particular.

2

Recall that Dn (01)(x) ≤ R1 for all x ∈ S and for all n implies that class 1 is always welcome. Hence, Lemma 3 immediately gives a sufficient condition for class 1 to be preferred: Theorem 2 If

λ2 G1 (1−G2 ) (1−λ1 G2 )(1−G1 )

≤

R1 , R2

then class-1 jobs are preferred.

To interpret this result we can look at the one-server system, for which there are three possible policies, to accept only class 1, only class 2 or to accept both classes. A straightforward evaluation of the corresponding value functions gives the following optimality conditions: Theorem 3 For the 1-server system we have (i) It is optimal to accept only class-1 jobs if and only if (ii) It is optimal to accept all jobs if and only if

(1−λ2 G1 )(1−G2 ) λ1 G2 (1−G1 )

≤

R1 . R2

λ2 G1 (1−G2 ) (1−λ1 G2 )(1−G1 )

≤

R1 R2

R1 R2

≤

λ2 G1 (1−G2 ) . (1−λ1 G2 )(1−G1 )

(iii) It is optimal to accept only class-2 jobs if and only if

≤

(1−λ2 G1 )(1−G2 ) . λ1 G2 (1−G1 )

So the conditions for class 1 to be preferred in Theorems 2 and 3 are the same. Hence, if class 1 is preferred in a 1-server system, then also in the multiple-server system. 4.3 A Sufficient Condition for Class 2 to Be Preferred In this section we derive a sufficient condition for class 2 to be preferred by finding an upper bound on Dn (02)(x): Lemma 4 If

R1 R2

≤

1−λ2 G2 , λ 1 G2

then Dn (02)(x) ≤ R2 for all x ∈ S and for all n.

13

Proof. Assume that the given condition is true. We use induction to prove the result. Obviously u0 (x) = 0 for all x ∈ S satisfies the claim. Assume that the statement is also true for period n, and consider period n+1. Now we use a sample path argument. Let system A be in state x and system B in x + e2 in period n + 1. Couple the two systems so that except for the additional job in B, all service and interarrival times in both systems are the same. Let t be the time till the next arrival. Then A will move to state y with probability qxy (t). With probability q2 (t), the additional job in B leaves the system before an arrival occurs, so B also moves to state y, and the two systems couple. Otherwise, B moves to state y + e2 . In that case, we let A take the optimal actions and B reject all jobs in period n+1, which may lead to three different outcomes. System A may reject the incoming job, then the difference between the two systems due to the additional job in B, is preserved. If A accepts a class-1 job the two systems are led to two different states y + e1 and y + e2 with a difference of R1 in reward. If A accepts a class-2 job the two systems couple with a difference of R2 in reward. Thus: Dn+1 (02)(x) ≤

≤

∞

e−βt

0

y≤x

∞

qxy (t) (1 − q2 (t)) λ1 max{R1 + Dn (12)(y), Dn (02)(y)} +λ2 max{R2 , Dn (02)(y)} + q2 (t) × 0 dG(t)

e−βt

0

y≤x

qxy (t)(1 − q2 (t)) (λ1 max{R1 , R2 } + λ2 R2 ) dG(t)

= (λ1 max{R1 , R2 } + λ2 R2 ) G2 where the first inequality is due to the coupling, the second inequality follows from the induction hypothesis and part 2 of Lemma 2, and the rest follows from

y≤x qxy (t)

=1

and 1 − q2 (t) = e−µ2 t with some algebra. Now, if R1 ≤ R2 , obviously Dn+1 (02)(x) < R2 . Otherwise, the assumption of the theorem implies: Dn+1 (02)(x) ≤ G2 (λ2 R2 + λ1 R1 ) ≤ R2 . From this we have: 14

2

Theorem 4 If

R1 R2

≤

1−λ2 G2 , λ1 G2

then class-2 jobs are preferred.

Contrary to class 1, the condition for class 2 to be preferred does not coincide with that in 1-server systems: Comparison of the conditions given in Theorem 3 and Theorem 4 shows that systems with more than one server and with parameters such that: R1 (1 − λ2 G1 )(1 − G2 ) 1 − λ2 G2 < < λ1 G2 R2 λ1 G2 (1 − G1 )

(6)

may reject class-2 jobs in several states, even though the 1-server system always accepts them. The region specified by (6) is always nonempty, so for all systems there are certain values of R1 and R2 for which the system preference for class 2 may change with the additional servers. The following example presents such a system. Example 1: Consider the system with service rates µ1 = 0.5, µ2 = 4, rewards R1 = 1.8, R2 = 0.255, and discount rate β = 0. Assume that the arrival process is Poisson with λ = 3.01, where λ1 = 3/3.01 and λ2 = 0.01/3.01. Then, the left-hand side of (6) is 2.3333, and right-hand side is 9.3333, while R1 /R2 = 7.0588. For c = 1, .., 5, both classes are preferred, whereas class-2 jobs are rejected in a few states for c = 6, .., 32. Finally, when 33 ≤ c ≤ 50, both classes are again preferred. Note that this system prefers class 1 by Theorem 2. As 1 ≤

1−λ2 G2 , λ 1 G2

Lemma 4 also proves the following intuitively obvious corollary.

Corollary 1 Whenever R1 ≤ R2 , so that class-2 jobs bring higher rewards, and require shorter service times, class-2 jobs are preferred. Remark 1 Using a straightforward sample path argument one may show that this corollary also holds for general service time distributions if the service time for class2 jobs is stochastically smaller than the one for class 1.

5 BEYOND PREFERRED CLASS WITH DIFFERENT ARRIVAL REGIMES 15

From Theorem 3, we know that there is always at least one preferred class in a one-server system. However, for systems with more than one server, the sufficient conditions for each class to be preferred are not complementary, i.e., for certain values of parameters our results cannot claim that there exists a preferred class: Remark 2 If the parameter values are such that: 1 − λ2 G2 R1 λ2 G1 (1 − G2 ) , < < λ1 G2 R2 (1 − λ1 G2 )(1 − G1 )

(7)

then our results are inconclusive. In some systems, the inconclusive region given by (7) is empty since its right-hand side is less than its left-hand side. Such systems have a preferred class for all possible values of R1 and R2 . The system in Example 1 is one of them since the left-hand side of (7) is 2.3333, and its right-hand side is 0.01995. Example 2, on the other hand, presents a system for which our results are inconclusive: Example 2: Consider the system introduced in Example 1, but now λ is increased to 301. Then the left-hand side of (7) becomes 1.0133, and its right-hand side 1.6. Now, we consider different values of R2 , for which R1 /R2 lies in the inconclusive region: When R2 is increased to 1.126 so R1 /R2 = 1.5986, class-1 jobs are rejected in the 1-server system, although both classes are preferred in systems with c servers, where 2 ≤ c ≤ 50, i.e., the increase in capacity works in favor of class 1. For 1.205 ≤ R2 ≤ 1.7763, i.e., when 1.0133 ≤ R1 /R2 ≤ 1.4938, class 2 is the only preferred class for all c with 1 ≤ c ≤ 50, since all these systems reject class-1 jobs in at least one state.

¨ Ormeci et al [1] discusses several issues on the existence of preferred class. Here, we investigate systems for which our preferred class results are inconclusive. Whenever there is not a preferred class, we know a little about the optimal policy: We still have 16

a threshold policy, and it is also easy to show that an optimal policy has to use all the servers: Proposition 1 An optimal policy has to utilize all the servers in the system. Proof.

Let π ∗ be an optimal policy which always keeps at least one server idle.

Policy π that serves the rejected jobs under π ∗ in the “always” idle server whenever possible, while imitating π ∗ in all other decisions performs strictly better than policy π ∗ , a contradiction.

2

Our results, so far, do not guarantee that in each state at least one of the two classes has to be accepted. The next subsection shows that for the 2-server system it is never optimal to reject both classes in a state. In subsection 5.2 we consider a different arrival process, a Markov modulated Poisson process, for which we present an example in which it is optimal to reject both classes in one of the states. 5.1 The 2-Server System This section proves that it is never optimal to reject both of the classes in any state only for systems with two servers. Theorem 5 In the 2-server system in each state at least one of the classes is accepted. Proof.

Both servers have to be utilized by Proposition 1. Thus, at least one of

the classes has to be accepted in state (0, 0). Both classes can be rejected in either state (1, 0) or (0, 1). Assume that there is an optimal policy, π ∗ , which rejects both classes in state (1, 0). Then, class-2 jobs have to be accepted in state (0, 0) and at least one of the classes has to be accepted in state (0, 1). Let systems A and B be in state (1, 0) initially and let them follow policy π ∗ and π, respectively, where policy π accepts class-2 jobs in state (1, 0). The two systems differ with a class-2 arrival upon which system A stays in state (1, 0), while system B moves to (1, 1) with an 17

additional reward of R2 . Now, till one of the jobs leave the system, there will not be any change in the states of the two systems, since A, i.e., π ∗ is rejecting all the jobs in this state due to our assumption, and since in B both servers are occupied. If the class-2 job in B leaves the system, then the two systems couple with B having an additional reward of R2 . Hence, policy π performs better in this case. If the class-1 job in both systems finishes its service, then A is in state (0, 0) and B in (0, 1). If there is a class-2 arrival, B rejects this job whereas A accepts so that both systems couple. If it is optimal for A to accept class-1 jobs, B also accepts the arriving class-1 job so that then A and B move to states (1, 0) and (1, 1), respectively. Then, the process repeats itself, therefore policy π performs better than policy π∗ , which is a contradiction. If an optimal policy is assumed to reject both classes in state (0, 1), existence of a better performing policy can be shown by a similar argument. Therefore, it is never optimal to reject both classes in any state for a two-server system.

2

This line of proof fails for more than 2 servers. Nevertheless we expect the following to be true. Conjecture 1 For renewal arrivals and any number of servers, in each state at least one of the classes is accepted. 5.2 Systems with Markov Modulated Poisson Arrivals ¨ From Ormeci et al [1], we know that when the arrival rates and the probability of class-j arrivals vary, different preferred classes can be observed even though all other parameters of the system remains the same. In this section, we consider systems receiving a Markov Modulated Poisson Process (MMPP) in order to combine different arrival streams which induce different preferred classes. We first present the corresponding MDP. Denote the underlying Markov process for the MMPP by P, which has a state space Π and transition intensities πk,l , 18

k

λ1 (k)

λ2 (k)

1

0.36

0.01

0

0.00001 0.00001

2

1

100

Table 1: Arrival rates in different states of P, k ∈ Π so that class-j jobs arrive at the system with rate λj (k) whenever P is in state k. Let A = maxk∈Π { L = maxk∈Π {

j=1,2

l=k

πk,l } be the maximum rate of change in MMPP, and

λj (k)} be the maximum total arrival rate. Then, we can use

uniformization and normalization by assuming A + L + cµ2 + β = 1 to construct a MDP of this system, which gives the following optimality equations: For x1 + x2 < c: vn (k; x; j) = max{un (k; x + ej ) + Rj , un (k; x)} and for x1 + x2 = c: vn (k; x; 1) = vn (k; x; 2) = un (k; x), where for x1 + x2 ≤ c: un+1 (k; x) =

xj µj un (k; x − ej ) +

λj (k)vn (k; x; j) + j

+(1 − β −

j

j

λj (k) −

j

xj µj −

πk,l un (l; x) l=k

πk,l )un (k; x). l=k

Now we present an example in which in one state it is optimal to reject both classes: Example 3: Consider a system with 6 servers for which we want to maximize average rewards, so β = 0. The other parameters of the system are as follows: µ1 = 0.05, µ2 = 4, R1 = 18, and R2 = 0.255. Jobs arrive at the system according to a MMPP, P, with the state space Π = {0, 1, 2}: Hence, each state in Π corresponds to an arrival stream specified in Table 1; e.g., if P is in state 1, then arrivals are Poisson with rate 19

1 1

0

-0.001 0.001

2 0

0

50

-200

150

2

0

0.001 -0.001

Table 2: Transition rates of P

Figure 1: Optimal policies for systems with Poisson arrivals (a) λ1 = 0.36 and λ2 = 0.01, (b) λ1 = 0.00001, and λ2 = 0.00001, and (c) λ1 = 1, and λ2 = 100.

20

Figure 2: The optimal policy for the system receiving arrivals according to MMPP specified by Table 1 and Table 2, where (a) P is in state 1, (b) P is in state 0, (c) P is in state 2. 0.37, and probability of a class-1 arrival is 0.36/0.37. The optimal policies for systems receiving Poisson arrivals with these rates are given in Figure 1. States of P are labeled in such a way that in states 1 and 2, classes 1 and 2 would be preferred, respectively, if only the corresponding arrival stream in each state was observed, whereas in state 0 both classes would be preferred. The two arrival streams with single preferred class communicate weakly through the intermediate state 0 which normally would induce two preferred classes. Here the arrival process stays in state 0 for a very short time. Further, in state (1;5,0) only class 1 is accepted, whereas in state (2;5,0) only class 2 jobs. When the system is in state (0;5,0) the next state will be with very high probability (1;5,0) or (2;5,0). The results show that in state (0;5,0) both classes are rejected, apparently because in state (0;5,0) the system prefers to wait until the next state of P is known.

21

References ¨ [1] E. L. Ormeci, A. Burnetas, and J. van der Wal. Admission policies for a two class loss system. Stochastic Models, 17:513—540, 2001. [2] I. Ziedins. Optimal admission controls for erlang’s loss system with phase-type arrivals. Prob Eng Inf Sci, 10:397—414, 1996. [3] S. Savin, M. Cohen, N. Gans, and Z. Katalan. Capacity Management in Rental Businesses with Heterogeneous Customer Bases. Operations Research, under revision, 2000. ¨ [4] E. L. Ormeci and A. Burnetas. Admission control with batch arrivals. Operations Research Letters, 32:448—454, 2004. [5] C. Ku and S. Jordan. Access control of parallel multiserver loss queues. Performance Evaluation, 50:219—231, 2002. [6] C. Ku and S. Jordan. Near optimal admission control for multiserver loss queues in series. Euro. J. Oper. Res., 144:166—178, 2003. [7] R. Righter. Expulsion and scheduling control for multiclass queues with heterogeneous servers. Queueing Systems, 34:289—300, 2000. [8] V. V. Rykov. Monotone control of queueing systems with heterogeneous servers. Queueing Systems, 37:391—403, 2001. [9] R. Righter. Scheduling. In M. Shaked and J. G. Shanthikumar, editors, Stochastic Orders and Their Applications. Academic Press, 1994. [10] M. Puterman. Markov Decision Processes. John Wiley and Sons Inc., New York, 1994.

22