Time-varying demands

From Supply Chain Management Encyclopedia

Russian: Спрос, изменяющийся во времени

Consider situations where demand changes over time.^[1] It also allows for time-varying purchase costs. Real demand rates and purchase costs do change, because of seasonal factors, or growing or shrinking markets, or other shifts in the economic landscape. The central managerial dilemma is to find the right balance between the cost of holding inventory and the cost of ordering, including scale economies. This issue is complicated here by temporal variations.

In practice, our current picture of future demand is a forecast. It is important to mention that the models of this chapter treat such forecasts as perfect. Demands change, but the changes are entirely predictable.

1. Extreme Cases

Consider a scenario like that of the basic economic order quantity in all respects but one: The demand rate is now a function of time, say $\, \lambda (t)$ . The cost factors remain constant. The general case of this model is quite difficult. There are a few special cases, however, whose solutions can be described in simple terms, at least approximately. Understanding these special cases will help build our intuition about the overall effects of time-varying demands.

1.1 Small Changes

First, suppose the demand rate $\,\lambda (t)$ changes over time, but only a little; there is some overall average demand rate $\,\lambda$ , and $\,\lambda (t)$ deviates from $\,\lambda$ by only a few percent.

Since $\,\lambda (t)$ is almost constant, the EOQ model with constant demand rate $\,\lambda$ is almost correct. If we use a constant order quantity $\,q$ , the EOQ's cost function $\,C(q)$ measures the actual cost quite accurately. Alternatively, if we use a constant cycle time $\,u, C(u)$ is a good approximation. There is no compelling reason to consider radically different policies. In sum, EOQ model's optimal policy ( $\,q^*$ or $\,u^*$ ) should work well, and its optimal cost $\,C^*$ should accurately approximate the true optimal cost.

The EOQ model is robust with respect to demand-rate changes. That analysis concerned persistent changes, changes over all time. Here, the deviations are transient. If anything, we should expect the EOQ model to be more robust in this setting.

1.2 Fast Changes

The scenario above limits the demand fluctuations' amplitude. The next two cases restrict their frequency.

First, suppose $\,\lambda (t)$ fluctuates quickly around an overall average $\,\lambda$ . Again, we define this condition loosely: For each $\,t$ , let $\,\underline{\lambda }(t)$ denote the average of $\,\lambda (\cdot )$ over a small interval near $\,t$ . Call a fast-changing demand rate, if $\,\underline{\lambda }(t)$ is nearly constant and equal to $\,\lambda$ . The fluctuations may be large, but they are so rapid, the averaging process damps them out.

Next Figure shows what happens.

The demand-rate fluctuations cause only tiny ripples in $\,D(t)$ and hence in $\,I(t)$ . Clearly, the EOQ model accurately measures the costs of alternative policies. Again, we can ignore the fluctuations and apply the EOQ model as is.

1.3 Slow Changes

Next, consider the opposite case: Suppose $\,\lambda (t)$ changes slowly. The idea, roughly, is that $\,\lambda (t)$ remain nearly constant over every plausible order interval. For instance, define

$\,u(t)=\sqrt{\frac{2k}{\lambda (t)h} }$

This is just the optimal order interval, computed for each $\,t$ as if the demand rate were constant at the current value $\,\lambda (t)$ . One way to define a slow-changing demand rate is to stipulate that $\,\lambda (\cdot )$ change only a little over the interval $\,{t, t }+ \textit{u}(\textit{t})$ , for all $\,t$ .

Here is a plausible policy: Order only when stock would run out otherwise, and if $\,t$ is such a moment, order the quantity

(1) $\, q(t)=\sqrt{\frac{2k\lambda (t)}{h} }$

That is, use the EOQ formula, treating the demand rate as constant at its current value. Alternatively, order just enough to meet demand until $\,t + u$ ( $\,t$ ).

Why should this heuristic work? Here is an intuitive argument: Consider a time period of intermediate length, covering several order cycles but no large shifts in $\,\lambda (t)$ and $\,q(t)$ . If $\,\lambda (t)$ really were constant, the EOQ model's optimal $\,q^*$ would nearly minimize the average cost over this period. Actually, $\,\lambda (t)$ does change, but only slightly, and each $\,q(t)$ is near $\,q*$ . So, the heuristic policy nearly minimizes the average cost over the period.

The basic idea is: The demand rate will change significantly only in the distant future, and we can ignore such changes in the current order cycle. (This is a myopic heuristic, one that focuses on the near future only. Such methods are effective in a variety of situations. We shall encounter them again later.)

The same reasoning suggests an approximation $\,C^*$ of the optimal average cost:

$\,C^{*} (t)=c\lambda (t)+\sqrt{2k\lambda (t)h}$

$\,C^{*} =\mathop{\lim }\limits_{T\to \infty } \left(\frac{1}{T} \right)\int _{0}^{T}C^{*} (t)dt$

(Think of $\,C^*$ ( $\,t$ ) as the approximate instantaneous cost rate. The integral can be evaluated exactly, of course, only for certain special forms of $\,\lambda (t)$ .

This model inherits the robustness properties of the EOQ model. For instance, $\,q(t)$ and $\,C^*$ change only slightly in response to a modest change in $\,k$ , and if the entire function $\,\lambda (t)$ doubles, each $\,q(t)$ increases only by $\,\sqrt{2}$ , as does $\,C^*$ . Moreover, $\,q(t)$ is dynamically robust as well. That is, consider one fixed function $\,\lambda (t)$ . If $\,\lambda (t)$ changes modestly over some interval of time, then $\,q(t)$

For this reason, an even cruder heuristic works fairly well: Keep the order size (or the cycle time) constant most of the time. Change it only when $\,q(t)$ (or $\,u$ ( $\,t$ )), as computed above, departs too far from the current policy. It is often easier to administer a policy whose variables change infrequently.

1.4 Discussion

To summarize: If the changes in $\,\lambda (t)$ are small and/or rapid, focus on the long-run average $\,\lambda$ , ignoring the current demand rate. If $\,\lambda (t)$ evolves slowly, focus on the current $\,\lambda (t)$ and ignore longer-run changes.

We can even combine these three cases: Suppose $\,\lambda (t)$ is the sum of three functions, a small-, a fast-, and a slow-changing one. That is, suppose the local average $\,\underline{\lambda }(t)$ does change over time, but only slowly. Following the arguments above, a reasonable heuristic policy is to set $\,q(t)$ according to (1), using $\,\underline{\lambda }(t)$ instead of $\,\lambda (t)$ .

This is still a rather extreme case. What about more typical cases, where $\,\lambda (t)$ includes changes of substantial size that are neither slow nor fast, but somewhere in between? The following crude guideline appears to work well: Suppose $\,\lambda (t)$ varies within a certain range. Compute the corresponding range of values for the EOQ formula, and set each order quantity within this range.

Of course, when the range of $\,\lambda (t)$ is wide, this guideline leaves a great deal of leeway. As discussed below, there seem to be no more precise, simple, reliable guidelines for finding a truly optimal or even close-to-optimal policy. Algorithmic methods, exact or approximate, appear to be essential.

1.5 A Finite Production Rate

Suppose there is a finite production rate $\,\mu$ . Small or rapid changes in $\,\lambda (t)$ can again be ignored, following the arguments above. Consider a slow-changing demand rate. For simplicity, assume $\,\lambda (t)$ is continuous.

The simplest case is where $\,\lambda (t)<\mu$ for all $\,t$ . The heuristic approach above can be adapted directly: Define $\,\rho (t)=\lambda (t)/\mu$ , and redefine

(2) $\, q(t)=\sqrt{\frac{2k\lambda (t)}{h[1-\rho (t)]}}$ .

Arguing as in Section 1.3, the policy using the $\,q(t)$ as batch sizes will likely perform reasonably well. (This formula presumes that stock produced can be used immediately to meet demand. Otherwise, revise it, replacing $\,1-\rho (t)$ by $\,1+\rho (t)$ )

This approach will not work, obviously, when $\,\lambda (t)>\mu$ for some $\,t$ . In that case, demand exceeds capacity, at least in the short run, and we must somehow anticipate such heavy-load periods. Next Figure illustrates the situation.

The horizontal line represents the capacity $\,\mu$ , and the curve is $\,\lambda (t)$ (The notation will be explained in a moment.)

Let $\,D(t)=\int _{0}^{t}\lambda (s)ds$ denote the cumulative demand. Feasibility requires $\,D(t)\le \mu t$ for all $\, t$ . Suppose there is a finite time $\,t_{+}$ , such that $\,\lambda (t)\le \mu$ for $\,t\ge t_{+}$ . There are no capacity shortages after $\,t_{+}$ and we can apply (2) as above; the difficulties come before $\,t_{+}$ . Choose $\,t_{+}$ as small as possible. By continuity, $\,\lambda (t_{+} )=\mu$ , and for $\, t$ below but near $\,t_{+}$ $\,\lambda (t)>\mu$ and

$\,D(t_{+} )-D(t)>\mu (t_{+} -t)$

Reducing $\,t$ further, this inequality certainly holds as long as $\,\lambda (t)>\mu$ , and it continues to hold for a while even when $\,\lambda (t)$ falls below $\,\mu$ .

At some point, however, cumulative supply catches up with cumulative demand, and

$\,D(t_{+} )-D(t)=\mu (t_{+} -t)$

Set $\,t\_$ to be the largest $\,t<t_{+}$ satisfying this equation. Thus, if we should arrive at time $\,t\_$ with no inventory, we must produce continuously at least until $\,t_{+}$ . The lightly shaded area in previous Figure is the total excess demand before $\,t_{+}$ , which must be anticipated by earlier production, and $\,t\_$ is the point where the darker area equals the light one.

Clearly, $\,\lambda (t_{-} )<\mu$ . For the moment, suppose $\,\lambda (t)\le \mu$ for all $\,t\le t_{-}$ , as in the previous Figure.In this case the original heuristic fails only during the interval $\,[t_{-} ,t_{+} ]$ .

This suggests the following modified heuristic: Apply (2) until $\,t_{-}$ , then produce continuously until $\,t_{+}$ , (Minor adjustments may be needed to hook up the long production run in $\,[t_{-} ,t_{+} ]$ with the short ones before and after.)

Conversely, suppose that some $\,t<t_{-}$ has $\,\lambda (t)>\mu$ . Thus, at some time before $\,t_{-}$ , the situation looks just like Figure. So, repeat the same approach: Identify a new $\,[t_{-} ,t_{+} ]$ , and schedule production around it in the same way.

Continue in this manner to identify such intervals, each requiring a relatively long production cycle to compensate for its short-term capacity shortage. Outside these intervals, apply (2) as above. (This procedure, like everything else in this section, is a heuristic.)

The broad effect of these extended production cycles on performance is clear: The early part of each cycle builds up inventory in order to meet demand in the later part when demand is heaviest. Thus, we end up holding larger inventories than we would otherwise.

The same ideas cover situations where the production rate also changes over time. i.e., $\,\mu =\mu (t)$ . One special case deserves mention, where $\,\mu (t)$ is proportional to $\,\lambda (t)$ , so $\,\rho (t)=\frac{\lambda (t)}{\mu (t)}$ is the constant $\,\rho <1$ .

Here, capacity expands and contracts in direct response to demand variations. Equation (2) reduces to

$\,q(t)=\sqrt{\frac{2k\lambda (t)}{h(1-\rho )} }$

As in the uncapacitated model, $\,q(t)$ varies as the square root of $\,\lambda (t)$ .

This discussion covers extreme cases only.

The general case requires intricate computational methods.

2. The Dynamic Economic Lotsize Model

2.1 Discrete-Time Formulation

This section formulates and analyzes an analogue of the EOQ model, where the demand and the purchase cost can vary over time in any manner.

To attain this level of generality introduce a very different conception of time. We model time as a finite sequence of discrete time points. We casually refer to time periods, the intervals between the time points, but in this view of the world all the significant events occur precisely at the time points themselves.

The problem, is the following: Demand for a product occurs at each of several time points. We must meet all demand as it occurs; no backorders or lost sales are permitted. We can order or produce supplies at each point, and we can carry inventory from one point to the next. Replenishment decisions take effect immediately; there is no order leadtime.

Each order incurs a fixed cost regardless of the size of the order, and also a variable cost proportional to the order quantity. There is a cost to hold inventory between any two successive points. These costs as well as the demands may change over time. The goal is to determine a feasible ordering plan which minimizes the total cost over all time points.

To formulate this problem, denote

$\,T$ = time horizon

$\,t =$ index for time points, $\,t=0,...,T$

The horizon $\,T$ is finite. Time period $\,t$ is the time from point $\,t$ until just before $\,t + 1$ . The data of the problem include

$\,d(t) =$ demand at time $\,t$

These are arbitrary nonnegative constants. The decision variables are

$\,x(t)=$ inventory at time $\,t$

$\,z(t)$ = order size at time $\,t$

The starting inventory at time $\,t = 0$ is the known constant $\,x_{0}$ .

We use the notation $\,d(t)$ instead of $\,\lambda (t)$ to emphasize that demand occurs in discrete chunks, not continuously. Also, we use $\,z(t)$ for the order size, not $\,q(t)$ .

We reserve $\,q(t)$ to describe a policy, indicating the amount to order if certain conditions are met, whereas $\,z(t)$ specifies precisely what to order with no conditions attached. This is the most common usage in the literature on discrete-time models, perhaps because $\,z(t)$ looks more like a decision variable than $\,q(t)$ .For similar reasons we denote inventory by $\,x(t)$ instead of $\,I(t)$ .

The precise sequence of events at each time point $\,t<T$ is as follows:

1. We observe the inventory $\,x(t)$ .

2. We decide the order size $\,z(t)$ .

Then, sometime during period $\,t$ , the order $\,z(t)$ arrives and the demand $\, d(t)$ occurs. We don't care precisely when these events happen, provided they are complete by the end of the period, in time to determine $\,x(t + 1)$ at point $\,t + 1$ .

The story concludes at step 1 of the last time point $\,T$ ; the terminal inventory $\,x(t)$ is important, but there is no order or demand at the horizon.

The cost parameters are the following:

$\,k(t) =$ fixed order cost at time $\,t$ $\,c(t) =$ variable order cost at time $\,t$

$\,h(t) =$ inventory holding cost at time $\, t$ .

These are all nonnegative. Let $\,\delta (\cdot )$ denote the Heaviside function, that is, $\,\delta (z)=1$ for $\,z>0$ , and $\,\delta (z)=0$ for $\,z\le 0$ . The total order cost at time $\,t$ is thus $\,k(t)\delta (z(t))+c(t)z(t)$ . The holding cost at $\,t$ is $\,h(t)x(t)$ . We ignore the constant cost $\,h(0)x(0)=h(0)x_{0}$ , but we do include the terminal holding cost $\,h(T)x(T)$ .

The model

Initial conditions:

(3) $\, x(0)=x_{0}$

Dynamics

(4) $\,x(t+1)=x(t)+z(t)-d(t),\, \, \, \, \, t=0,...,T-1$

Constraints:

$\,x(t)\ge 0,\, \, \, \, \, t=1,...,T$

(5) $\,z(t)\ge 0,\, \, \, \, \, t=1,...,T-1$

Objective function:

Minimize

(6) $\, \sum _{t=0}^{T-1}[k(t)\delta (z(t))+c(t)z(t)]+\sum _{t=1}^{T}h(t)x(t)$

This optimization problem is called the dynamic economic lotsize DEL model. It is also called the Wagner-Whitin problem after its inventors, Wagner and Whitin [1958].

Here is some additional notation, used below:

$\,D(t)$ - cumulative demand through time $\,t$ ,

$\,D(t)=\sum _{s=0}^{t}d(s)$

$\,D [t, u)$ - demand from time $\, t$ through $\,u- 1$

$\,D[t,u)=D(u-1)-D(t-1),\, \, \, \, t\le u$

$\,\tilde{c}[t,u)$ - variable cost to order a unit at $\,t$ and hold it until $\,u$ .

$\,\tilde{c}[t,u)=c(t)+\sum _{s=t+1}^{u}h(s),\, \, \, \, t\le u$

The DEL model can be reformulated to eliminate the nonlinear function $\,\delta$ from the objective by introducing additional binary indicator variables $\,v(t)$ . Here, $\,v(t)$ is 1 if we order at time $\,t$ , and 0 if not. (If you are familiar with integer programming, you will recognize this as a standard trick.)

The model requires some new constraints in addition to (5),

$\,v(t)\in \{ 0,1\}$

$\,z(t)\le D[t,T)v(t)\, \, \, \, t=1,...,T-1$

and the objective (6) now becomes linear:

Minimize

(7) $\,\sum _{t=0}^{T-1}[k(t)v(z(t))+c(t)z(t)]+\sum _{t=1}^{T}h(t)x(t)$

Thus, the DEL model can be expressed as a linear mixed-integer program.

2.2 The Linear-Cost Case

The linear-cost case, where all the $\,k(t)=0$ , is easy to solve, and the solution is interesting.

First, suppose that all the $\,c(t)$ equal some constant $\,c\ge 0$ . The solution is obvious: Assuming $\,x_{0} =0$ , set each $\,z(t) = d(t)$ and $\,x(t) =0$ . Likewise, if $\,x_{0} >0$ , order nothing until the initial stock runs out, and from then on order the minimal amount required to keep $\,x(t)\ge 0$ .

In general, order as little and as late as possible, while still meeting demand as it occurs. This is the discrete-time version of a perfect flow system - it meets all demands while holding no inventory (except any remaining from the initial stock).

Now, suppose the variable costs $\,c(t)$ do depend on $\,t$ . The basic economic issue here is the balance of purchase and holding costs: We can avoid projected cost increases by ordering earlier than necessary, but then we incur holding costs.

Assume $\,x_{0} =0$ for now. Consider any time $\, t$ and any single unit of demand within $\,d(t)$ . To fill that demand unit, we can order a unit at any time $\,s\le t$ .If we choose time $\,s$ , the total cost is just $\,\tilde{c}[s,t)$ .

This includes both the purchase cost $\,c(s)$ and the holding costs between $\,s$ and $\,t$ . To minimize this cost, compute

(8) $\, \tilde{c}[*,t)=\mathop{\min }\limits_{s} \{ \tilde{c}[s,t):0\le s\le t\}$

Let $\,\tilde{s}(t)$ denote the largest $\,s$ achieving this minimum.

This calculation applies to all the demand units in $\,d(t)$ . Thus, to solve the overall problem, we need only determine the best order time $\,\tilde{s}(t)$ to meet time $\,t$ 's demand, separately for each $\,t$ . These optimal order times are independent of the demand quantities $\,d(t)$ ; they depend solely on the cost factors.

The following recursive scheme streamlines the calculation:

(9) $\,\tilde{c}[*,0)=c(0)$

$\,\tilde{c}[*,t+1)=\min \{ \tilde{c}[*,t)+h(t+1),c(t+1)\}$

That is, there are only two possible values for $\,\tilde{s}(t+1)$ : If the first quantity in brackets is smaller, then $\,\tilde{s}(t+1)=\tilde{s}(t)$ , while if the second is smaller, then $\,\tilde{s}(t+1)=t+1$ . For each $\,t > 0$ , (9) requires the smaller of two numbers instead of the $\,t + 1$ in in (8). Also, in (9) there is no need to compute the $\,\tilde{c}[s,t)$ in advance. If we do order at some time $\,s$ , we order enough to meet demand at several consecutive time points (those $\,t\ge s$ for which $\,\tilde{s}(t)=s$ ). (This latter property holds for positive $\,k(t)$ too, as we shall see shortly.)

When $\,x_{0} >0$ , calculate the $\,\tilde{s}(t)$ as above. Not all of these times represent actual orders, however. Use the initial inventory to meet demands until it runs out, thus replacing some of the earliest orders.

Incidentally, when $\,\tilde{s}(t)<t$ , we say there is a speculative motive for holding inventory, for this means we anticipate an increase in the purchase cost from period $\,\tilde{s}(t)$ to $\,t$ , large enough to offset the intervening holding costs. If on the other hand $\,\tilde{s}(t)=t$ for all $\,t$ , as in the case of constant $\,c$ ( $\,t$ ), we say the problem offers no speculation opportunities. This latter case is important, even when there are additional complexities like fixed costs.

2.3 The Zero-Inventory Property

The general DEL model with positive $\,k(t)$ , as formulated above, is a hard-to-solve nonlinear program or an equally hard linear mixed-integer program. The model possesses a remarkable property, however, which we shall exploit later to devise a simple solution procedure.

Given a feasible solution, call $\,t$ an order time if $\,z(t)> 0$ . The central result describes the optimal schedule in terms of the optimal order times, and is called the zero-inventory property.

It is simplest to state assuming $\,x_{0} =0$ : Orders should be planned so as to run out of stock just as each order is received. This rule works in the general case $\,x_{0} \ge 0$ too, with a slight qualification: The first order may arrive when there is positive inventory, but only the first. Here is a formal statement:

THEOREM There exists an optimal solution $\,x^*(t), z^*(t)$ to equations (3) to (6) such that $\,z^*(t) > 0$ only when $\,x^*(t) = 0$ , for every $\,t$ except possibly the earliest order time.

The theorem asserts that this property continues to hold even with nonstationary data.

The zero-inventory property implies that, at each order time, we order precisely the amount needed to cover demand until the next order time. In particular, the order times completely determine the order quantities. This point is crucial for the reformulation of the next subsection. (Also, assuming $\,x_0 = 0$ , when the $\,d(t)$ are all integers, so are the $\,z^*(t)$ . This fact is useful: Sometimes it is important that the $\,z(t)$ be integral, though the DEL model itself contains no such restrictions. It doesn't need them; they hold automatically. This is even true, it turns out, when $\,x_0$ is positive but integral.)

Incidentally, there is another way to demonstrate the zero-inventory property: The objective is a concave function of the variables over the convex set defined by the constraints and the dynamics. Its minimum can be found, therefore, at an extreme point of the feasible region. It is possible to show that every extreme point has the zero-inventory property, so the optimal solution does too. We shall not pursue this approach here, but it is worth being aware of it. Several extensions of the DEL model can be analyzed in this way.

2.4 Network Representation and Solution

To solve the DEL model, then, the primary problem is to select the order times. Focus on the case $x_{0} =0$. This selection problem can be expressed in terms of a network: The nodes correspond to the time points $\, t$ = 0, . . . , $\, t$ . There is a directed arc from $\,t$ to \textit{и }for every node pair (\textit{t, u}) with \textit{t $<$ u. }Any specific choice of order times corresponds to a\textit{ path }in this network from node 0 to node \textit{T, }and vice versa. The nodes encountered along the path (excluding $\, t$ itself) identify the order times.

Now, consider any one path and a particular arc $\,(t, u)$ along the path. Choosing this arc means that $\,t$ is an order time, and we order just enough at $\,t$ to meet the demands at points $\,t$ through $\, u - 1$ . Let $\,k[t, u)$ denote the total cost incurred by this decision. The dynamics imply that $\,z(t)=D[t,u),x(t+1)=z(t)-d(t)=D[t+1,u)$ , and $\,x(s+1)=x(s)-d(s)=D[s-r,u)$ for $\,t<s<u$ . Thus,

(10) $\, k[t,u)=k(t)+c(t)z(t)+\sum _{s=t+1}^{u}h(s)x(s)=k(t)+\sum _{s=t}^{u-1}\tilde{c}[t,s)d(s)$

Now add the $\,k[t,u)$ over all arcs encountered on the path. This sum accounts for the all costs in all periods - it is the cost of choosing the order times along the path.

So, compute $\,k[t, u)$ for every arc $\,(t, u)$ in the network, and think of $\,k[t, u)$ as the travel cost along arc $\,(t, u)$ . To determine an optimal sequence of order times, find a path of minimum total cost. In sum, the DEL model reduces to a shortest-path calculation. There are very efficient solution procedures for such problems. (See Gallo and Pallottino [1986], for example.) This network is acyclic (there is no path from a node to itself), and the nodes are naturally ordered by $\,t$ , which makes the calculation even easier.

Let us look at one method in detail. It is called forward recursion. The idea is to compute the minimum-cost path from node 0 to every node $\,t$ , starting with $\,t= 1$ , then $\,t = 2$ and continuing until $\,t = T$ . This method solves the DEL model with horizon $\,t$ for each $\,t$ . Let $\,\tilde V(T)$ denote the optimal cost of the $\,t$ -horizon problem, so $\,\tilde V(T)$ is the optimal cost of the original DEL model.

Step $\,t$ aims to determine the last order time in the r-horizon problem, denoted $\,\hat{s}(t)$ . But, assuming $\,\hat{s}(t)=s$ for some fixed $\,s<t$ , we should set all earlier order times according to the optimal solution of the $\,s$ -horizon problem, so the total cost is $\,\tilde V(s)+k[s,t)\equiv \tilde V(s,t)$ . To find the best such $\,s$ , the actual $\,\hat{s}(t)$ , compute the smallest of the $\,\hat{V}(s,t)$ . The following algorithm embodies this idea:

Algorithm Forward_DEL:

Set $\,\tilde V(0)=0$

For $\,t = 1,...,T$ :

$\,\tilde V(s,t)=\tilde V(s)+k[s,t)\, \, \, \, 0\le s<t \tilde V(s)=\mathop{\min }\limits_{s} \{ \tilde V(s,t):0\le s<t\}$

$\,\hat{s}(t)=$ largest $\,s$ achieving this minimum.

Once this calculation is done, recover the optimal order times by tracing the $\,\hat{s}(t)$ back from $\, t$ . That is, $\,\hat{s}(t)$ is the last order time, $\, \hat{s}(\hat{s}(T))$ is the next to last, and so on.