Wallace B. C Crowston.

Lot size determination in multi-stage assembly systems online

. (page 1 of 2)
Online LibraryWallace B. C CrowstonLot size determination in multi-stage assembly systems → online text (page 1 of 2)
Font size
QR-code for this ebook

FEB 19 1971







no, So?' "7 I


MAR 1 1971



In a multi-stage assembly system each stage requires inputs from
a number of immediate predecessor stages and it supplies, in turn, one
immediate successor stage. An efficient dynamic programming algorithm
for lot size determination at all stages is derived for the infinite
horizon case under the assumption of constant demand. For the finite
horizon case with deterministic demand, an application of Benders'
mixed integer programming algorithm is presented. For the special case
of one predecessor for each stage, a dynamic prograimning algorithm is
developed .



Wallace B. Crowston and Michael Wagner
Sloan School of Management, M. I. T.


The classical economic lot size model is used to determine the
lot size that minimizes the sum of production and inventory carrying
costs for a single stage system. Demand is assumed to be continuous
and constant with no stockout permitted. A number of extensions to the
basic single stage model have been devised [7] including provisions for
non-instananeous production, and for discrete, but constant, demands.
A further large class of extensions considers stochastic demands. A
distinguishing characteristic of all of these models is that the objective
is minimization of costs over an infinite horizon.

A different fundamental approach to determination of lot sizes is
based on the assumption of discrete known dem.ands occurring through a
finite horizon. Such an approach allows consideration of non-constant
demands and a time varying objective function. Manne [10] , Dzielinski
and Gomory [4], H. Wagner and Whitin [lA] , and H. Wagner [15] develop
results for a single facilitv. Dantzig [3] introduces the concept of
multi-facility systems in which production of items at one facility
requires inputs from other facilities, and obtains solutions for a linear

cost structure. Veinott [13] and Zangwill [16-19] consider extensions
to concave cost objectives including the important case of a production
set up charge with linear production and holding cost.

A multi-stage assembly system is a special case of Veinott 's
general multi-facility system in that each facility or stage may have
any number of predecessor stages but is restricted to at most a single
successor. Gorenstein [5,6] considers systems of this form in the
context of the finite horizon planning models of Manne [10], and
Dzielinski and Gomory [4]. In this paper we develop a finite horizon
model and present solution techniques for two cases: the multi-echelon
system with each stage having a single predecessor, and the more general
multi-stage assembly system. The former case has been treated by Zangwill
[19] for concave objective functions. We modify his dynamic programming
algorithm to take substantial advantage of the particular objective
function under consideration. In the latter case we investigate the
application of Benders' partitioning procedure [1] for mixed integer
problems, and discuss how the assembly structure can be exploited to
computational advantage.

For the case of an infinite horizon we show in this paper that the
optimal lot size at any stage is an integer multiple of the lot size at
the succeeding stage. Using this result a total cost model is formulated
and a bounded dynamic programming algorithm is presented for the optimal
solution of the problem. In a companion naper, the authors with Henshaw
[2] discuss heuristic solution methods for this problem and give comparisons
of computational times and solution values for the heuristic routines and
a version of the dynamic programming algorithm to be presented below.

Schussel [11] discusses the problem and develops a heuristic for a more
general criterion function than that described in this paper.

Problem Description

In a multi-stage system, the manufacture of final product requires
completion of a number of operations or stages. A stage might consist
of an operation such as procurement of raw materials, fabrication of
parts, or assembly. A fixed sequence of operations is assumed, so that
output from one stage serves as input to an immediate successor stage.
The final stage is an exception in that its output is a finished product
used to service customer demand. Output from any stage mav be stored
until needed in that stage's inventory.

A multi-stage assembly system is characterized by the restriction

that each stage has at most one immediate successor. We emphasize that,

in general, a stage may have any number of immediate predecessors.

Examples of multi-stage assembly systems are depicted in Figures 1 and 2.

We shall denote a stage F , where n is an index ranging from 1 to


N, and F is the final stage. Let a(n) be the index of the immediate

successor of F , A(n) the set of indices of all successors, b(n) the

set of indices for all immediate predecessors and B(n) for all
predecessors. In T^igure 2 for example

a(6) = [7], b(6) = [4,5], A(6) = [7,17],
B(7) = [1,2,3,4,5,6].




€) 'X2

3 level, 1 stage per level system



^2 "3

4 levels, multi-stage per level system

For expositional convenience, we introduce the notion of a level, where

stages are assigned to levels according to: the final stage F is in

level L„, and F is in level L^, if its successor F . . is in L„, , •
M n M a(n) M+1

It is assumed throughout that demand is known with certainty.

The objective is minimization of the cost of satisfying all demand with

no backorders. Costs are assumed to depend upon the stage, F , there


being a fixed charge for production setup, s ($/setup) , and a linear

inventory holding cost, H ($/unit/time) . One unit at a stage is the

quantity required in one unit of final product.

We will find it convenient to refer to an incremental inventory

holding cost, h , defined by: h = H - E H . The concept of an
n n n , , , m


incremental holding cost is closelv related to that of 'value added" at a

production stage. In fact, the holding cost in many situations might

be: H = C I, where C = total value of a completed stage n unit and
n n n

I is a cost of carrying inventory and h = c I, where c = value per

n n n

unit added by the stage n process. We note that a direct per unit
production cost, p , can easily be added to the models discussed herein,
but such a term has no effect upon the lot size decision and simply
adds a constant to the total costs.



A finite horizon model makes it possible to express non-constant
demand for final product and time varying objective functions. The
special case of a system with a single stage for each level, such as
that depicted in Figure 1, has been treated by Zangwill [19]. He develops
a dynamic programming algorithm under the assumption of a general concave
cost function. Under the more restrictive assumption of a time invariant
cost function, we present a characterization of the form of an optimal
solution to the multi-stage per level assembly system. Aoplication of
Zangwill 's algorithm is then discussed for the single stage per level
case with simplifications arising from our restricted objective function
noted. It is found that Zangwill 's algorithm cannot be simply extended
to the multiple stage per level case. We thus turn to a mixed integer
linear programming approach and describe application of Benders'
partitioning procedure.

Model Formulation

We assume that demand occurs at discrete points in time, production is
instantaneous and that we wish to minimize costs over a finite number
of time periods T. Then the problem of economic lot size determination
can be given a mathematical programming formulation which shall be

referred to as Problem I;

Let Q = Production quantity at stage n at time t
nt T 7 o

Y = Ending inventory at stage n at time t



if Q^^ > 0,

if Q^^ = 0;

given R = Demand for final product at time t

H = One period inventory holding cost
S = Production set up cost

then minimize Z = EZ(H-Y+Sd) I. A

n t n nt n nt

subject to Q^^ + Y^^_^ - Y^^ - Q^^^^^ = n=l,...,N,

t=l,...,T, I.B

Q > 0, Y > for n,t

nt — nt —

where Y ^ = Y „ = for all n

nO nT

Q /„^ = R for all t

^a(N)t t

M d - > 0, d 0-1 integer for all n,t I.C

t nt -nt — ' nt

where M is a suitably large constant, namely, M = E R .


Form of an Optimal Solution

This model is an example of the multi-facility economic lot-size
model discussed by Veinott [11]. In this connection, we remark that
the objective function I.A is concave. Furthermore the constraint set
I.B is of the form Ax = b , where A is a Leontief matrix, that is, each
column of A has exactly one positive element. Following Veinott, we
obtain the following characterization of an optimal solution:
a) production at a stage does not occur if entering inventory already
exists; and b) production at a stage does not take place unless
production also occurs simultaneously at the immediate successor stage.
These results are summarized in Theorem 1.

Theorem 1: Form of the Optimal Solution. There exists an optimal
solution to Problem I with the properties that

a) Q ^ • Y , = for all n,t; and

^nt nt-1

b) Q • (1 - d , , ) = for all n,t,
^nt a(n)t '

A detailed proof is given in the Appendix. Approximately stated,

property a) is direct consequence of Veinott's Corollary 2 [13] which

characterizes extreme point solutions of Leontief substitution systems.

Property b) depends upon the time invariance of the cost functions

H and P . We start with a presumed optimal solution and show that
nt nt K f

it can be modified so as to satisfy the conditions of Theorem 1 with

identical setup costs and at no increase in inventory holdings costs.
Theorem 1 provides the basis for a dynamic programming algorithm for
solution of the single predecessor case.

Dynamic Programming: One Stage per Level

We now consider the case in which each stage has no more than one
predecessor. This model has been analyzed bv Zangwill [19] for concave
cost functions. He develops the dynamic programming recursion:

F (a,B) = Min {P , . I R + F , . (a,n)
nt T T, a(n)t m a(n)t

a-lQ h

• ii; ^—*(S^ ^— T 1 3


.^^22) »(^23)

Given: d^^ = d^^ = d22 = ^

^12 = ^^13 = ^23 = °

"11 = °' "12 = ^1 + "l' ^3 = "^12 ■*■ "1

w = w + 0, W22 = min(w^2' ^21 "*" ^^2^ ' ^23 ^ ^''22 "*" ^2

^1 = ^21 = ^22 = °' ^12 = ^12' ^3 = ^3' ^23 = ^23 " "l3





In this section we focus on the problem of determining the set of
optimal lot sizes in an N-stage assembly system under assumptions of
constant discrete demand and infinite production rates with no back-
orders. We shall refer to this as the Basic Problem. In addition to the
Basic Problem described above we briefly discuss the case of non-instanta-
neous production and the case of delivery delay between stages. We also
examine the implications of these models for the development of heuristic
solution techniques for more complicated multi-facility structures.

For the special case of a single predecessor for each stage, or
serial production, there are two recent contributions. The model of
Taha and Skeith [12] allows non-instantaneous production, delay between
stages and back-orders for the product of the final stage. They assume
that in an optimal solution the lot-size at a stage is an integer multiple
of the lot-size at the succeeding stage and suggest the problem be solved
by examining all combinations of such integer values. Jensen and Khan
[9] also allow non-instantaneous production but do not use the assumption
of positive integers. Instead they have constructed a simulation model
which evaluates the average inventory at a stage, given the lot size
at that stage and at the succeeding stage, along with the production
rate at both stages. A dynamic programming algorithm is then formulated in
which the simulation model is used in evaluation of each functional eauation.
They note that high average inventories result if the integer multiple


assumption is not followed and discuss a problem for which non-constant
lot size is optimal.

For the multiple predecessor case Schussel [11] develops a simulation
model and heuristic decision rule which again assumes that integer
multiples are optimal. He adds a "learning curve" function so that
unit production cost decreases with lot size and allows costs to be
discounted over time. Crowston, Wagner and Henshaw [2] tested four
heuristic rules and compared them with a version of the dynamic programming
algorithm developed in this paper.

In this section we prove that under certain assumptions the "integer
multiple" assumption used bv others is correct. A particularly
simple model of the total cost structure is then formulated and a
dynamic programming algorithm is developed to find optimal lot sizes
for all stages in the system. It is shown that the cost structure may
be used to develop upper and lower bounds on all lot sizes and thus
increase the efficiency of the dynamic programming algorithm.

Form of the Optimal Solution

We consider only solutions which can be characterized bv a single

lot-size for each stage. Let k = Q /Q , . and K = Q /Q., . A particular

n n a(n) n n N

solution is given by k^ = {k^ ,k^ , . . . ,k^_^, 1} and Q^ or by K^ = {kJ,K^,

. . . ,K^_ , 1} and Q^. Then it can be shown that the ratio of lot sizes
between successor and predecessor stages, k , must be a positive integer.
This result is summarized in Theorem 2.


Theorem 2 : Form of the Optimal Solution. If the set of all solutions

to the Basic Problem which can be characterized by a set of rational

lot size multiples k and final stage quantity Qjl, a minimum cost

solution exists with od, and k all positive integers.

A detailed proof is given in the Appendix. An expression is

derived for the costs associated with a lot size Q given . . . This

n "a(n)

function is shown to be minimized with k = Q /Q , v a positive integer.

n n a(n)

Proof then follows by induction over the levels of the svstem.

We wish to emphasize that the assumption of a time-invariant lot
size for each stage is quite strong. The possibility of cyclic lot
sizes, for example, is thus eliminated. The restriction may be
justified, in some cases, by the costs of administering changing lot
sizes. In any event. Theorem 2 leads to computationally powerful
algorithms for finding the optimum in a class of easily imnlemented
solutions. Given the results of Theorem 2, we now derive expressions
for the total costs of a particular solution k , Q~ .


Development of the Model

If all lot sizes within the system were equal, then, given instanta-
neous production and no transfer delay, inventory would be held only at the

final stage. If Q ?^ Q / x then in-process inventory occurs at F and the
" n a(n) n

average level of such inventory is a complicated function of Q and

Q , - . The value of a unit of such inventory would be C = E c + c
a(n) n „, , m n

^ meB(n)

and the carrying cost would be IC . In Figure 5 we show the inventory

at each stage of a 3-stage production process with K = 6 , K„ = 2 and

K3 = l.

As we have implied above, existing models have been based on a

determination of average inventory at a stage . A simpler but mathematically

equivalent formulation results from an expression of the inventory in the

total system that has undergone the activity of a particular stage.

Figure 6 illustrates such system-wide inventory for the 3-stage problem.

Since the demand on the system is assumed constant, the total system

inventorv of units that have undergone the activity of F will decline

at rate R between successive production of Q . Given the optimality

'^ n

condition of Theorem 2, and Q , . will be produced simultaneously.

n a(n)

Since this is true for all stages F , m e A(n) , at the instant before

° m

Q is produced the complete system inventory of units that have undergone

the activity of F will be zero. At that point in time a lot is

produced and the system inventory becomes Q with units possibly located

at F and F , m e A(n) . We observe that the system inventory of the

n m — — '

product of any stage has the familiar saw-tooth pattern of the basic
E.O.Q. model and thus the average inventory for the product of F would be









i I





^2 1^




















Q^ - 1

assuming discrete demand. The value of this inventory will be

c per unit and therefore the holding cost will be

Q - 1 0-1

The total cost for the product of F , including set-up and inventory


carrying cost will be

RS 0-1

TC = -^ + (-^^— ) h^ (4)

n Q In

and the total cost for the system, s, will be

N RS Q - 1
^ n=l ^n 2

N RS K Q„ - 1

n=l n N

Note that for a particular vector K-^ the optimal value of Q will be



Simple Extensions of the Model

In this section we briefly consider a special case of non-instanta-
neous production and the case of transfer delay between stages. If we assume

production rate p at F and given p > v> / \ then the result of
^ n n n — a(n)

Theorem 2 applies. The cost function for the product of F will be

TC = RS /K Q.. + [(K 0,, - 1)/2][1 - R/p ]h . (7)

n n n N n N n n

Finally we observe that a transfer delay between stages simply adds
a constant inventory term to either equation (4) or (7) and therefore
does not affect the optimal solution.

The Dynamic Programming Algorithm

The dynamic programming algorithm is written in terms of the simplest
cost structure although it is clear that it could be modified to include
the cost function for non-instantaneous production. Solution proceeds
from the raw material stage to F,, with the recurrence relation defined
as follows.


Let L denote the set of all positive integers; u (O ) , the optimal

n n

cost at F and all prior stages F , m e B(n) given Q . Then
n in n

(Q^ - 1) RS^

u (0 ) = t; h + - — + Z minimum u (2.Q ) . (8)

n^n^ 2 n Q u/ ^ n t m ^n
n meb(n) HeL

Optimal solutions for the system of Figure 2 have been obtained
with this algorithm in approximately ten seconds of computation time
on a time-shared GE 645 system [2].

We note that an inventory space constraint at F may be included


directly as an upper bound on Q . Other bounds are possible given the
form of cost function ( 4 ) . We will now develop both upper and lower
bounds on Q so as to improve the theoretical efficiency of the dynamic
programming algorithm.

If we assume a problem with cost structure (4 ) , then at F a
lower bound, b , on the cost of system inventory of that stage will be

RS /2RS h
" ■'2RS \l K 2

This assumes no interdependency between successive stages. Then a
lower bound for the complete system, B will be

= E b


An upper bound on total cost B for the system may be derived from a
feasible heuristic solution [2] to the problem. Thus an upper bound
on the cost of the product of F will be


Online LibraryWallace B. C CrowstonLot size determination in multi-stage assembly systems → online text (page 1 of 2)