Online Library → M. I Reiman → Dynamic scheduling of a two-class queue with setups → online text (page 1 of 4)

Font size

HUZO

.M414

/V3.

t-o

Dewey

WORKING PAPER

ALFRED P. SLOAN SCHOOL OF MANAGEMENT

Dynamic Scheduling of a Two-Class Queue

with Setups

Martin L Reiman

Lawrence M. Wein

#3692-94-MSA

May 1994

MASSACHUSETTS

INSTITUTE OF TECHNOLOGY

50 MEMORIAL DRIVE

CAMBRIDGE, MASSACHUSETTS 02139

Dynamic Scheduling of a Two-Class Queue

with Setups

Martin I. Reiman

Lawrence M. Wein

#3692-94-MSA May 1994

M.I.T. LIBRARiES

:' JUN 2 1994

RECEIVED

Dynamic Scheduling of a Two-Class Queue with Setups

Martin I. Reiman

AT&T Bell Laboratories

Murray Hill, NJ 07974

Lawrence M. Wem

Sloan School of Management, M.I.T.

Cambridge, MA 02139

ABSTRACT

We analyze two scheduling problems for a queueing system with a single server and two cus-

tomer classes. Each class has its own renewal arrival process, general service time distribution

and holding cost rate. In the first problem, a setup cos* is incurred when the server switches

from one class to the other, and the objective is to minimize the long run expected average

cost of holding customers and incurring setups. The setup cost is replaced by a setup time in

the second problem, where the objective is to minimize the average holding cost. By assuming

that the queueing system operates under standard heavy traffic conditions, we approximate the

dynamic scheduling problems by diffusion control problems. For both problems, considerable

insight is gained into the nature of the optimal policy, and the computational results show

that the proposed scheduling policy is within several percent of optimal over a broad range of

problem parameters.

APRIL 1994

We consider two dynamic scheduling problems for a single server queueing system with two

classes of customers. In both problems, each class possesses its own renewal arrival process,

general service time distribution and holding cost rate, and the server incurs a setup when

switching from one class to the other. In the setup cost problem, a setup cost is incurred and

the objective is to minimize the long run expected average setup and holding cost. In the

setup time problem, a random setup time is incurred when the server switches class, and the

objective is to minimize the long run expected average holding cost. In both problems, the

server has three options at each point in time: serve a customer from the class that is currently

set up, switch to the other class (and immediately begin service in the setup cost problem), or

sit idle.

These scheduling problems have numerous applications, most notably for manufacturing

systems and polling systems in computer communication networks. The setup time problem

is more realistic than the setup cost problem in most situations, but is also n^rre difficult to

analyze. However, the setup cost problem is relevant for some manufacturing systems because,

motivated by just-in-time (JIT) manufacturing, many facilities have internalized their setup

times; that is, they have essentially ehminated their setup times at the expense of incurring

significant material, labor and/or capital costs.

Although many studies have analyzed the performance of polling systems under various

scheduling policies (see Takagi 1986, Boxma and Takagi 1992 and references therein), relatively

few papers have considered the optimal scheduling of polling systems. The seminal paper in

this research area is Hofri and Ross (1987), who analyze a two-class system with setup costs

and times. Let c, and //, denote the holding cost rate and service rate, respectively, for class

i customers. When ci^i = C2H2, they show that a double threshold policy, where the server

serves each class until its queue is exhausted and the length of the other queue achieves a

certain threshold level, minimizes the cost of setups and holding customers, under both the

discounted and average cost criteria. Very little is known about the polling problem when

ciMi Â¥" f2M2, aside from the fact that the class with the larger cfi index should be served to

exhaustion.

Several authors have studied the setup time problem in which more than two classes are

present. Structural results for symmetric systems are derived by Liu, Nain and Towsley (1991)

and references therein. Browne and Yechiali (1989) derive quasi-dynamic index policies, which

allow the server to choose the sequence of classes to visit at the beginning of each cycle, that

minimize or maximize the mean cycle length. Boxma, Levy and Westrate (1991) derive an

efficient polling table (a predetermined fixed visit sequence) for minimizing the mean waiting

cost. Bertsimas and Xu (1993) derive lower bounds and construct static policies that perform

close to the bound when all classes have identical c/i indices. Van Oyen and Duenyas (1992)

develop a dynamic scheduling heuristic based on myopic reward rates; Duenyas and Van Oyen

(1993) also construct a dynamic policy for the setup cost problem.

Since the two-class asymmetric problem appears to be analytically intractable, heavy traffic

approximations are employed in an attempt to make further headway. T'lat is, we make the

heavy traffic assumption that the server must be busy the great majority of the time to satisfy

demand. In the setup cost problem, we also need to assume that the setup costs are very large,

roughly two orders of magnitude larger than the holding cost rate. Following in the tradition

of Foschini (1977) and Harrison (1988), we study the diffusion control problem that arises as

a heavy traffic Hmit of a sequence of queueing scheduling problems. These limiting control

problems tend to be more tractable than their queueing counterparts and have led to network

scheduling policies (see, for example, Harrison and Wein 1990 and Wein 1990b) that have a

surprisingly simple form and appear to perform well.

1

Using the heavy traffic averaging principle derived in Coffman, Puhalskii and Reiman

(1993), we show in Section 1 that the setup cost problem simplifies rather dramatically in the

limiting heavy traffic regime: the dimension of the state space collapses from three (queue

length of each clciss and the position of the server) to one (total workload). This result also

allows our analysis to naturally decompose onto two different time scales. On the very fast

time scale over which individual queue lengths change, we myopically optimize a control that

specifies the amount of low priority work to serve as a function of the total workload. This state-

dependent control is derived in closed form and offers considerable insight. On the slower time

scale over which the total workload varies, a singular control problem is solved that specifies a

busy/idle pohcy. The solution to this control problem leads to a rather complex equation for

one variable, which represents a threshold level, that can easily be solved numerically.

The setup time problem is addressed in Section 2, and the averaging principle in Coffman,

Puhalskii and Reiman (1994) leads to a limiting control problem that again is one-dimensional,

although here we obtain an explicit diffusion control problem. The control, which represents

the amount of low priority work to serve as a function of the total workload, appears in the drift

term of the diffusion process in a nonlinear fashion, and consequently the optimahty equation

leads to a nonlinear ordinary differential equation (ODE) that cannot be solved explicitly.

However, we use asymptotics to obtain a scheduling policy; the asymptotics also reveal a

substantial qualitative difference between the optimal policies in the setup cost and setup time

cases.

For both problems, we use the value iteration algorithm to obtain "exact" optimal policies

for a variety of test cases, and show in Section 3 that the suboptimality of the proposed policies

is within several percent of optimal over a broad range of problem parameters.

Our presentation of the analysis, and indeed the analysis itself, is rather informal through-

out. For example, we do not prove that the limiting control problems are the heavy traffic

limit of a sequence of queueing scheduling problems. Also, several of our claims regarding the

nature of the limiting control problems and their optimal solutions are not proved. Providing

a rigorous presentation of our results would be extremely demanding, and would take us far

afield from our two main objectives: to obtain fundamental insights into the nature of the

optimal policies and to develop effective scheduling policies for these systems. However, much

of our analysis relies upon observations that have been rigorously proven for simpler systems,

and we have no doubt that our results are essentially correct. We hope that this approach

increases the accessility of the paper without sacrificing the persuasiveness of our arguments.

1 THE SETUP COST PROBLEM

1.1 Problem Description

Customers of class i = 1,2 arrive according to independent renewal processes, where A, and

c^j denote respectively the arrival rate and squared coefficient of variation (variance divided

by the square of the mean) of the interarrival times. Each class has its own general service

time distribution with service rate /Xj and squared coefficient of variation c^j, and we define the

system's traffic intensity by p = Yn=i{^i/f^i)- A cost c, is incurred per unit time for holding

a class i customer in the system. A setup cost K/2 is imposed whenever the server switches

from one class to the other, so that A' is the setup cost per cycle.

The server hcis three scheduling options at each point in time: serve the class that is

currently set up, switch to the other class and initiate service, or sit idle. Since a switchover

is instantaneous and costly, the option of switching to the other class and idling need not be

considered. We assume that the server works in a preemptive-resume fashion, although the

heavy traffic analysis is too crude to capture the effects of the nonpreemptive discipline as an

alternative assumption. Let Qi{t) be the number of class i customers in queue or in service at

time t, and let J{t) denote the number of times the server sets up in the time interval \0,t\.

Then our objective is to find a nonanticipating (with respect to the queue length process)

scheduling policy to minimize

limsup â€”;E

r-.oo T

rY,c,Q,{t)dt+^^J{T)

Jo ~1 ^

(1.1)

1.2 The Heavy Traffic Normalizations

A precise formulation of the approximating diffusion control problem requires much nota-

tion that would not be subsequently used. In addition, the limiting control problem will not

be explicitly solved; rather, we optimize over a specific form of policy that is introduced in

Subsection 1.4. Hence the heavy traffic control problem will not be precisely formulated, and

a description of the heavy traffic conditions and normalizations will suffice for our purposes.

The approximating control problem is the limit of a sequence of scheduling problems in-

dexed by the heavy traffic scaling parameter n, where n â€”>â– oo. Since a heavy traffic limit

theorem will not be proved here, we avoid unnecessary notation by considering a single large

integer n satisfying y/n{l â€” p) = c, where c is positive and of moderate size (that is, 0(1)); this

standard heavy traffic condition requires the server to be busy the great majority of the time

over the long run. As we will see later, the scheduling policy that arises out of our heavy traffic

analysis is independent of the system parameter n. Let V, be the unfinished workload process

for class i; Vi{t) is the amount of time a continuously busy server requires to clear all of the class

i customers who are present in the system at time t. The normalized, or scaled, queue length

process is defined by Zj(i) = Qt{nt)/y/n- similarly, W,(t) = V't(ni)/v^ denotes the normalized

workload process. We approximate these normalized processes by the appropriate, and yet to

be defined, fimiting processes. Although Vi{t) is not directly observable by the scheduler at

time i, the normalized workload process is more convenient to employ than the normalised

queue length process in the approximating heavy traffic control problem. However, we use the

linear identity Zj = HiW^ to translate the solution of the approximating control problem into a

scheduling policy that is expressed in terms of the original queue length process (Qi, Q2)- This

linear identity is justified by extant heavy traffic limit theorems for many queueing systems.

In addition to speeding up time by a factor of n and reducing the queue lengths by a

factor of y/n, we also need to rescale the cost parameters C; and A'. The crux of problem

(1.1) is the tradeoff between setup costs and holding costs, and hence to obtain a nontrivial

solution to the approximating control problem, these two costs need to be of the same order

of magnitude. Since only the ratio of these two costs matters, without loss of generality we

leave the holding cost rates ci and C2 unsealed at 0(1), and only scale the setup cost K. The

following thought experiment allows us to conclude that the setup cost K needs to be divided

by n in the approximating control problem. The heavy traffic condition implies that there

are 0(^/n) customers in the original queueing system, and hence 0(1) scaled customers in the

heavy traffic system. The holding cost rate is eff'ectively multiplied by n because of the time

scaUng, so holding costs are incurred in the limiting control problem at the rate of 0{n^'^) per

unit time. Since 0{y/n) customers are in the system, the server switches class every 0{\/n)

unsealed time units, on average, implying that setup costs are incurred at the rate of 0{^)

per unit time in the heavy traffic time scale. Since holding costs are incurred at rate 0{n^''^)

and setup costs are incurred at rate 0{y/n), the setup cost K must be 0{n) for these cost rates

to be of the same order, and to get an 0(1) Hmiting setup cost, we must divide the setup cost

K by the heavy traffic scahng parameter n. Consequently, let k = K/n denote the normalized

setup cost. Thus, heavy traffic conditions for the setup cost problem imply that the traffic

intensity should be near one and the setup cost should be large. A canonical example is to set

n = 100 and set c, ci,C2 and k all equal to one, so that p = 0.9 and the setup cost A' = 100.

1.3 A Preliminary Heavy Traffic Result

The starting point for the setup cost problem is a recent heavy traffic result due to Coffman,

Puhalskii and Reiman (1993), which will be referred to hereafter as the CPR result. We present

an informal statement of a special case of this heavy traffic limit theorem that will suffice for

our purposes. As in problem (1.1), consider a queueing system with a single server and two

customer classes. The CPR result is derived under a specific queue discipline: the server serves

each class to exhaustion, and then switches class. The work conserving nature of the disciphne

implies that the total workload process W = Wi + W2 is identical to the corresponding process

under the FCFS policy. It follows from the heavy traffic umit theorem of Iglehart and Whitt

(1970) that this process is well approximated under heavy traffic conditions by RBM(â€” c, cr^),

which is a reflected Brownian motion (see Harrison 1985 for a definition) on [0,oc) with drift

â€” c and variance

It turns out to be impossible to obtain a limit process for (M^i, W2) in the usual sense, because

in the heavy traffic limit, the two-dimensional process moves back and forth along the cross

diagonal at an infinite rate, the direction being determined by which of the two queues is

being served; see Figure 1. The CPR result provides an averaging principle that implies the

following: given the normahzed total workload W , the two-dimensional workload (H^i,W^2)

can be treated as if it is uniformly distributed along the constant workload line from (0, W)

to (ly, 0). That is, the two-dimensional distribution is {UW, (1 â€” U)W), where U is a uniform

[0, 1] random variable that is independent of W .

This averaging principle is due to a time scale decomposition. On the time scale giving rise

to reflected Brownian motion for the total workload, the two-dimensional workload process

moves (asymptotically) infinitely quickly. If we slow time down so that the two-dimensional

workload moves at a flnite and positive rate, the total workload stays fixed, and the movement

of the two-dimensional workload is deterministic. Although this result has been proved only

under the exhaustive policy, we assume that it holds more generally. This has far-reaching

implications for the heavy traffic analysis of our control problem. In particular, it allows us to

collapse the state space of the control problem from three dimensions (the number of customers

of each class in the system and the location of the server) to one dimension (the total workload).

1.4 The Form of the Optimal Policy

The traditional heavy traffic approach to scheduling problems is to precisely formulate the

queueing system scheduling problem, find the limiting control problem that approximates the

scheduling problem \ni(lor heavy traffic conditions, and solve the latter problem. The approach

taken here is slightly different: we first argue that the optimal policy should be of a specific

form in the heavy traffic limit, and then optimize the approximating system over this class of

policies.

(H^,0)

(1 - U)W

serving queue 1

W = Wi + W-, : REM

W,

Figure 1: The heavy traffic averaging principle of Coffman, Puhalskii and Reiman (CPR).

Without loss of generahty, we assume that ci/xi > c^fJ-j and sometimes refer to classes 1 and

2 as the high and low priority classes, respectively. Existing results (Hofri and Ross for Poisson

arrivals and exponential service times, and Duenyas and Van Oyen for Poisson arrivals and

general service times) as well as intuition suggest that class 1 should be served to exhaustion.

(It is possible to construct examples where this pohcy is not optimal. Our contention is that

it is asymptotically optimal in heavy traffic.) When the server is set up for class 1, the only

other decision is to specify whether the server should idle or switch to class 2 when no class 1

customers are present. Since we work with the normalized workload process (1^1,^2), the only

reasonable form of the optimal policy is to switch when W^jit) > W2 for some scaled threshold

level ^2.

Since switching is instantaneous, Wi{t) = and W2{t) = .r at the moment of switching,

where x must be greater than or equal to the threshold W2- Because preemption is allowed,

the server should never idle at class 2 when class 2 customers are present. The CPR result

implies that the total workload W = Wi + W2 remains constant in the heavy traffic time scale

while the server is serving class 2 customers. Hence, our decision can be expressed as the

amount u(x) by which the server depletes class 2's original work. That is, class 2 is served

until Wi{t) = u(.r) and V^^IO = .r- u{x). The control u(x) must be between zero and x, where

u = X is the exhaustive policy. Figure 2 contains a picture with u{x) = .r/3 for a particular

value of X. Since a different amount u can be chosen for each value of the total workload x,

the control u{x) can generate any possible switching curve in the nonnegative orthant, and so

is without loss of generality.

Finally, since the server should never idle at station 2 when W2{t) > 0, if u{x) < x then

W^

Figure 2: The control u{x) = x/3 for a fixed value of x.

the server immediately switches back to class 1 when Wi{t) = u(x) and W2{t) = x - u(x).

However, if u(x) = x and hence class 2 is served exhaustively, then the server must decide

whether to idle or switch back to class 1. Once again, the obvious form of the optimal policy

in this case is to idle until Wi{t) is greater than or equal to wi. Notice that if the threshold

levels wi and ^2 were both zero, then infinite setup costs would be incurred.

In summary, the controls are the function u{x), which specifies the amount of class 2's work

to serve, and the threshold levels wi and W2, which dictate the server's busy/idle policy. The

form of the optimal policy in heavy traffic is: serve class 1 until Wi{t) = arid W2{t) > u'2,'

switch to class 2. If W2{t) = x at the moment of switching, then serve class 2 until Wi{t) =

u(x) and W2{t) = x â€” u{x). If u{x) < x, then switch to class 1; if u{x) = x, then do not switch

until Wi{t) > vui.

1.5 An Overview of the Analysis

The analysis hinges on the following crucial observation: since setups are instantaneous,

the total workload process is only affected by the server's busy/idle policy, not by how often

the server switches class. Hence, the control u{x) only influences the total workload indirectly

via the idling. However, u{x) does affect the rate at which holding costs and setup costs are

incurred when the total workload is x. Therefore, a two-step procedure is employed to find the

optimal policy {u{x),wi,W2) within the specified form. In the first step, the control u{x) is

chosen to minimize the cost rate for each state .r; this minimization is performed independently

for each state x. In the second step, we attempt to find the optimal threshold levels u)\ and

U'2, and L.Mice the optimal total workload process. Our heavy traffic analysis will show that

the optimal total workload process is a RBM(â€” c, o"'^) on [u;,oo), where w is a parameter that

is chosen to minimize the total expected cost. Hence, the Brownian model is too crude to

distinguish between the two thresholds wi and W2, and so we set both Â«'i and Â»'2 equal to the

derived value of (/'.

As in previous heavy traffic scheduling work (see Harrison 1988 and Wein 19y0a, for ex-

ample), the analysis naturally decomposes onto two time scales. On the very fast time scale,

where individual ([ueues can change instantaneously fast, we myopically optimize over ii{x).

Tiicn. on the slower time scale over which the total workload varies, a singular control problem

is solved to find the threshold, or reflecting barrier, w that specifies the busy/idle policy.

1.6 The Optimal u{x)

The control u{x) is chosen to minimize the cost rate that is incurred when the normalized

total workload process is x. Under the policy characterized by u(x), class 2's work is depleted

by the amount u{x) if the total workload when the server arrives to class 2 is x. The CPR

result implies that, for our purposes, it is as if Wi is uniformly distributed between and u{x),

and W2 is uniformly distributed between x - u(i) and x. Since Zj â€” ^jV^j, the holding cost

rate when in state x is

V" rrn/i "(^) , f2x-u{x)

2^ C^|I^E\VV^\ = Cl/Xlâ€” h C2M2 I '

Au(x) , ,

= C2M2-r + â€” - â€” , (1-3)

where

A = ci/xi -C2/X2 â– (1-4)

To find the setup cost rate when in state ;c, we need to find the cycle length. For a fixed

total unfinished workload .r, the two-dimensional workload process (^1^1,^2) moves back and

forth deterministically at an asymptotically infinite rate along the line segment from (0, x) to

((/(.r),x - u(x)); hence, the cycle length is deterministic.

We determine the deterministic cycle length, and hence the setup cost rate, as a function

of the normalized workload by slowing down the time scale. If the server finds x units of work

in class 2 upon arrival, then this work will be depleted at rate \ â€” p^- The server works until

'W\[t) = u{x) and W2{t) = x - u(x), which occurs after u(x)/(l - P2) time units. As we will

see later, the normalized total workload process W never spends any time below max(it;i, Â«;2),

and so we need not include any unnecessary inserted idle time into the cycle length calculation.

Therefore, it takes u(x)/{l - p\ ) time units to deplete class 1 and complete the cycle, resulting

in a cycle of length u(.r)/(l - P2) + u(x)/(l â€” p\). Since the holding costs are estimated using

a heavy traffic approximation and the scheduling problem essentially trades off the setup and

holding costs, a more accurate analysis results if we assume that p = 1 in our cycle length

expression, which simplifies the cycle length to u{x)/pip2. Because two setups are incurred in

each cycle, the setup cost rate when in state x is pip2K/u{x).

Now we find the optimal u{x) by solving;

mm C2P2-r + â€” - â€” + , , . (1-5)

u(x)e[o,x] 2 u(x)

If we define

2piP2K,

then straightforward calculus leads to

t/'(.r) = min(x, u;) . (!â€¢")

Hence, w is the largest value of the total workload for which class 2 is served exhaustively.

Notice that w = 00 when A = 0, and so the optimal control in the balanced case is u*(.r) = .c

for all .r, which corresponds to exhaustive service for class 2.

.M414

/V3.

t-o

Dewey

WORKING PAPER

ALFRED P. SLOAN SCHOOL OF MANAGEMENT

Dynamic Scheduling of a Two-Class Queue

with Setups

Martin L Reiman

Lawrence M. Wein

#3692-94-MSA

May 1994

MASSACHUSETTS

INSTITUTE OF TECHNOLOGY

50 MEMORIAL DRIVE

CAMBRIDGE, MASSACHUSETTS 02139

Dynamic Scheduling of a Two-Class Queue

with Setups

Martin I. Reiman

Lawrence M. Wein

#3692-94-MSA May 1994

M.I.T. LIBRARiES

:' JUN 2 1994

RECEIVED

Dynamic Scheduling of a Two-Class Queue with Setups

Martin I. Reiman

AT&T Bell Laboratories

Murray Hill, NJ 07974

Lawrence M. Wem

Sloan School of Management, M.I.T.

Cambridge, MA 02139

ABSTRACT

We analyze two scheduling problems for a queueing system with a single server and two cus-

tomer classes. Each class has its own renewal arrival process, general service time distribution

and holding cost rate. In the first problem, a setup cos* is incurred when the server switches

from one class to the other, and the objective is to minimize the long run expected average

cost of holding customers and incurring setups. The setup cost is replaced by a setup time in

the second problem, where the objective is to minimize the average holding cost. By assuming

that the queueing system operates under standard heavy traffic conditions, we approximate the

dynamic scheduling problems by diffusion control problems. For both problems, considerable

insight is gained into the nature of the optimal policy, and the computational results show

that the proposed scheduling policy is within several percent of optimal over a broad range of

problem parameters.

APRIL 1994

We consider two dynamic scheduling problems for a single server queueing system with two

classes of customers. In both problems, each class possesses its own renewal arrival process,

general service time distribution and holding cost rate, and the server incurs a setup when

switching from one class to the other. In the setup cost problem, a setup cost is incurred and

the objective is to minimize the long run expected average setup and holding cost. In the

setup time problem, a random setup time is incurred when the server switches class, and the

objective is to minimize the long run expected average holding cost. In both problems, the

server has three options at each point in time: serve a customer from the class that is currently

set up, switch to the other class (and immediately begin service in the setup cost problem), or

sit idle.

These scheduling problems have numerous applications, most notably for manufacturing

systems and polling systems in computer communication networks. The setup time problem

is more realistic than the setup cost problem in most situations, but is also n^rre difficult to

analyze. However, the setup cost problem is relevant for some manufacturing systems because,

motivated by just-in-time (JIT) manufacturing, many facilities have internalized their setup

times; that is, they have essentially ehminated their setup times at the expense of incurring

significant material, labor and/or capital costs.

Although many studies have analyzed the performance of polling systems under various

scheduling policies (see Takagi 1986, Boxma and Takagi 1992 and references therein), relatively

few papers have considered the optimal scheduling of polling systems. The seminal paper in

this research area is Hofri and Ross (1987), who analyze a two-class system with setup costs

and times. Let c, and //, denote the holding cost rate and service rate, respectively, for class

i customers. When ci^i = C2H2, they show that a double threshold policy, where the server

serves each class until its queue is exhausted and the length of the other queue achieves a

certain threshold level, minimizes the cost of setups and holding customers, under both the

discounted and average cost criteria. Very little is known about the polling problem when

ciMi Â¥" f2M2, aside from the fact that the class with the larger cfi index should be served to

exhaustion.

Several authors have studied the setup time problem in which more than two classes are

present. Structural results for symmetric systems are derived by Liu, Nain and Towsley (1991)

and references therein. Browne and Yechiali (1989) derive quasi-dynamic index policies, which

allow the server to choose the sequence of classes to visit at the beginning of each cycle, that

minimize or maximize the mean cycle length. Boxma, Levy and Westrate (1991) derive an

efficient polling table (a predetermined fixed visit sequence) for minimizing the mean waiting

cost. Bertsimas and Xu (1993) derive lower bounds and construct static policies that perform

close to the bound when all classes have identical c/i indices. Van Oyen and Duenyas (1992)

develop a dynamic scheduling heuristic based on myopic reward rates; Duenyas and Van Oyen

(1993) also construct a dynamic policy for the setup cost problem.

Since the two-class asymmetric problem appears to be analytically intractable, heavy traffic

approximations are employed in an attempt to make further headway. T'lat is, we make the

heavy traffic assumption that the server must be busy the great majority of the time to satisfy

demand. In the setup cost problem, we also need to assume that the setup costs are very large,

roughly two orders of magnitude larger than the holding cost rate. Following in the tradition

of Foschini (1977) and Harrison (1988), we study the diffusion control problem that arises as

a heavy traffic Hmit of a sequence of queueing scheduling problems. These limiting control

problems tend to be more tractable than their queueing counterparts and have led to network

scheduling policies (see, for example, Harrison and Wein 1990 and Wein 1990b) that have a

surprisingly simple form and appear to perform well.

1

Using the heavy traffic averaging principle derived in Coffman, Puhalskii and Reiman

(1993), we show in Section 1 that the setup cost problem simplifies rather dramatically in the

limiting heavy traffic regime: the dimension of the state space collapses from three (queue

length of each clciss and the position of the server) to one (total workload). This result also

allows our analysis to naturally decompose onto two different time scales. On the very fast

time scale over which individual queue lengths change, we myopically optimize a control that

specifies the amount of low priority work to serve as a function of the total workload. This state-

dependent control is derived in closed form and offers considerable insight. On the slower time

scale over which the total workload varies, a singular control problem is solved that specifies a

busy/idle pohcy. The solution to this control problem leads to a rather complex equation for

one variable, which represents a threshold level, that can easily be solved numerically.

The setup time problem is addressed in Section 2, and the averaging principle in Coffman,

Puhalskii and Reiman (1994) leads to a limiting control problem that again is one-dimensional,

although here we obtain an explicit diffusion control problem. The control, which represents

the amount of low priority work to serve as a function of the total workload, appears in the drift

term of the diffusion process in a nonlinear fashion, and consequently the optimahty equation

leads to a nonlinear ordinary differential equation (ODE) that cannot be solved explicitly.

However, we use asymptotics to obtain a scheduling policy; the asymptotics also reveal a

substantial qualitative difference between the optimal policies in the setup cost and setup time

cases.

For both problems, we use the value iteration algorithm to obtain "exact" optimal policies

for a variety of test cases, and show in Section 3 that the suboptimality of the proposed policies

is within several percent of optimal over a broad range of problem parameters.

Our presentation of the analysis, and indeed the analysis itself, is rather informal through-

out. For example, we do not prove that the limiting control problems are the heavy traffic

limit of a sequence of queueing scheduling problems. Also, several of our claims regarding the

nature of the limiting control problems and their optimal solutions are not proved. Providing

a rigorous presentation of our results would be extremely demanding, and would take us far

afield from our two main objectives: to obtain fundamental insights into the nature of the

optimal policies and to develop effective scheduling policies for these systems. However, much

of our analysis relies upon observations that have been rigorously proven for simpler systems,

and we have no doubt that our results are essentially correct. We hope that this approach

increases the accessility of the paper without sacrificing the persuasiveness of our arguments.

1 THE SETUP COST PROBLEM

1.1 Problem Description

Customers of class i = 1,2 arrive according to independent renewal processes, where A, and

c^j denote respectively the arrival rate and squared coefficient of variation (variance divided

by the square of the mean) of the interarrival times. Each class has its own general service

time distribution with service rate /Xj and squared coefficient of variation c^j, and we define the

system's traffic intensity by p = Yn=i{^i/f^i)- A cost c, is incurred per unit time for holding

a class i customer in the system. A setup cost K/2 is imposed whenever the server switches

from one class to the other, so that A' is the setup cost per cycle.

The server hcis three scheduling options at each point in time: serve the class that is

currently set up, switch to the other class and initiate service, or sit idle. Since a switchover

is instantaneous and costly, the option of switching to the other class and idling need not be

considered. We assume that the server works in a preemptive-resume fashion, although the

heavy traffic analysis is too crude to capture the effects of the nonpreemptive discipline as an

alternative assumption. Let Qi{t) be the number of class i customers in queue or in service at

time t, and let J{t) denote the number of times the server sets up in the time interval \0,t\.

Then our objective is to find a nonanticipating (with respect to the queue length process)

scheduling policy to minimize

limsup â€”;E

r-.oo T

rY,c,Q,{t)dt+^^J{T)

Jo ~1 ^

(1.1)

1.2 The Heavy Traffic Normalizations

A precise formulation of the approximating diffusion control problem requires much nota-

tion that would not be subsequently used. In addition, the limiting control problem will not

be explicitly solved; rather, we optimize over a specific form of policy that is introduced in

Subsection 1.4. Hence the heavy traffic control problem will not be precisely formulated, and

a description of the heavy traffic conditions and normalizations will suffice for our purposes.

The approximating control problem is the limit of a sequence of scheduling problems in-

dexed by the heavy traffic scaling parameter n, where n â€”>â– oo. Since a heavy traffic limit

theorem will not be proved here, we avoid unnecessary notation by considering a single large

integer n satisfying y/n{l â€” p) = c, where c is positive and of moderate size (that is, 0(1)); this

standard heavy traffic condition requires the server to be busy the great majority of the time

over the long run. As we will see later, the scheduling policy that arises out of our heavy traffic

analysis is independent of the system parameter n. Let V, be the unfinished workload process

for class i; Vi{t) is the amount of time a continuously busy server requires to clear all of the class

i customers who are present in the system at time t. The normalized, or scaled, queue length

process is defined by Zj(i) = Qt{nt)/y/n- similarly, W,(t) = V't(ni)/v^ denotes the normalized

workload process. We approximate these normalized processes by the appropriate, and yet to

be defined, fimiting processes. Although Vi{t) is not directly observable by the scheduler at

time i, the normalized workload process is more convenient to employ than the normalised

queue length process in the approximating heavy traffic control problem. However, we use the

linear identity Zj = HiW^ to translate the solution of the approximating control problem into a

scheduling policy that is expressed in terms of the original queue length process (Qi, Q2)- This

linear identity is justified by extant heavy traffic limit theorems for many queueing systems.

In addition to speeding up time by a factor of n and reducing the queue lengths by a

factor of y/n, we also need to rescale the cost parameters C; and A'. The crux of problem

(1.1) is the tradeoff between setup costs and holding costs, and hence to obtain a nontrivial

solution to the approximating control problem, these two costs need to be of the same order

of magnitude. Since only the ratio of these two costs matters, without loss of generality we

leave the holding cost rates ci and C2 unsealed at 0(1), and only scale the setup cost K. The

following thought experiment allows us to conclude that the setup cost K needs to be divided

by n in the approximating control problem. The heavy traffic condition implies that there

are 0(^/n) customers in the original queueing system, and hence 0(1) scaled customers in the

heavy traffic system. The holding cost rate is eff'ectively multiplied by n because of the time

scaUng, so holding costs are incurred in the limiting control problem at the rate of 0{n^'^) per

unit time. Since 0{y/n) customers are in the system, the server switches class every 0{\/n)

unsealed time units, on average, implying that setup costs are incurred at the rate of 0{^)

per unit time in the heavy traffic time scale. Since holding costs are incurred at rate 0{n^''^)

and setup costs are incurred at rate 0{y/n), the setup cost K must be 0{n) for these cost rates

to be of the same order, and to get an 0(1) Hmiting setup cost, we must divide the setup cost

K by the heavy traffic scahng parameter n. Consequently, let k = K/n denote the normalized

setup cost. Thus, heavy traffic conditions for the setup cost problem imply that the traffic

intensity should be near one and the setup cost should be large. A canonical example is to set

n = 100 and set c, ci,C2 and k all equal to one, so that p = 0.9 and the setup cost A' = 100.

1.3 A Preliminary Heavy Traffic Result

The starting point for the setup cost problem is a recent heavy traffic result due to Coffman,

Puhalskii and Reiman (1993), which will be referred to hereafter as the CPR result. We present

an informal statement of a special case of this heavy traffic limit theorem that will suffice for

our purposes. As in problem (1.1), consider a queueing system with a single server and two

customer classes. The CPR result is derived under a specific queue discipline: the server serves

each class to exhaustion, and then switches class. The work conserving nature of the disciphne

implies that the total workload process W = Wi + W2 is identical to the corresponding process

under the FCFS policy. It follows from the heavy traffic umit theorem of Iglehart and Whitt

(1970) that this process is well approximated under heavy traffic conditions by RBM(â€” c, cr^),

which is a reflected Brownian motion (see Harrison 1985 for a definition) on [0,oc) with drift

â€” c and variance

It turns out to be impossible to obtain a limit process for (M^i, W2) in the usual sense, because

in the heavy traffic limit, the two-dimensional process moves back and forth along the cross

diagonal at an infinite rate, the direction being determined by which of the two queues is

being served; see Figure 1. The CPR result provides an averaging principle that implies the

following: given the normahzed total workload W , the two-dimensional workload (H^i,W^2)

can be treated as if it is uniformly distributed along the constant workload line from (0, W)

to (ly, 0). That is, the two-dimensional distribution is {UW, (1 â€” U)W), where U is a uniform

[0, 1] random variable that is independent of W .

This averaging principle is due to a time scale decomposition. On the time scale giving rise

to reflected Brownian motion for the total workload, the two-dimensional workload process

moves (asymptotically) infinitely quickly. If we slow time down so that the two-dimensional

workload moves at a flnite and positive rate, the total workload stays fixed, and the movement

of the two-dimensional workload is deterministic. Although this result has been proved only

under the exhaustive policy, we assume that it holds more generally. This has far-reaching

implications for the heavy traffic analysis of our control problem. In particular, it allows us to

collapse the state space of the control problem from three dimensions (the number of customers

of each class in the system and the location of the server) to one dimension (the total workload).

1.4 The Form of the Optimal Policy

The traditional heavy traffic approach to scheduling problems is to precisely formulate the

queueing system scheduling problem, find the limiting control problem that approximates the

scheduling problem \ni(lor heavy traffic conditions, and solve the latter problem. The approach

taken here is slightly different: we first argue that the optimal policy should be of a specific

form in the heavy traffic limit, and then optimize the approximating system over this class of

policies.

(H^,0)

(1 - U)W

serving queue 1

W = Wi + W-, : REM

W,

Figure 1: The heavy traffic averaging principle of Coffman, Puhalskii and Reiman (CPR).

Without loss of generahty, we assume that ci/xi > c^fJ-j and sometimes refer to classes 1 and

2 as the high and low priority classes, respectively. Existing results (Hofri and Ross for Poisson

arrivals and exponential service times, and Duenyas and Van Oyen for Poisson arrivals and

general service times) as well as intuition suggest that class 1 should be served to exhaustion.

(It is possible to construct examples where this pohcy is not optimal. Our contention is that

it is asymptotically optimal in heavy traffic.) When the server is set up for class 1, the only

other decision is to specify whether the server should idle or switch to class 2 when no class 1

customers are present. Since we work with the normalized workload process (1^1,^2), the only

reasonable form of the optimal policy is to switch when W^jit) > W2 for some scaled threshold

level ^2.

Since switching is instantaneous, Wi{t) = and W2{t) = .r at the moment of switching,

where x must be greater than or equal to the threshold W2- Because preemption is allowed,

the server should never idle at class 2 when class 2 customers are present. The CPR result

implies that the total workload W = Wi + W2 remains constant in the heavy traffic time scale

while the server is serving class 2 customers. Hence, our decision can be expressed as the

amount u(x) by which the server depletes class 2's original work. That is, class 2 is served

until Wi{t) = u(.r) and V^^IO = .r- u{x). The control u(x) must be between zero and x, where

u = X is the exhaustive policy. Figure 2 contains a picture with u{x) = .r/3 for a particular

value of X. Since a different amount u can be chosen for each value of the total workload x,

the control u{x) can generate any possible switching curve in the nonnegative orthant, and so

is without loss of generality.

Finally, since the server should never idle at station 2 when W2{t) > 0, if u{x) < x then

W^

Figure 2: The control u{x) = x/3 for a fixed value of x.

the server immediately switches back to class 1 when Wi{t) = u(x) and W2{t) = x - u(x).

However, if u(x) = x and hence class 2 is served exhaustively, then the server must decide

whether to idle or switch back to class 1. Once again, the obvious form of the optimal policy

in this case is to idle until Wi{t) is greater than or equal to wi. Notice that if the threshold

levels wi and ^2 were both zero, then infinite setup costs would be incurred.

In summary, the controls are the function u{x), which specifies the amount of class 2's work

to serve, and the threshold levels wi and W2, which dictate the server's busy/idle policy. The

form of the optimal policy in heavy traffic is: serve class 1 until Wi{t) = arid W2{t) > u'2,'

switch to class 2. If W2{t) = x at the moment of switching, then serve class 2 until Wi{t) =

u(x) and W2{t) = x â€” u{x). If u{x) < x, then switch to class 1; if u{x) = x, then do not switch

until Wi{t) > vui.

1.5 An Overview of the Analysis

The analysis hinges on the following crucial observation: since setups are instantaneous,

the total workload process is only affected by the server's busy/idle policy, not by how often

the server switches class. Hence, the control u{x) only influences the total workload indirectly

via the idling. However, u{x) does affect the rate at which holding costs and setup costs are

incurred when the total workload is x. Therefore, a two-step procedure is employed to find the

optimal policy {u{x),wi,W2) within the specified form. In the first step, the control u{x) is

chosen to minimize the cost rate for each state .r; this minimization is performed independently

for each state x. In the second step, we attempt to find the optimal threshold levels u)\ and

U'2, and L.Mice the optimal total workload process. Our heavy traffic analysis will show that

the optimal total workload process is a RBM(â€” c, o"'^) on [u;,oo), where w is a parameter that

is chosen to minimize the total expected cost. Hence, the Brownian model is too crude to

distinguish between the two thresholds wi and W2, and so we set both Â«'i and Â»'2 equal to the

derived value of (/'.

As in previous heavy traffic scheduling work (see Harrison 1988 and Wein 19y0a, for ex-

ample), the analysis naturally decomposes onto two time scales. On the very fast time scale,

where individual ([ueues can change instantaneously fast, we myopically optimize over ii{x).

Tiicn. on the slower time scale over which the total workload varies, a singular control problem

is solved to find the threshold, or reflecting barrier, w that specifies the busy/idle policy.

1.6 The Optimal u{x)

The control u{x) is chosen to minimize the cost rate that is incurred when the normalized

total workload process is x. Under the policy characterized by u(x), class 2's work is depleted

by the amount u{x) if the total workload when the server arrives to class 2 is x. The CPR

result implies that, for our purposes, it is as if Wi is uniformly distributed between and u{x),

and W2 is uniformly distributed between x - u(i) and x. Since Zj â€” ^jV^j, the holding cost

rate when in state x is

V" rrn/i "(^) , f2x-u{x)

2^ C^|I^E\VV^\ = Cl/Xlâ€” h C2M2 I '

Au(x) , ,

= C2M2-r + â€” - â€” , (1-3)

where

A = ci/xi -C2/X2 â– (1-4)

To find the setup cost rate when in state ;c, we need to find the cycle length. For a fixed

total unfinished workload .r, the two-dimensional workload process (^1^1,^2) moves back and

forth deterministically at an asymptotically infinite rate along the line segment from (0, x) to

((/(.r),x - u(x)); hence, the cycle length is deterministic.

We determine the deterministic cycle length, and hence the setup cost rate, as a function

of the normalized workload by slowing down the time scale. If the server finds x units of work

in class 2 upon arrival, then this work will be depleted at rate \ â€” p^- The server works until

'W\[t) = u{x) and W2{t) = x - u(x), which occurs after u(x)/(l - P2) time units. As we will

see later, the normalized total workload process W never spends any time below max(it;i, Â«;2),

and so we need not include any unnecessary inserted idle time into the cycle length calculation.

Therefore, it takes u(x)/{l - p\ ) time units to deplete class 1 and complete the cycle, resulting

in a cycle of length u(.r)/(l - P2) + u(x)/(l â€” p\). Since the holding costs are estimated using

a heavy traffic approximation and the scheduling problem essentially trades off the setup and

holding costs, a more accurate analysis results if we assume that p = 1 in our cycle length

expression, which simplifies the cycle length to u{x)/pip2. Because two setups are incurred in

each cycle, the setup cost rate when in state x is pip2K/u{x).

Now we find the optimal u{x) by solving;

mm C2P2-r + â€” - â€” + , , . (1-5)

u(x)e[o,x] 2 u(x)

If we define

2piP2K,

then straightforward calculus leads to

t/'(.r) = min(x, u;) . (!â€¢")

Hence, w is the largest value of the total workload for which class 2 is served exhaustively.

Notice that w = 00 when A = 0, and so the optimal control in the balanced case is u*(.r) = .c

for all .r, which corresponds to exhaustive service for class 2.

Online Library → M. I Reiman → Dynamic scheduling of a two-class queue with setups → online text (page 1 of 4)