Back to "Search By Author"

002-0234

Optimal Lot Size Decisions Using the Wagner-Whitin Model with Backorders: A Spreadsheet Version

Second World Conference on POM and 15th annual POM Conference, Cancun, Mexico, April 30-May 3, 2004

Juan J. Gonzalez and Raydel Tullous The University of Texas at San Antonio 501 West Durango Blvd. San Antonio, TX 78255 [email protected] (210) 458-2528

Back to "Search By Author"

Optimal Lot Size Decisions Using the Wagner-Whitin Model with Backorders: A Spreadsheet Version

Abstract
A simple and practical form to find the optimal solution to the lot size ordering problem with backorders is presented. The process of optimization uses the framework of the transportation problem, and it is equivalent to the Wagner and Whitin algorithm. We recommend using a spreadsheet as the environment to carry out the computations required. We used Microsoft Excel due to its popularity and the availability of Solver as optimization tool. This approach eliminates the need for a special algorithm or computer code in order to generate the solution to the problem. We believe that this approach can easily be adapted to other specific lot size ordering situations and promote better decision making.

Introduction
Order management has been defined by Cox and Blackstone (1998) as the planning, directing, monitoring and controlling of the processes related to customer orders, manufacturing orders and purchase orders. In all cases, a decision policy or set of rules for lot sizes is established in order to determine the parameters related to an order. In general, lot-sizing involves the determination of the size of the order or order quantity and the timing of such decisions to satisfy the requirements of demand over a defined future horizon. Currently, many organizations attempt to satisfy the needs of their customers using complex enterprise resources planning systems (ERP) or advanced planning and scheduling systems (APS). However, from an optimization perspective, these systems lack the required features to provide recommendations that meet managements 2

Back to "Search By Author"

objectives. Hsiang (2001) indicates that systems currently on the market are fairly simplistic and do not optimize inventory operations. Most systems arbitrarily fix planning parameters such as lot size, lead-time and safety stock without any analysis by transferring the information from one generation system to the next. The reality according to Cusin (2001) is that ERP and APS systems require these important parameters as inputs and once they are provided, they are rarely validated. The operation of these planning systems requires these input parameters and it is up to the production planner to set them. Yet, simple practical tools to establish the parameters properly are rarely available to the planner. This is particularly true for the process of determining lot sizes. Dissatisfied with the square root formula to find the economic lot size under the assumption of steady-state (constant) demand, Wagner and Whitin (1958) developed an elegant forward algorithm based on dynamic programming principles to make optimal lot size decisions. The problem considered by Wagner and Whitin is the N periods problem with no backorders when the assumption of constant demand is dropped i.e., when the amounts demanded in each period are known but are different and furthermore, when inventory costs vary from period to period. Their 1958 paper is considered a classical and had been cited innumerable times in the lot-sizing literature. Their model formulation permits the determination of optimal lot sizes for a single item when demand, inventory holding charges and setup costs vary over N periods of time. The solution provided by the Wagner and Whitin algorithm (WWA) is considered the benchmark or standard against which other lot-sizing rules or heuristics are judged. Notwithstanding the fact of providing an optimal solution to the discrete lot-sizing problem, the WWA has been considered by many as an impractical approach. Many researchers indicate that the algorithm is difficult to use due to the dynamic programming nature of the procedure and 3

Back to "Search By Author"

other limitations such as computational time, computer memory and misunderstanding of its complexity (Evans 1985; Heady and Zhu 1994; Jacobs and Khumawala 1987; Saydam and McKnew 1987; Boe and Yilmaz 1983). For practitioners in general, the WWA is considered more as a philosophy of problem solving than as a technique for lot-sizing decisions. To circumvent the WWA inconveniences, numerous heuristic lot-sizing procedures have been developed such as Silver and Meal (1973), Groff (1979) and Gaither (1981). Blackburn and Millen (1985) reported that these heuristics produce satisfactory approximations in many cases. Friend et al. (2001) analyzed the performance of seventeen lot-sizing methods and the effects they have on inventory for an aircraft application. They concluded among other things that the WWA ranks number one if the total cost of the system is the criteria used to assess the performance of the methods. The rest of the lot-sizing rules, only approximate the WWA, which is taken as a benchmark against which the rest are measured. We suggest in this paper, that if a convenient and practical optimization procedure is available, then it should be considered and perhaps it should take precedence over popular approximation rules. Gonzalez and Tullous (2002) presented a convenient and practical way to solve the N periods discrete lot-sizing problem by transforming the model into an assignment problem and suggested solving it in a spreadsheet framework. In this paper, the discrete N periods lot-sizing model of the WWA is extended by considering backorders or equivalently to allow backlogging of demand to exit. The problem is formulated as a transshipment network model and then reformulated as a transportation model in order to facilitate the process of getting the optimal solution by using commonly available tools. In our model, if backorders are undesirable or not permitted to exist, the solution generated will be identical to the one produced by the 4

Back to "Search By Author"

WWA. The approach we are recommending is convenient and practical as it uses a spreadsheet as a tool to find the optimal size and timing of the orders. The remainder of the paper is organized into sections. Following this introduction, the general lot-sizing problem is presented. In the next section the model is extended to allow backorders and it is described as a transshipment network, and then reformulated as a transportation problem. The section that follows presents an example problem to illustrate the optimal lot-sizing decisions using the approach of this paper. A summary concludes this work.

The Lot-Sizing Problem

The lot-sizing problem described here considers an N-periods planning horizon problem with known demands d1, d2, d3 dN. The problem is to find an ordering policy which leads to an optimum total cost of combined acquisition (purchasing, receiving and inspection) costs, set-up costs, backordering costs and inventory carrying costs over the N-periods planning horizon. We use the following notations and definitions: di = known demand for period i, required at the beginning of the period (units) Si = Set up cost or ordering cost at period i, (dollars per set up) Ci = unitary acquisition or procurement cost at period i, (dollars per unit) hi = unitary carrying or holding cost at period i, (dollars per unit per period) bi = unitary backordering cost at period i, (dollars per unit per period) Ii = net inventory at the end of period i, (units) Bi = backorder position at period i, (units) N = the number of time periods in the problem Qi*= optimal quantity ordered or produced at the beginning of period i (units) The solution to this problem is the determination of the values Qi*, i = 1, 2,N such that all demands for the N periods are met at a minimum total cost. The case in

Back to "Search By Author"

which backorders are not allowed to exist is the situation whose optimal lot sizing decisions are the same as the solution given by WWA. The original WWA was designed to find the optimal policy for lot-sizing decisions by means of a forward recursive algorithm which first solves a one period problem and then sequentially solves subproblems until the overall N periods problem solution is found. The algorithm effectiveness in terms of reducing the number of computations or subproblems is due to the fact that if production takes place in a period t, the entering inventory for that period must be zero, that is Qt It-1 = 0. Also, if for any period t, a minimum total aggregate cost occurs at time period j where j t, then it is sufficient to consider explicitly periods 1 through j-1 separately. Proof of the theorems that support breaking the N periods lot-sizing problem into small subproblems is given by Wagner and Whitin (1958).

The Backordering Model

The original Wagner and Whitin model considered that backorders are not allowed to exist, therefore requiring that demand for period j, j =1, 2, N be satisfied with a decision for production in any time period t, t j. The backordering model relaxes this assumption and permits that demand for any given period j be satisfied with a production decision in any time period t, t N. If demand for period j is met with a production in time period t, t > j then an additional backordering expense is effected. The modeling of this backordering cost can be made as a function of the number of units backordered, the time period where the backorder exists, the number of backorders occurring simultaneously or by a variety of other forms. In this paper, we are considering backordering cost to be proportional to the quantity of units backordered or backlogged at time period t. The unitary backordering cost can vary from period to period but it is assumed that its value is known. 6

Back to "Search By Author"

An excellent way to explain and discuss the structure and relationships of the N periods lot-sizing problem is to conceptualize it as a network, in particular a transshipment network with N+1 nodes and 3N-2 arcs. The resulting network is shown in Figure 1. The nodes represent the source S and the time periods 1, 2, .N. At each node i, the demand is shown as di, whereas at the source node the supply is shown as the sum of all demands. The arcs represent the possible relationships among the different periods including the material balance conditions that relate demands with production variables, inventory carryovers and backordering quantities. There are N arcs Qi connecting the source node S to each of the time period nodes, these arcs represent the order quantities or lot sizes at time period i. There exist N-1 arcs Ii connecting nodes i to i+1; i= 1, 2, N-1 that represent the inventory position at time period i and also there exist N-1 arcs Bj connecting node i to i-1; i=N, N-1, N-2,2 that represent the possible backorders at time period i. ____________________________________________ Insert Figure 1 about here ____________________________________________

The Transportation Problem

The transshipment model of Figure 1 can easily be converted into a transportation problem by following the indications of Wagner (1975): (i) Designate a row for each source node. Its supply value is the stock supplied. In our model it is stated equal to di. (ii) Designate a column for each sink node. Its demand value is the amount of stock demanded. In our model, this instruction is ignored since our transshipment model has no sink nodes.

Back to "Search By Author"

(iii)

Designate a row and a column for each transshipment node. Let Tk be the nodes net stock position. If stock is supplied, Tk is a positive number. If stock is demanded, Tk is a negative number. Then for node k, let its supply and demand values be defined as Tk + B and B respectively, where B is the sum of stock available at all points.

(iv)

Permit variables for only the arcs existing in the transshipment network. For each transshipment node k, also permit a variable to exist with objective function coefficient ckk = 0.

Applying the previous rules to the N period problem of Figure 1 results in the equivalent transportation model shown in figure 2 where node S is the source and nodes 1 to N are the transshipment nodes. The shaded cells in the transportation table are nonexistent variables or nonexistent connections between pairs of nodes. Note that possible shipments are possible at the intersection of the row and column associated with each of the transshipment nodes where the associated transportation cost equal 0. It is obvious that these shipments from a node to itself are fictitious and help only to facilitate the modeling of the network as a standard transportation problem. ____________________________________________ Insert Figure 2 about here ____________________________________________ The precise description of the transshipment version of the lot-sizing problem in mathematical programming terms requires the definition of additional variables in order to model the set up costs. Let 1 Yj = if Qj > 0; j=1, 2, 3.N

0 if Qj = 0; j=1, 2, 3.N

Back to "Search By Author"

these binary variables reflect the situation that a value of one is required at any time period when a production quantity or lot size order is incurred. The linear programming formulation of the transshipment model is Mininize Subject to

A Y
j j=1

C Q
j j=1

h I
j j=1

N 1

b B
j j= 2

(1)

j=1

Qj =

j=1

dj

(2) (3) (4) (5) (6) (7) (8)

Q1 + B2 I1 = d1 Qj + Ij-1 - Ij + Bj+1 - Bj = dj ; j = 2, 3,.N-1 QN +IN-1 BN = dN Qj MYj < 0 ; j = 1, 2, 3,.N Qj + Yj > 0 ; j = 1, 2, 3,.N

Yj binary, Qj, Ij, Bj > 0 ; j = 1, 2, 3,.N, and M = very large positive number

In this model, the objective function (1) includes the sum of the set up costs, the acquisition or procurement costs, the inventory carrying costs and the backordering costs. Constraints (2) to (5) represent the material balance at the source node and at each transshipment node. Constraint (2) indicates that the quantities demanded must be produced at some point in time, however this constraint is redundant and can be ignored since it results by summing constraints (3) to (5). Restrictions (6) and (7) are necessary to accommodate the logic of this model since for Yj = 0 they imply that there is no production at time period j (Qj = 0). For Yj = 1, constraint (6) becomes ineffective, and constraint (7) redundant. Finally constraint (8) indicates the non-negativity restrictions for the variables Qj, Ij, Bj and the binary condition for the Yj variables. 9

Back to "Search By Author"

The equivalent transportation model of figure 2 can also be described in precise mathematical form using the classical format of the transportation problem: Mininize Subject to

Aj Yj +
j=1

Cj Qj +
j=1

cjj Xjj +
j=1

hj Ij +
j=1

N 1

b B
j j= 2

(9)

i =1

Qi =

i =1

di (10)

X11 + I1 = B - d1 Bi + Xii + Ii = B di ; i = 2, 3,N-1 BN + XNN = B dN Q1 + X11 + B2 = B Qj + Ij-1 + Xjj + Bj = B ; j = 2, 3,N-1 QN + IN-1 + XNN = B

(11)

Qj MYj < 0 ; j = 1, 2, 3,.N Qj + Yj > 0 ; j = 1, 2, 3,.N

(6) (7) (12)

Yj binary, Qj, Ij, Bj, Xjj > 0 ; j = 1, 2, 3,.N, and M = very large positive number

The objective function (9) includes those costs of (1) and the sum of the transshipment costs cjjXjj since the transshipment variables Xjj are required for this formulation. However, this term can be ignored as the cjj = 0, thus making (9) identical to (1). The N+1 constraints included in (10) represent the classical supply constraints of the transportation problem and the N constraints included in (11) are the classical demand restrictions. Also, the combination of constraints (6) and (7) are necessary to accommodate the logic of the model and (12) shows the non-negativity restrictions for the variables Qj, Ij, Bj, Xjj, and the binary condition for the Yj variables.
10

Back to "Search By Author"

Spreadsheet Solution
Spreadsheets are considered a very popular form of computer modeling for many applications and have become an indispensable business tool. Spreadsheets allow the user to combine data, mathematical formulas, text and graphics together in a single report or worksheet. Some spreadsheet packages like Microsoft Excel contain or allow ad-in modules with optimization features. Solver is the optimization tool of Excel. For a detailed set of instructions or tutorial about using Excel to solve linear programming problems see for instance Anderson, Sweeney and Williams (2003). To illustrate the process of finding the optimal solution to the lot size ordering problem with backorders in a spreadsheet format, we present and modify the four-period example discussed by Evans (1985). The data are:

Time period (i) Demand (di) Set up cost (Si) Procurement cost (Ci) Holding cost (hi) Backordering cost (bi)

1 60 150 7 1 2

2 100 140 7 1 2

3 140 160 8 2 1

4 200 160 7 2 1

The corresponding transshipment network is shown in Figure 2 with N = 4. The quantities Qi* = Qi that optimize the lot size ordering problem with backorders are obtained from a spreadsheet that solves the transportation problem. The Qi values are calculated by Solver, the optimization tool available in Microsoft Excel. Figure 3

11

Back to "Search By Author"

shows the spreadsheet of this example. The optimal solution is to produce 160 units in period 1 and 340 units in period 4 with a total cost of 4050. This solution will carry 100 units in inventory during period 1 to meet the demand of period 2 and backorder 140 units demanded in period 3 to period 4. ____________________________________________ Insert Figure 3 about here ____________________________________________ As expected, the spreadsheet model will produce the same result as given in Evans (1985) if the backordering cost are made very large, corresponding to the result given by the WWA.

12

Back to "Search By Author"

References
Anderson, D. R., D. J. Sweeney and T. A. Williams (2003), An Introduction to Management Science, Mason, Ohio: Thompson South-Western, 84-89. Blackburn J. D. and R. A. Millen (1985), A Methodology for Predicting Single-Stage Lot-Sizing Performance: Analysis and Experiments, Journal of Operations Management, 5, 4, 433-448. Boe, W. J. and C. Yilmaz (1983), The Incremental Order Quantity, Production and Inventory Management, 24, 2, 94-100. Cox, J. F. and Blackstone J. H. (1998), APICS Dictionary Ninth Edition, Falls Church: APICS-The Educational Society for Resource Management, 64. Cusin, J. D. (2001), A Lot Size of One? Get Serious, APICS-The Performance Advantage, 11, 11, 32-37. Gaither, N. (1981), A Near-Optimal Lot-Sizing Model for Materials Requirements Planning Systems, Production and Inventory Management, 22, 4, 75-89. Evans, J. R. (1985), An Efficient Implementation of the Wagner-Whitin Algorithm for Dynamic Lot-Sizing, Journal of Operations Management, 5, 2, 229-235. Friend, H. F., A. L. Swift and A. A. Ghobbar (2001), A Predictive Cost Model in LotSizing Methodology, with Specific Reference to Aircraft Parts Inventory: An Appraisal, Production and Inventory Management Journal, Third/Fourth Quarter, 24-33. Gonzalez, J. J. and R. Tullous (2002), The Lot Size Ordering Problem Using the Wagner-Whitin Model: A Spreadsheet Version, Proceedings of the POMS. Groff, G. K. (1979), A Lot-Sizing Rule for Time Phased Component Demand, Production and Inventory Management, 20, 1, 47-53. Heady, R. B. and Z. Zhu (1994), An Improved Implementation of the Wagner-Whitin Algorithm, Production and Operations Management, 3, 1, 55-63. Hsiang, T. (2001), The Illusion of Power, OR/MS Today, 28, 1, 34-36. Jacobs, F. R. and B.M. Khumawala (1987), A Simplified Procedure for Optimal SingleLevel Lot Sizing, Production and Inventory Management, 28, 3, 39-43. Johnson, L. A. and D. C. Montgomery (1974), Operations Research in Production Planning, Scheduling and Inventory Control, New York: John Wiley & Sons, 7479. Manne, A. S. (1958), Programming of Economic Lot Sizes, Management Science, 4, 2, 115-135. 13

Back to "Search By Author"

Saydam, C. and M. McKnew (1987), A Fast Microcomputer Program for Ordering using the Wagner-Whitin Algorithm, Production and Inventory Management, 28, 4, 15-19. Silver, E. A. and H. C. Meal (1973), A Heuristic for Selecting Lot Size Quantities for the Case of a Deterministic Time-Varying Demand Rate and Discrete Opportunities for Replenishment, Production and Inventory Management, 14, 2, 64-75. Wagner, H. M. and T. M. Whitin (1958), Dynamic Version of the Economic Lot Size Model, Management Science, 9, 1, 89-96. Wagner, H. M. (1975), Principles of Operations Research Englewood Cliffs: Prentice Hall, 181, 225.

14

Back to "Search By Author"

di

Q1

Q2

Q3

Q4

QN

I1

I2

I3 B3

I4

B5

IN-1

1
-d1

B2

2
-d2

B4

4
-d4

BN

N -dN

-d3

Figure 1.

TRANSHIPMENT NETWORK REPRESENTATION OF THE N PERIODS LOT-SIZING PROBLEM WITH BACKORDERS

15

Back to "Search By Author"

To From

S 1 2 3 4 : N
Demand

1 Q1 B2

2 Q2 I1

3 Q3 I2

4 Q4

. . . .

N QN

Supply B

B-d1 B-d2 B-d3 B-d4 : B : B-dN

B3 B4 : B : B : B

I3 B5 B

. I4 . BN B

Figure 2 TRANSPORTATION PROBLEM EQUIVALENT TO THE N PERIODS LOT- SIZING PROBLEM WITH BACKORDERS.

16

Back to "Search By Author"

Figure 3 SPREADSHEET OF THE TRANSPORTATION PROBLEM FOR THE 4 PERIODS EXAMPLE OF EVANS (1985)

17