> Teach Dynamic Programming Add-in - Line Partition
A class of problems for which dynamic programming can be effectively applied involves the partitioning of a line into non-overlapping segments. Applications include production scheduling for finite time horizon, capacity expansion of a production facility, and setting up inspection stations along an assembly line. In the definition of these problems both the state and decision vectors have a single component, making them easy to solve. From a modeling point of view, they are illustrative of the case where the classical stage representation for dynamic programming is not appropriate.

Consider a line, as with n+1 discrete points or nodes numbered 0 to n

The problem is to find an optimal partition of the line into segments such that each segment begins at one node and ends at another. Some objective or payoff function is associated with each continuous subsequence of nodes, and is typically nonlinear. The figure shows one possible partition.

A vector of selected nodes defines a solution, with each adjacent pair of nodes defining a segment of the line. Thus a general solution comprising k segments can be written as a vector; that is,

Note that the number of segments, k, is a variable in this problem.

A cost function is defined in terms of the nodes the comprise the segments with c(i , j) the cost of the segment starting at node i and terminating at node j.  The cost of a solution is the sum of the segment costs. The goal is to minimize this cost.

 To make a model of this class, click the Line option on the dialog. The line length is the number of points in the line not including 0. Thus when 10 is entered, the nodes on the line are numbered 0 through 10. The Max in interval entry is the length of the maximum segment. In the figure above, the center segment has a length of 4. To reduce computation effort, this number might be chosen as some number less than n. There are three data form values 0, 1 and 2. We illustrate the three cases below.

Line Partition

 For this case we adopt a simple cost function for a segment that is it is the number of nodes in the segment squared plus a fixed cost. For the example we use a fixed cost of 10. Thus for a segment passing from node i to node j the cost is c(i, j) = 10 + (j - i)^2 The definition of this cost function distinguishes one model from another. There are no restrictions, such as convexity, on the characteristics of the function. One of the strengths if dynamic programming is that it can be used for all kinds of objective functions. The model for this line problem is partially shown at the left. The case illustrated is for s=3 and d= 3. All line problems have a single state variable and a single decision variable. The maximum decision value is set so that a segment does not go beyond the last node. The forward transition equation is: s' = s + d For the example s' = 6. The add-in builds a worksheet with all formulas and data structures automatically provided. For some cases, the built in formulas and data structure must be modified. In this case the formula for the cost function is placed in cell F51. The definition of the fixed cost in F47 and the objective function calculation in F51 is added to the model.

Click the Solve button at the top of the page to perform the dynamic programming algorithm. For the example, we generate all feasible states first, and then perform the backward recursion method of dynamic programming. When the complete solution is obtained we use the forward recovery method to return the solution. The solution is shown below together with the statistics of the solution process.

Capacity Expansion

A power company expects a growth in demand of one unit (100 megawatts) of power for each year in the next 20 years.  To cover the growth the company will install additional plants with capacities in integer sizes of 1 through 10.  The size chosen will determine how many years before the next capacity expansion is required.  The cost for the 10 sizes is shown below.

 Size 1 2 3 4 5 6 7 8 9 10 Facility Cost 15 16 19 24 30 34 39 45 49 54

The goal is to minimize the present worth of the expansion costs for the next 20 years.  We use i to indicate the interest rate for present worth calculations, and assume i = 5%.  To illustrate how the objective function is evaluated, say we choose to build plants in the size sequence 4, 6, 5, 5.  This means that the expansions occur at times 0, 4, 10 and 15 so the present worth of the costs is

The situation can be modeled as a line partitioning problem with

where c(d) is given in the cost table as a function of the expansion size d.  The exponent of the discount factor is s, the year of installation. In the DP model this is the state variable.

The problem is created in Excel with the Line option on the model dialog. Here we specify the data structure option as 1. The add-in builds the DP form and adds a single vector to the right of the model (in column N). We have added the entry in N9 to hold the interest rate. To complete the model, place the function z(s, d) in cell F51.

Solving the problem yields the optimum solution. A facility is built at time 0 of size 6. The second facility is built at time 6 of size 6. At time 12 a facility of size 4 is built. Finally a facility of size 4 is built at time 16. The discounted cost of the plan is 83.73.

Production Scheduling (Wagner-Whitin algorithm)

A manufacturing facility has forecasted demand for the next 20 weeks as shown in the table below.  There is a fixed cost for setting up a production run equal to f.  In addition, there is a variable cost v that is proportional the number of items produced.  If we produce more than the demand in a particular week, the excess items are stored until needed.  The inventory cost is proportional to the number of units and the number of weeks stored.  The cost per unit per week is w.  The problem is to find a production schedule that minimizes the total fixed, variable and inventory costs. Demand data used for the example is below.

 Period 1 2 3 4 5 6 7 8 9 10 Demand 3 1 7 0 0 2 8 2 3 2

 Period 11 12 13 14 15 16 17 18 19 20 Demand 9 4 1 8 3 3 8 6 5 5

The appropriate dynamic programming model is similar to that for the line partitioning problem.  When applied to the inventory problem, the approach is called the Wagner-Whitin algorithm.  The line to be partitioned in this case is the time line.  The nodes correspond to the times {0, 1, 2,…,20}.  A solution is described by a sequenced set of times at which production occurs.  For this case n = 20.  With the cost computations described above, it can be shown that when production occurs, it is always optimal to produce exactly the quantity demanded for the interval being considered (Dreyfus and Law 1977).

To express the decision objective in general terms let be the demand in week t, and let c(s, s') be the cost associated with producing at time s to satisfy the demands for periods s+1 to s'.  The cost function has three components.

To illustrate, we calculate z(s, s') for s = 0, d = 6 and s' = 6.  The parameter values are f = 30, v = 4 and w = 1.

To implement the model in Excel, we again choose the Line model option, but for this problem we use the Data Form as option 2. This creates a two-dimensional table shown below as starting in column N. We have placed the cost parameters in column L. Only part of the table is shown since it has 20 columns. The table entries compute values for c(s, d), the cost of producing items at time s. The amount produced is sufficient to cover the demand for d periods. For example the entry in cell N17, 107, is the cost of producing 13 units at time 0 and paying inventory on the items until they are consumed.

The Excel DP model requires no modification. The decision objective formula is a direct reference to the table.

 The model requires a state variable and a single decision variable. Clicking the Solve button solves the problem. The solution statistics are below. There are 21 states. Using the line partitioning model with this cost function, the optimal sequence is (0, 6, 10, 13, 16, 20).  The table depicts the results.  The first five components of this sequence are production times; the corresponding production quantities are 13, 15, 14, 14  and 24, respectively.  The total cost is 555.

If a problem is equivalent to the optimum line partitioning problem, DP requires only a single state variable. The problem is very efficiently solved.

Operations Research Models and Methods
Internet
by Paul A. Jensen