Lawrence M Wein.

Dynamic scheduling of a multiclass make-to-stock queue online

. (page 1 of 3)
Online LibraryLawrence M WeinDynamic scheduling of a multiclass make-to-stock queue → online text (page 1 of 3)
Font size
QR-code for this ebook


^



*



Of



-

'■






O /



&



&




WORKING PAPER
ALFRED P. SLOAN SCHOOL OF MANAGEMENT



DYNAMIC SCHEDULING OF A MULTICLASS
MAKE-TO-STOCK QUEUE

Lawrence M. Wein

Sloan School of Managment, MIT

Working Paper No. 31 13-90-MSA



MASSACHUSETTS

INSTITUTE OF TECHNOLOGY

50 MEMORIAL DRIVE

CAMBRIDGE, MASSACHUSETTS 02139



DYNAMIC SCHEDULING OF A MULTICLASS
MAKE-TO-STOCK QUEUE

Lawrence M. Wein

Sloan School of Managment, MTT

Working Paper No. 31 13-90-MSA



Wi.l.T. UBRAh,.
MAR 1 5 1990






DYNAMIC SCHEDULING OF A MULTICLASS MAKE-TO-STOCK QUEUE

Lawrence M. Wein

Sloan School of Management, M.I.T.

Abstract



Motivated by make-to-stock production systems, we consider a scheduling problem
for a single-server queue that can process a variety of different job classes. After jobs
are processed, they enter a finished goods inventory that services customer demand. The
scheduling problem is to release jobs to the queue and decide which job class, if any, to
serve next in order to minimize the long run expected average cost incurred per unit of
time, which includes linear costs (which may differ by class) for backordering finished
goods inventory, holding finished goods inventory, and holding WIP inventory. Under the
heavy traffic condition that the server must be busy the great majority of the time in
order to satisfy customer demand, the scheduling problem is approximated by a dynamic
control problem involving Brownian motion. The Brownian control problem is solved, and
its solution is interpreted in terms of the queueing system in order to obtain an effective
scheduling policy. The proposed scheduling policy releases jobs to the queue only when
they are about to begin processing, and keeps the server busy as long as the weighted
sum of the finished goods inventory (where the inventory of each class is weighted by its
expected processing time) is not too large. When the server is working, priority is given to
backlogged classes that are expensive to backlog and have short expected processing times,
and when there are no backlogged jobs, priority is given to jobs that are inexpensive to
hold in finished goods inventory and have long expected processing times.



January 1990



DYNAMIC SCHEDULING OF A MULTICLASS MAKE-TO-STOCK QUEUE

Lawrence M. Wein

Sloan School of Management, M.I.T.



Production facilities are often categorized as make- to-order systems or make-to-stock
systems. In make-to-order systems, the facility produces according to customer requests,
and no finished goods inventory is kept. In make-to-stock systems, the facility produces
according to a forecast of customer demand, and completed jobs enter a finished goods in-
ventory, which in turn services actual customer demand. Due to increased global manufac-
turing competition, the customer response time (the length of time between the placement
of a customer's order and the delivery of the order) required to stay in business is being
reduced, and is sometimes smaller than a firm's manufacturing cycle time (the length of
time between a job's start of production and its completion). In such cases, the facility is
forced to operate (at least partially) as a make-to-stock production system.

The goal of this paper is to investigate the scheduling problem faced by a single
machine, make-to-stock production facility in a dynamic stochastic environment. This
facility is pictured in Figure 1, where it is assumed that there is an ample amount of raw
material inventory of product k, for k = l,...,iv. The scheduler decides when to release a
raw product k job onto the shop floor, at which time the job becomes a unit of product k
work-in-process ( WIP) inventory. These decisions will be referred to as release decisions.
There is a single machine that transforms units of product k WIP inventory into units of
product k finished goods inventory. The machine is modeled as a multiclass queue, in that
the machine may work on only one unit at a time, and each product has its own general
processing time distribution. Demand for each product can be any arbitrary point process
that satisfies a functional central limit theorem (for example, a compound Poisson process).
If the machine produces A' products, the dynamic sequencing decisions consist of choosing



among K + 1 options at each point in time: either work on a type k product, k = 1, ..., K,
or allow the machine to sit idle. Preemptive resume scheduling is allowed, but as will be
seen later, our method of analysis is crude enough that our resulting scheduling policy is
independent of the particular assumptions made with regard to preemption. There are
no set-up times incurred when switching production from one type of product to another.
There are linear costs incurred per unit of time for backordering finished goods inventory,
holding finished goods inventory, and holding WIP inventory, and these costs may differ
by product. The scheduling problem is to find a release policy and a sequencing policy to
minimize the long run expected average backorder and holding (both WIP and finished
goods) cost incurred per unit of time.



Product 1



Product K




A— A

Raw W)p

hUSintifrl? Inventory

Inventory ;




Machine



A

A



-•ii-



-.11-



Finished

Goods

Inventory



Product 1
Demand



Product K
Demand



Figure 1. The Production Facility.



In order to analyze this scheduling problem, we have employed a Brownian model
developed by Harrison (1988) that approximates, under so-called heavy traffic conditions,
a dynamic scheduling problem for a multiclass queueing network by a dynamic control
problem involving Brownian motion. The heavy traffic conditions assume that the server
must be busy the great majority of the time (for example, 90% of the time) in order to
satisfy customer demand over the long run. By solving a reformulation of the Brownian
control problem and interpreting the solution in terms of the original queueing system, a

2



variety of seemingly intractable scheduling problems have been analyzed; see, for exam-
ple, Harrison and Wein (1989), Wein (1989a,1989b), and Laws and Louth (1988). In this
paper, we alter Harrison's model to accommodate a finished goods inventory that services
customer demand, and approximate a multiclass make-to-order queueing system schedul-
ing problem by a dynamic control problem involving Brownian motion. A closed form
solution to the workload formulation of the control problem is obtained, and this solution
is interpreted in terms of the original production/inventory system in order to obtain an
effective scheduling policy.

Not surprisingly, the proposed release policy releases a raw unit of product k to the
shop only when the scheduler decides to process a type k unit, and thus no WIP inventory
is held. Although the release decisions appear to be superfluous in our model, the main
reason they are included is to maintain consistency with Harrison's original model, which
considers a general queueing network with controllable inputs and dynamic scheduling
capability. By appending the customer demand process and finished goods inventory to
Harrison's model, one can formulate a control problem (job release and priority sequencing)
for a very general make-to-stock queueing network.

The proposed sequencing policy dynamically tracks the weighted inventory process,
which is the weighted (by the mean processing times) sum of the finished goods inventory
levels (which can be positive or negative) of each product. Whenever the weighted inven-
tory process is below a certain critical value, then the machine stays busy; otherwise, it is
idle. When the machine is busy, it employs a dynamic sequencing policy that is somewhat
reminiscent of the so-called c\i rule that minimizes the weighted average cycle time in a
conventional multiclass queue. In the c/x rule, c k is the holding cost for class k jobs in
queue and //* is the service rate, and the rule gives priority to larger values of the index
Ckfik- In our setting, let the backorder cost for type k products be 6*, the finished goods
inventory holding cost be denoted by h k , and the service rate be /x*- Among the job classes
that are currently backordered, our sequencing policy awards priority to the class with the

3



largest value of the index 6*^*- If no job classes are backlogged, then priority is given to
the class with the smallest value of the index h^Hk- A simulation experiment is performed
with two numerical examples, and the proposed policy is compared to the conventional
scheduling policy of releasing jobs as above, keeping the machine busy whenever the total
(unweighted) inventory process is below a critical value, and dynamically awarding priority
to the class with the smallest finished goods inventory level. The proposed policy reduces
the total cost by 14.9% and 23.2% relative to the conventional policy in the two numerical
examples.

An important implication of the balanced heavy loading conditions assumed in Harri-
son's Brownian network model is that, in the heavy traffic limit represented by the Brow-
nian model, any stations in the original queueing network that are not among the most
heavily loaded will simply vanish. This has been proven for some single-type queueing net-
works (see Johnson 1983 and Chen and Mandelbaum 1989), and justifies the procedure of
eliminating all non-bottleneck stations when performing the Brownian analysis. Therefore,
our scheduling policy applies to any make-to-stock production system with one bottleneck
workstation that does not allow jobs to visit this station more than once.

The remainder of this paper is organized as follows. The relevant literature is reviewed
in Section 1, the queueing system scheduling problem is defined in Section 2, and the
corresponding Brownian control problem is given in Section 3. The problem is reformulated
in terms of workloads in Section 4, and the workload formulation is solved in Sections
5 through 9. The solution is interpreted in Section 10, and a simulation experiment
is performed in Section 11 to demonstrate its effectiveness. Section 12 contains some
concluding remarks.

This section concludes with the probabilistic formalisms that will be adopted in this
paper. When we say that X is a A'— dimensional (/i,E) Brownian motion (readers are
referred to Karatxas and Shreve 1988 for a definition), it is assumed there is a given
(J), F, F t , X, P z ), where (ft, F) is a measurable space, X = X(lj) is a measurable mapping

4



of 0, into C(R K ), which is the space of continuous functions on R K , F t = a(X(s),s < t)
is the filtration generated by X, and P z is a family of probability measures on Q such
that the process {X(t),t > 0} is a Brownian motion with drift fi, covariance matrix E,
and initial state x under P z . Let E x be the expectation operator associated with P z . If
Y = {Y(t),t > 0} is a process that is F t -measurable for all t > 0, then we say that the
process Y is non-anticipating with respect to the Brownian motion X . More generally, we
will say that one process Y is non-anticipating with respect to another process X when Y
is adapted to the coarsest filtration with respect to which X is adapted.

1. Relevant Literature

The problem posed in this paper is to dynamically schedule a multiclass make-to-stock
queue, which represents a multi-product, single machine, production /inventory system.
Notice that the conventional multiclass queue (where jobs arrive randomly and then exit the
system after service is completed) corresponds to a multi-product, single machine, make-
to-order facility. Although the problem of minimizing the number of jobs in a conventional
multiclass queue has been thoroughly examined (see, for example, Klimov 1974), there are
no studies that explicitly analyze the multiclass make-to-stock queue. However, there have
been several studies analyzing single-machine production/inventory systems with random
demand. Gavish and Graves (1977) and Graves and Keilson (1981) consider the single-
product case with deterministic processing times and set-up costs. Here the scheduling
problem is to decide when to start and stop the machine. Graves (1980) attempts to
generalize these results to the multi-product case by considering a periodic review policy
and introducing the notion of a composite product. Bemelmans and Wijngaard (1982)
also aggregate the products in a single-machine, multi-product problem, although their
production model is different than a standard queueing model, in that the machine is
allowed to work on several products simultaneously.

The paper that is most closely related to ours is probably Zheng and Zipkin (1990),

5



who analyze a production/inventory system that produces two distinct products. The
production system is modelled as a single server queue with exponential processing times,
the customer demand for each product is a Poisson process, and an (S — 1,5) policy is
used to trigger orders for each product to the production system. They analyze this system
under two different sequencing policies: FCFS, and serve the product that has the lower
inventory level. Their queueing theoretic analysis reveals that the latter policy outperforms
FCFS.

There is also a substantial literature on dynamic lot-sizing problems, but these mod-
els (except for the presence of set-up times) are more restrictive than a standard queueing
model. Readers are referred to the survey paper of Graves (1981) for more on these prob-
lems. He reviews scheduling problems for both make-to-order and make-to-stock systems,
and refers to these systems as open shops and closed shops, respectively.

Our consideration of queueing and inventory aspects in a single model is not new. In
fact, the analysis and design of such systems have been the subject of much recent work;
see, for example, Williams (1984), Bertrand (1985), Zipkin (1986), Karmarkar (1987),
Cohen and Lee (1988), Altiok (1989), and Mitra and Mitrani (1988). In particular, it was
the paper by Zipkin (1986) that partially stimulated this analysis. Finally, the heavy traffic
theory for queueing systems underlying this Brownian model offers a partial justification
for the direct modeling of an inventory storage system by a diffusion process, both in past
(see, for example, Bather 1966, Puterman 1975, and Browne and Zipkin 1989) and future
research efforts.

2. The Scheduling Problem

Consider a single server that can serve K different classes of jobs. We refer to the
entities populating the queueing system as jobs rather than customers, so as not to confuse
them with the actual customer demand. In terms of the production/inventory system, the
server is the machine, each job class corresponds to a type of product, and each job is a



unit of a particular product. Class k jobs have a general service time distribution with
finite mean m* and variance s\, for k = 1,...,K. The service times (or processing times)
for class k are equivalently characterized by the renewal process S* (r), which is the number
of class k service completions up to time i if the server were continuously serving class k
jobs in the interval [0,i]. Adopting conventional terminology, we will refer to //* = m^ 1
as the service rate of class k jobs.

For each class k = 1,...,A", there is an independent demand process -Djt(r), which is
the number of class k units demanded up to time t. For now we will assume that Dk(t) is
a renewal process, and that interarrival times of this demand process have mean A^ and
variance a?. As will be seen in the next section, this assumption can be relaxed, and all
that is required is that £>* satisfy a functional central limit theorem (FCLT).

There are two types of decisions in the scheduling problem, and these decisions take
the form of cumulative control processes. Let the reiease process Nk(t) be the number
of class k jobs released to the machine's queue in [0,r]. Let the allocation process Tjt(i)
be the cumulative amount of time that the server devotes to serving class k jobs in [0,r].
Then the vectors TV = (7V fc ) and T = (7*) represent the release and sequencing policies,
respectively. Let Qk(t) be the number of class k jobs in the queue or in service at time
t, and let Zk(t) be the number of units (possibly negative) of class k jobs in the finished
goods inventory. The vectors Q = (Qk) and Z = (Z*) will be called the queue length
process and inventory process, respectively. If we assume that Q(0) = Z(0) = 0, then it
follows that for k = 1, ..., K and t > 0,

Qk(t)=N k (t)-Sk(T k (t)), and (2.1)

Zk(t)=Sk(T k (t))-Dk(t). (2.2)

Furthermore, if we define the cumulative idleness process I(t) to be the cumulative amount

of time the server is idle in [0, t], then

K

I(t)=t~Y t T k (t), forr>0. (2.3)

7



As in Harrison (1988), a scheduling policy (N,T) must satisfy

T is continuous with T(0) = 0, (2.4)

N and T are nondecreasing and JV(0) = 0, (25)

N and T are nonanticipating with respect to Q, (26)

J is nondecreasing with 1(0) = 0, and (2.7)

Q(t) > for all t > 0, (2.8)

where constraint (2.6) implies that the scheduler cannot observe future demands or service
times.

Now define the cost function c k for k = 1,...,A', by

0. (3.16)

y/n

Then a straightforward application of the functional central limit theorem for renewal

processes and the random time change theorem (see Section 17 of Billingsley) implies that

X n k ^X k , for* = l,...,A, (3.17)

10



where =>• denotes weak convergence, and X\,...,X k are independent Brownian motion
processes with drift y/n(\ k — fi k a k ) and variance a k ^i\s 2 k . Similarly, applying the above
two theorems and the continuous mapping theorem (Billingsley, Theorem 5.1), we have

X n k ^X k , for* = tf + l,..,2tf, (3.18)

where Xk+\,...,X 2 k are independent Brownian motion processes with drift —^/n(X k —
fi k Q k ) and variance a k fj. 3 k s 2 k + \ 3 k a. 2 k . Notice that any demand process satisfying afunctional
central limit theorem can be incorporated into our model. Thus characteristics of actual
customer demand, such as batch arrivals and dependencies across products (e.g., customers
arriving with demands for several products) can be modeled; see Section 6 of Reiman (1984)
for more details.

We are now in a position to state the limiting control problem, which is to choose
K— dimensional RCLL (right continuous with left limits) processes Y and 8 to

T K K

min limsup-£ r [/ VQ t (f) + Vc*(Z*(t))«ft] (3.19)

r-oo l Jo k=1 t=1

subject to Q k (t) = X k (t) + n k Y k (t)-6 k (t), for fc = l,...,A', and t > 0, (3.20)
Z k (t) = X K+k (t)-fi k Y k (t) fovk = l,...,K, and t > 0, (3.21)

K

U(t) = Yl Y k(t)iovt>0, (3.22)

fc=i
Q(t) > for all* > 0, (3.23)

U is nondecreasing with U(0) = 0, and (3.24)

9 and Y are nonanticipating with respect to X. (3.25)

4. The Workload Formulation

The basic system state equations (3.20) and (3.21) are in terms of the number of jobs in
WIP inventory and finished goods inventory, respectively. In this section, we reformulate
the limiting control problem (3.19)-(3.25) in terms of workloads, meaning that the two

11



inventories will now be expresses in terms of the amount of work embodied in them. First
define the one-dimensional Brownian motion B\ by

K
B 1 (t) = J2 m kX k {t), t>0, (4.1)

t=i

so that B\ has drift \/™ ]Ct=i m *(^*~ Hk 0, (4.2)

*=i

with drift y/n(l — p) > and variance /> -1 (X)fc=i ^* 5 *) + Ylk=i P\^* a \- The workload
formulation of the limiting control problem (3.19)-(3.25) is to choose the A'— dimensional
processes Q, Z, and #, and the one-dimensional process U to

T K K

min limsup-£ r [/ V Q k (t) + V c*(Z*(t)) 0, (4.4)

k=l k=l

K

Y J ™ k Z k {t) = B 2 {t)-U{t), for t > 0, (4.5)

*=i

Q( for all* > 0, (4.6)

U is nondecreasing with U(0) = 0, and (4-7)

Q, Z, U, and 6 are nonanticipating with respect to A'. (4-8)

Let (Y, 0) be a feasible solution to the limiting control problem (3.19)-(3.25) if (Y,9)
satisfies (3.20)-(3.25), and let (Q, Z, U, 8) be a feasible solution to the workload formulation
(4.3)-(4.8) if (Q, Z, U, 6) satisfies (4.4)-(4.8). Then problems (3.19)-(3.25) and (4.3)-(4.8)are
equivalent formulations, as can be seen from the following proposition.


1 3

Online LibraryLawrence M WeinDynamic scheduling of a multiclass make-to-stock queue → online text (page 1 of 3)