Copyright
M. I Reiman.

Dynamic scheduling of a two-class queue with setups online

. (page 1 of 4)
Online LibraryM. I ReimanDynamic scheduling of a two-class queue with setups → online text (page 1 of 4)
Font size
QR-code for this ebook


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.


1 3 4

Online LibraryM. I ReimanDynamic scheduling of a two-class queue with setups → online text (page 1 of 4)