# An O(T 3 ) Algorithm for the Lot-Sizing Problem with Constant Capacities and Large Inventory Bounds

Victor Spitzer

► To cite this version:

Victor Spitzer. An O(T 3 ) Algorithm for the Lot-Sizing Problem with Constant Capacities and Large Inventory Bounds. 2024. hal-04774355v3

HAL Id: hal-04774355

https://hal.science/hal-04774355v3

Preprint submitted on 16 Dec 2024

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# An $O(T^3)$ Algorithm for the Lot-Sizing Problem with Constant Capacities and Large Inventory Bounds

Victor Spitzer<sup>a,b,*</sup>

<sup>a</sup>Lhyfe, Nantes, France

<sup>b</sup>LISN, Université Paris-Saclay, Gif-sur-Yvette, France

## Abstract

This work aims at designing a new algorithm of improved complexity to solve the lot-sizing problem with constant capacities and inventory bounds, in cases where those bounds are twice higher than the production capacity at all time. We build upon previous works by investigating the decomposition of this optimization problem into subplans. New results on the feasibility and optimality of a subplan are proposed that lead to an improved algorithm of cubic worst-case complexity.

**Keywords:** Lot-Sizing, Constant Capacities, Inventory Bounds, Computational Complexity

## 1. Introduction

The Lot-Sizing problem covers a broad range of application for the optimal planification of production, and its size often requires efficient algorithms for its resolution. It represents, across $T$ consecutive periods of time, the interaction between a demand for an item, the production generating such item and the use of an inventory to store items produced in advance. The cost of production are considered to be linear, however a setup cost must be accounted for at any period of production. Holding costs linearly penalize the amount of item in inventory at each period. The objective is to find a feasible production plan that minimizes total costs.

This work tackles the Single-Item Capacitated Lot-Sizing problem with constant production capacity, linear costs and inventory upper bounds. Existing polynomial algorithms for the resolution of this problem are of $O(T^4)$ complexity at best. We undertake an in-depth study of the feasibility and optimality conditions of such problems and we derive properties that lead to an improved algorithm of $O(T^3)$ complexity for instances whose potential for storage is at least twice the production capacity.

### 1.1. Related work

The Lot-Sizing problem has been widely studied for decades as its applications and variations are numerous (Brahimi et al., 2017). There has been precise studies of its complexity in order to classify which models could be solved in polynomial time, or were otherwise NP-hard (Brahimi et al., 2006). The Capacitated Lot-Sizing Problem (CLSP) may be classified by a system first introduced by Bitran and Yanasse (1981), where each problem belongs to a particular category depending of its setup costs, holding costs, production costs and production capacity being non-increasing (NI), non-decreasing (ND), of none value (Z) or "general" (G) otherwise. In our case, we study the G/G/G/C CLSP with general setup costs, holding costs, production costs and constant production capacity, with an added upper bound constraint on the maximum inventory capacity. The standard G/G/G/C CLSP has been shown to be solved in polynomial time, first with an $O(T^4)$ algorithm (Florian and Klein, 1971) then later with an $O(T^3)$ algorithm (van Hoesel and Wagelmans, 1993).

The G/G/G/C Lot-Sizing Problem with Constant Capacities and Storage Upper Bounds, denoted LS-CC-SUB in the following, was first introduced by Erenguc and Aksoy (1990). It has been studied by Wolsey

<footnote>*Corresponding author.</footnote>

<footnote>Email address: victor.spitzer@lhyfe.com (Victor Spitzer)</footnote>
(2005), demonstrating equivalences between that problem and certain cases of Lot-Sizing problem with time-windowed demand and showing it can be solved with a polynomial $O(T^4)$ algorithm. A special case of the LS-CC-SUB was solved in $O(T^3)$ complexity by Akbalik et al. (2015) for a problem with Wagner-Whitin cost structure. An optimality property for the LS-CC-SUB with lower and upper bounds on the production and storage capacity is given in Love (1973), although the study is restricted afterward to the uncapacitated lot-sizing problem (without upper bound on production capacity) with inventory bounds.

## 1.2. Contributions

In the following, an introduction to the studied mathematical model is first proposed in section 2 where general assumptions on the model are made and the notion of subplan is developed. We then focus on the feasibility conditions of a subplan for the LS-CC-SUB in section 3, and on a dynamic procedure to solve a subplan in section 4. The resulting properties on feasibility and optimality allow for the design in sections 5 and 6 of an efficient dynamic resolution that improves the overall complexity.

# 2. The Lot-Sizing Problem with Constant Capacities and Storage Upper Bounds

## 2.1. Mathematical model

We present a general model for the LS-CC-SUB. Let $C$ denote the constant production capacity in each period. For any period $t \in [|1, T|]$, we define the following parameters:

* $I^0$ the initial inventory value;

* $S_t$ the inventory capacity in $t$;

* $s_t$: the setup cost in $t$;

* $c_t$: the production cost in $t$;

* $h_t$: the holding cost in $t$;

* $d_t$: the demand in $t$;

Furthermore for any periods $1 \le t_1 \le t_2 \le T$, the cumulative demand in $[|t_1, t_2|]$ is denoted by $d_{t_1, t_2}$. Then for each period $t \in [|1, T|]$, we define the following variables:

* $x_t$: the production value in $t$;

* $I_t$: the inventory value in $t$;

* $z_t$: the choice to produce in $t$.

A general model for the LS-CC-SUB is then:

$$ \min \sum_{t \in [|1, T|]} z_t \cdot s_t + x_t \cdot c_t + I_t \cdot h_t \quad (1) $$

$$ \text{s.t.} \quad x_t \le z_t \cdot C \qquad \forall t \in [|1, T|] \quad (2) $$

$$ I_1 = I^0 + x_1 - d_1 \qquad (3) $$

$$ I_t = I_{t-1} + x_t - d_t \qquad \forall t \in [|2, T|] \quad (4) $$

$$ I_t \le S_t \qquad \forall t \in [|1, T|] \quad (5) $$

$$ I_t, x_t \ge 0 \qquad \forall t \in [|1, T|] \quad (6) $$

$$ z_t \in \{0, 1\} \qquad \forall t \in [|1, T|] \quad (7) $$

## 2.2. Simplifying assumptions

We present three assumptions made without loss of generality to simplify the mathematical model of the LS-CC-SUB and derive necessary properties for the design of our novel algorithm.
### 2.2.1. Assumptions on holding costs

In the following, we assume the holding costs to be of zero value. If it is not the case, an equivalent problem is obtained by integrating the holding costs to the production costs (see, e.g., Wagelmans et al. (1992)). Suppose we define new production costs $c'$ such that $c'_{t} = c_{t} + \sum_{t'=1}^{t} h_{t'}$ for all periods $t \in [|1, T|]$. Then an equivalent model to (1)-(7) without holding costs would be:

$$ \min \sum_{t \in [|1, T|]} z_t \cdot s_t + x_t \cdot c'_t - \sum_{t \in [|1, T|]} h_t \cdot d_{1,t} \quad (8) $$

$$ \text{s.t. (2)-(7)} \qquad (9) $$

Hence in the following, we always assume the holding costs $h$ to be of zero value.

### 2.2.2. Assumptions on the demand

We also assume the demand to be upper-bounded by the constant production capacity $C$ at any period $t \in [|1, T|]$. If it is not the case, an equivalent problem with modified demand and inventory value can be found for which this property applies. This equivalent model is obtained by displacing any demand above the production capacity to earlier periods, so that it can be stored in advance.

Applying this technique is trivial for the unbounded inventory problem (see, e.g., van Hoesel and Wagelmans (1993)), however in the bounded case the inventory capacity must also be modified. Although it has been alluded to by Wolsey (2005), we propose to precisely define how to transform such instances of the LS-CC-SUB. A necessary condition for the LS-CC-SUB to be feasible is that the inventory capacity must be higher than the inventory value needed to meet current and future demand. Let $I_t$ represent the minimum necessary inventory value at the end of period $t \in [|1, T|]$:

$$ \begin{cases} I_T = 0 \\ I_t = \max\{0, I_{t+1} + d_{t+1} - C\}, \quad \forall t \le T \end{cases} $$

Then a solution to the LS-CC-SUB problem is feasible only if $I_t \ge I_{t-1}$, for all periods $t \in [|1, T|]$. It follows that the LS-CC-SUB problem is feasible only if $S_t \ge I_t$ at all periods $t$.

Suppose that at a given period $t$, the demand $d_t$ is greater than the production capacity $C$. Obviously, production at period $t$ is not sufficient to supply the demand in full, and production at previous periods must be stored in prevision of the demand at period $t$. This additional necessary production is represented, at the closest periods previous to $t$, by the maximum possible increase in the demand and a corresponding decrease in the inventory capacity.

Therefore an equivalent instance of the problem may be built as such, with a demand $d'$ and an inventory capacity $S'$ defined by $d'_{t} = \min\{C, d_{t} + I_{t}\}$ and $S'_{t} = S_{t} - I_{t}$, for all periods $t \in [|1, T|]$. In this equivalent problem, the demand $d'$ is obviously lower than the production capacity $C$ at all time. Hence in the following, we always assume the demand to be lower than the production capacity $C$.

### 2.2.3. Assumptions on inventory bounds

Finally, we assume that for any period $t$ there always exists a feasible production plan such that the inventory $I_t$ may attain its upper bound $S_t$. If it is not the case, an equivalent model can be obtained by tightening the inventory bounds.

First, the inventory value cannot exceed the overall inventory obtained from a production at all period while respecting the inventory capacity. Therefore, an equivalent model can be formulated with its inventory capacity $S'$ defined as:

$$ \begin{aligned} S'_{1} &= \min\{S_{1}, I^{0} + C - d_{1}\} \\ S'_{t} &= \min\{S_{t}, S'_{t-1} + C - d_{t}\}, \quad \forall t > 0 \end{aligned} $$

Furthermore, since the supply cannot exceed the sum of demand and inventory capacity, some inventory value upper bounds are unattainable as the inventory would not be sustained in future periods. Therefore, an equivalent model can be formulated with its inventory capacity $S'$ defined as:

$$ S'_{t} = \min\{S_{t}, S'_{t+1} + d_{t+1}\}, \quad \forall t < T $$
Hence we always assume:

$$S_1 \le I^0 + C - d_1 \qquad (10)$$

$$S_t \le S_{t-1} + C - d_t \qquad \forall t > 0 \qquad (11)$$

$$S_t \le S_{t+1} + d_{t+1} \qquad \forall t < T \qquad (12)$$

Inequalities (10)-(12) ensure that at any period $t \in [|1, T|$] and for any inventory value $I_t^* \in [0, S_t]$, a solution to the LS-CC-SUB problem between period $t$ and $T$ with entry stock $I_t^*$ may be found.

## 2.3. Polynomial algorithms for the LS-CC-SUB and the CLSP

We present the concept of subplans as first introduced by Florian and Klein (1971) to solve the CLSP and employed by Wolsey (2005) to design an $O(T^4)$ algorithm for the LS-CC-SUB.

Let $cf(t)$ denote the cost of producing at full capacity at period $t \in [|1, T|$]:

$$cf(t) = s_t + C \cdot c_t, \quad \forall t \in [|1, T|]$$

The production at period $t$ is called fractional if it belongs in $[0, C[$. A subplan denoted $(t_1, t_2, I^1, I^2)$ with $1 \le t_1 \le t_2 \le T$ and $I^1, I^2 \in \{0, 1\}$ is defined as a set of consecutive periods between $t_1$ and $t_2$ with at most one period of fractional production and of entry and ending inventory values $I_{t_1-1} = I^1 \cdot S_{t_1-1}$ and $I_{t_2} = I^2 \cdot S_{t_2}$.

Between any pair of fractional production periods in an optimal schedule, there always exists one period with an inventory value at its lower or upper bound. Hence to obtain an optimal solution to the LS-CC-SUB, it is only necessary to consider feasible solutions that can be subdivided into subplans and choose the best combinations of subplans forming a feasible and optimal solution.

For any subplan $(t_1, t_2, I^1, I^2)$, the production needed for any solution of that subplan to be feasible is:

$$d_{t_1, t_2} + I^2 \cdot S_{t_2} - I^1 \cdot S_{t_1-1} = K \cdot C + f$$

In other words, any feasible solution to that subplan contains a number $K \in \mathbb{N}$ of full production periods and a fractional production period of $f \in [0, C[$ value. If $f = 0$ then it is sufficient to select the $K$ periods of full production needed for the solution to be feasible and optimal.

Suppose the fractional period is fixed to $t_0 \in [|t_1, t_2|]$, then we denote by $P(t_0)$ the problem to determine the corresponding $K$ optimal full production periods. In order to solve the subplan, one has to find for all fractional production periods $t_0 \in [|t_1, t_2|]$ the optimal solution to problem $P$ and select the cheapest solution among them. This can be done in $O(T^2)$ by dynamically solving the associated linear problem (Wolsey, 2005).

Then in order to solve the LS-CC-SUB one must consider every possible subplan $(t_1, t_2, I^1, I^2)$, and for each subplan one must determine the optimal set of full production periods for each possible fractional production period in $[|t_1, t_2|]$. Therefore as there are $O(T^2)$ subplan and each subplan resolution is of $O(T^2)$ complexity, the LS-CC-SUB is of $O(T^4)$ complexity. Our novel $O(T^3)$ algorithm for the LS-CC-SUB derives from the work of van Hoesel and Wagelmans (1993) for the LS-CC without inventory bounds.

Let $P'(t_0)$ denote a relaxation of problem $P(t_0)$, provided that it is possible to have both full and fractional production at period $t_0$. In an initialization procedure for all starting periods $t_1 \in [|1, T|$], the authors dynamically determine a solution to problem $P'$ for the highest possible fractional period $t_0$ of all subplans starting at period $t_1 \in [|1, T|$] by incrementally decreasing the ending period $t_2$ from $T$ to $t_1$. This is done in cubic time. Then for all subplans, the problems $P$ are dynamically solved in linear time by incrementally decreasing the fractional period $t_0$. Indeed at each fractional period $t_0$, it is possible to retrieve in constant time the solution to $P'(t_0)$ from the solution to $P'(t_0+1)$ and then the solution to $P(t_0)$ from the solution to $P'(t_0)$. Hence, their algorithm is of $O(T^3)$ complexity.

It is necessary to account for the time-varying inventory bounds to propose a similar algorithm in our case. First, there must exist for all subplan a fractional production period such that $P'$ is feasible, in order to implement the initialization procedure. Then for any subplan, the set of feasible fractional period for $P'$ must be contiguous so that $P'$ can be solved dynamically by incrementally decreasing the value of the fractional period. Finally for all subplan and all feasible fractional period $t_0$, one must be able to retrieve in constant
time an optimal solution to $P'(t_0)$ from an optimal solution to $P'(t_0 + 1)$, and an optimal solution to $P(t_0)$ from an optimal solution to $P'(t_0)$.

Feasibility criteria for subplans under the previously presented assumptions are proposed in Section 3, while results on the dynamical solving of problem $P'$ and $P$ are introduced in Section 4. Then, those results are leveraged is Section 5 to construct a linear time complexity algorithm to solve any given subplan, building upon the work of van Hoesel and Wagelmans (1993) and accounting for the additional constraints on inventory bounds. Finally, the initialization procedure to solve all subplans is discussed in Section 6. The resulting body of work leads to an $O(T^3)$ time complexity algorithm for the LS-CC-SUB.

### 3. Results on the feasibility of a subplan

Let $(t_1, t_2, I^1, I^2)$ be a feasible subplan with $K$ full production period and a fractional period of non-zero production $f$. Suppose the fractional period is fixed to $t_0 \in [|t_1, t_2|]$. We demonstrate in this section that problems $P(t_0)$ and $P'(t_0)$ are feasible for any fractional period $t_0$ belonging in bounds defined in the following.

First, notice that there can be no fractional production periods as long as production at full capacity is mandatory to respect demand. Thus there are no fractional production period before a period $t_{min}^1$ defined as:

$$t_{min}^1 = \min\{t \in [|t_1, t_2|]; d_{t_1,t} \le (t - t_1) \cdot C + f + I^1 \cdot S_{t_1-1}\} \quad (13)$$

Secondly, there can be no fractional production periods as long as the inventory is not lower than its upper bound despite fractional production. Thus there are no fractional production period before a period $t_{min}^2$ defined as:

$$t_{min}^2 = \min\{t \in [|t_1, t_2|]; (1 - I^1) \cdot S_{t_1-1} + d'_{t_1,t} \ge f\} \quad (14)$$

Moreover, there can be no fractional production period once demand does not exceed anymore the fractional production value as it would result in unused leftover. Thus there are no fractional production period after a period $t_{max}^1$ defined as:

$$t_{max}^1 = \max\{t \in [|t_1, t_2|]; I^2 \cdot S_{t_2} + d_{t_1,t_2} \ge f\} \quad (15)$$

Finally, there can be no fractional production period once the remaining demand cannot be met even with only full production periods afterward. Thus there are no fractional production period after a period $t_{max}^2$ defined as:

$$t_{max}^2 = \max\{t \in [|t_1, t_2|]; d'_{t_1,t_2} \le (t_2 - t) \cdot C + f + (1 - I^2) \cdot S_{t_2}\} \quad (16)$$

Hence the bounds $(t_{min}, t_{max})$ on the value of the fractional production period as necessary conditions for $P$ to be feasible are:

$$t_{min} = \max(t_{min}^1, t_{min}^2)$$

$$t_{max} = \min(t_{max}^1, t_{max}^2)$$

Similar bounds may be found for the problem $P'$ to be feasible. In that case the lower bound defined by $t_{min}^1$ does not represent a necessary condition anymore: since a single time period can be both a fractional and a full production period for the $P'$ problem, the demand can always be satisfied at the fractional production period. For similar reasons, the upper bound $t_{max}^2$ is not necessary either. Hence $P'$ is feasible only if the fractional production period is within bounds $(t'_{min}, t'_{max})$ for $t'_{min} = t_{min}^2$ and $t'_{max} = t_{max}^1$.

We now prove that problems $P$ and $P'$ are feasible if and only if the fractional production period belongs in the respective bounds $(t_{min}, t_{max})$ and $(t'_{min}, t'_{max})$.

**Lemma 1.** Consider a subplan with a storage capacity higher than its constant production capacity at all time. If there are no fractional production and a number of full production period lower than or equal to the number of time period, then that subplan is feasible.

*Proof.* We prove this lemma by induction on the number $K$ of required full production period. First, suppose the subplan requires no full production period nor any fractional production, in other words no production at all, relying only on its starting inventory to satisfy demand and meet the ending inventory constraint. It is obviously feasible.
Suppose now that the lemma is proved for any number lower than $K$ of full production period. Let us prove the lemma is also valid for any subplan $(t_1, t_2, I^1, I^2)$ with a number $K$ of full production period lower than the number of time period in the subplan. First, we derive a useful property from assumptions (10)-(11):

$$S_t \geq I^2 \cdot S_{t_2} + d_{t+1,t_2} - (t_2 - t) \cdot C, \quad \forall t[|t_1, t_2 - 1|] \quad (17)$$

This property guarantees that for any subplan there always exists a sufficient inventory capacity to build the target ending inventory value $I^2 \cdot S_{t_2}$.

Let $t'$ denote the earliest period for which the inventory value in case of full production is below its upper bound:

$$t' = \min\{t \in [|t_1, t_2|]; I^1 \cdot S_{t_1-1} - d_{t_1, t} + C \leq S_t\}$$

If $t' = t_1$, a full production period can be placed in $t_1$, and $K-1$ full production period must be placed in subplan $(t_1+1, t_2, I^1, I^2)$ to build a feasible solution. By induction property, there exists a feasible solution for that subplan since it has one less required production period for one less time period. Thus a feasible solution can be retrieved for subplan $(t_1, t_2, I^1, I^2)$.

Otherwise $t' > t_1$ and the inventory balance in case of full production at time period $t$ lower than $t'$ is higher than $S_t$: $I^1 \cdot S_{t_1-1} - d_{t_1,t} + C > S_t$. It means that in case of no production before $t'$, the inventory value would remain positive, and since $I^1 \cdot S_{t_1-1} \leq S_{t_1-1}$ it would remain below its upper bound as per (10)-(11). By definition of $t'$ one has $I^1 \cdot S_{t_1-1} - d_{t_1,t'-1} + C > S_{t'-1}$. We deduce:

$$I^1 \cdot S_{t_1-1} - d_{t_1,t'} + C > S_{t'-1} - d_{t'} \geq 0 \quad (18)$$

Hence inventory value remains within its bound between $t_1$ and $t'$ in case of full production in $t'$ and none before. The number of full production period to be placed after $t'$ is $K' = K - 1$ such that:

$$K' = \frac{I^2 \cdot S_{t_2} + d_{t'+1,t_2} - (I^1 \cdot S_{t_1-1} - d_{t_1,t'} + C)}{C}$$

Let us prove that the remaining number of full production period $K'$ is lower than or equal to the number of remaining time period $1 + t_2 - t'$. As per inequality (18), one has:

$$K' < \frac{I^2 \cdot S_{t_2} + d_{t'+1,t_2} - (S_{t'-1} - d_{t'})}{C}$$

Then as per inequality (17), one has:

$$K' < (t_2 - t') + \frac{S_{t'} + d_{t'} - S_{t'-1}}{C}$$

Finally as per inequality (11), one has: $K' < (t_2 - t') + 1$.

Hence the number $K'$ of production period to be placed between $t' + 1$ and $t_2$ is lower than or equal to the number of time period $t_2 - t'$. According to the induction property, there exists a feasible solution to a subplan spanning from $t' + 1$ to $t_2$ with entry and ending storage value $I^1 \cdot S_{t_1-1} + C - d_{t_1}$ and $I^2 \cdot S_{t_2}$ from which we can derive a feasible solution to subplan $(t_1, t_2, I^1, I^2)$.

Therefore this proof by induction is completed. □

**Theorem 1.** Consider a subplan with a storage capacity twice higher than its constant production capacity at all time. If that subplan has a number of required production period lower than the number of time period, then the corresponding problem $P$ is feasible for any fractional production period within bounds $(t_{min}, t_{max})$.

*Proof.* Let $t_0$ be the fractional production period of subplan $(t_1, t_2, I^1, I^2)$ within bounds $(t_{min}, t_{max})$.

Consider now a modified subplan without period $t_0$ nor the demand satisfied by the corresponding fractional production. This subplan is obtained as follows from the original subplan $(t_1, t_2, I^1, I^2)$. Let $\tau$ denotes the earliest period after $t_0$ for which the fractional production no longer fully meets the demand. Such a period exists since $t_0$ is lower than or equal to $t_{max}$.
Suppose that $\tau > t_0$. The demand $d'$ of the modified subplan in periods $[t_0, \tau - 1]$ would then be none and in period $\tau$ would correspond to the part of the demand not met by the fractional production, such that:

$$ 
\begin{aligned}
d'_{t} &= 0, & \forall t \in [|t_0, \tau - 1|] \\
d'_{\tau} &= d_{\tau} - (f - d_{t_0, \tau-1})
\end{aligned}
$$

While the demand $d'$ is equal to the original demand $d$ for all other periods. The storage capacity $S'$ of the modified subplan is modified accordingly, since the fractional production in $t_0$ is stored to meet demand for periods in $[|t_0 + 1, \tau|]$. Hence it is defined as:

$$ S'_{t} = S_{t} - (f - d_{t_0,t}), \quad \forall t \in [|t_0, \tau - 1|] $$

While the storage capacity $S'$ is equal to the original storage capacity $S$ for all other periods. Note that in that case, the storage capacity is higher than the production capacity at all time.

Suppose that $\tau = t_0$, then the demand $d'_{t_0}$ is non-zero and of value $d_{t_0} - f$. Hence it must be met by storage constructed from full production in periods preceding $t_0$. In other words, it is possible to displace that demand at the closest previous periods and modify the storage capacity accordingly, while maintaining the demand under the production capacity $C$. Let $\zeta$ denotes the closest period before $t_0$ before which full production is not needed to meet demand in $t_0$. Such a period exists since $t_0$ is higher than or equal to $t_{min}$.

The demand $d'$ of the modified subplan in periods $[\zeta + 1, t_0 - 1]$ would then correspond to the maximum production capacity, would be none in period $t_0$ and correspond in period $\zeta$ to the part of the demand not met by the fractional production, such that:

$$ 
\begin{aligned}
d'_{t_0} &= 0 \\
d'_{t} &= C, \\
d'_{\zeta} &= d_{\zeta} + ((t_0 - \zeta) \cdot C - d_{\zeta,t_0})
\end{aligned}
\quad \forall t \in [|\zeta + 1, t_0 - 1|] $$

While the demand $d'$ is equal to the original demand $d$ for all other periods. The storage capacity $S'$ of the modified subplan is modified accordingly, since the full production in $[|\zeta, t_0 - 1|$] is stored to meet demand in $t_0$. Hence it is defined as:

$$ S'_{t} = S_{t} - ((t + 1 - \zeta) \cdot C - d_{\zeta,t}), \quad \forall t \in [\zeta, t_0 - 1] $$

While the storage capacity $S'$ is equal to the original storage capacity $S$ for all other periods. Note that in that case, the storage capacity is higher than the production capacity at all time.

Thus it is possible to obtain an equivalent subplan to $(t_1, t_2, I^1, I^2)$ with fractional production in $t_0$, such that there is no demand nor production in $t_0$. In other words, that subplan has no fractional production and a number of full production period lower than or equal to the number of time period, with a storage capacity higher than the production capacity at all time. Hence, the modified subplan is feasible and a feasible solution to subplan $(t_1, t_2, I^1, I^2)$ with fractional production in $t_0$ may be retrieved by integrating back the fractional production period and the corresponding demand it satisfies. $\square$

A similar reasoning leads the following property:

**Corollary 1.** Consider a subplan with a storage capacity twice higher than its constant production capacity at all time. If that subplan has a number of required production period lower than the number of time period, then the corresponding problem $P'$ is feasible for any fractional production period within bounds $(t'_{min}, t'_{max})$.

We have proved that problem $P$ and $P'$ are feasible for the fractional production period belonging within bounds $(t_{min}, t_{max})$ and $(t'_{min}, t'_{max})$ respectively. This allows for the design of a dynamical programming scheme to solve the subplan, by iteratively solving $P'$ at each fractional production period and deducing the corresponding solution to $P$ at each step.

## 4. Dynamically retrieving feasible and optimal solutions

let $(t_1, t_2, I^1, I^2)$ be a valid subplan with $K$ full production period and a fractional period of non-zero production $f$. We define properties to efficiently implement a dynamical programming scheme to solve problem $P'$ and $P$ for all fractional production period within bounds $(t_{min}, t_{max})$.
Let the fractional production period $t_0$ be fixed in $[|t_1, t_2|]$, we introduce two functions $A(t)$, $B(t)$ for $t \in [|t_1, t_2|$] that represents respectively the minimum and maximum number of full production periods in $[|t_1, t|]$ for any feasible solution of $P(t_0)$:

$$A(t) = \begin{cases} \left[ \frac{d_{t_1,t}-I^1 \cdot S_{t_1-1}}{C} \right] & \forall t < t_0 \\ \left[ \frac{d_{t_1,t}-f-I^1 \cdot S_{t_1-1}}{C} \right] & \forall t \ge t_0 \end{cases}$$

$$B(t) = \begin{cases} \left[ \frac{S_t+d_{t_1,t}-I^1 \cdot S_{t_1-1}}{C} \right] & \forall t < t_0 \\ \left[ \frac{S_t+d_{t_1,t}-f-I^1 \cdot S_{t_1-1}}{C} \right] & \forall t \ge t_0 \end{cases}$$

Then, the constraints on the lower and upper bounds of the inventory value for a fractional production period in $t_0$ can be expressed as:

$$\sum_{t'=t_1}^{t'=t} z_{t'} \ge A(t) \qquad \forall t \in [|t_1, t_2|]$$

$$\sum_{t'=t_1}^{t'=t} z_{t'} \le B(t) \qquad \forall t \in [|t_1, t_2|]$$

A solution of $P(t_0)$ is feasible if and only if for any $t \in [|t_1, t_2|$] the number of full production periods in $[|t_1, t|]$ is at least $A(t)$ and at most $B(t)$. Functions $A$ and $B$ are integral, non-decreasing except on period $t_0$ as per inequality (12).

For all $k \in [|1, K|]$, let $w_k$, $\bar{w}_k \in [|t_1, t_2|$] respectively be the lower and upper bound for the k-th period of production. They are defined as follow:

$$\underline{w}_k = \max\{t_1\} \cup \{t \in [|t_1+1, t_2|]; B(t-1) \le k-1\} \qquad \forall k \in [|1, K|]$$

$$\bar{w}_k = \min\{t \in [|t_1, t_2|]; A(t) = k\} \qquad \forall k \in [|1, K|]$$

We introduce for all $k \in [|1, K|]$ the parameter $t^k \in [|1, T|$] representing the chosen k-th period of full production. Then a solution of $P(t_0)$ is feasible if and only if:

$$t^k \in [|\underline{w}_k, \bar{w}_k|] \qquad \forall k \in [|1, K|]$$

$$t^k > t^{k-1} \qquad \forall k \in [|2, K|]$$

$$t^k \neq t_0 \qquad \forall k \in [|1, K|]$$

Interval $[|\underline{w}_k, \bar{w}_k|$] represents the window of available production for the k-th period of full production.

One may notice that the value of lower and upper bounds $\underline{w}_k$ and $\bar{w}_k$ for all full production periods $k \le K$ increase when displacing the fractional production period from $t_0 + 1$ to $t_0$. Indeed, an early fractional production period means less restriction to meet the demand but an inventory value closer to its maximum capacity, hence the latest and earliest time to place the k-th full production period increase.

First, we define conditions to retrieve an optimal solution to problem $P(t_0)$ from the optimal solution to problem $P'(t_0)$, for any fractional period $t_0 \in [|t_{min}, t_{max}|]$.

**Theorem 2.** Let $(t_1, t_2, I^1, I^2)$ be a feasible subplan and $t_0 \in [|t_{min}, t_{max}|]$ a candidate fractional production period. An optimal solution to problem $P(t_0)$ may be found from an optimal solution to problem $P'(t_0)$ by moving full production in $t_0$, if any, to the cheapest available period.

*Proof.* We prove this theorem by induction on the number $K$ of required full production periods. Suppose there are no required full production periods, in other words $K = 0$. Then there is no full production period and the optimal solution to problem $P(t_0)$ is identical to the solution of $P'(t_0)$.

Suppose now that the theorem is verified for any feasible subplan with at most $K-1$ full production periods. If the optimal solution to $P'(t_0)$ has no full production at period $t_0$, then it is obviously also an optimal solution to $P(t_0)$. Otherwise, we suppose that the $k_0$-th full production period $t^{k_0}$ is equal to $t_0$, and must be moved to another period available for production in order to obtain a feasible solution to $P(t_0)$. Obviously, it can be moved inside its own window of production $\{\underline{w}_{k_0}, \dots, \bar{w}_{k_0}\}$ after (resp. before) the $t^{k_0-1}$ (resp. $t^{k_0+1}$).
In this way, it remains the $k_0$-th production period. However, if it is moved beyond $t^{k_0+1}$, it is inverted with the $(k_0 + 1)$-th production period, which in turn becomes the $k_0$-th one, as shown in Figures 1 and 2.

<figure><img src="image_2.png" /><figcaption>Figure 1: Example before inversion</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>Figure 2: Example after inversion</figcaption></figure>

This is only possible if $t^{k_0+1}$ originally belongs in $\{\underline{w}_{k_0}, \dots, \bar{w}_{k_0}\}$. The same reasoning applies when inverting the $t^{k_0}$ and $t^{k_0-1}$. By successive inversions, it is possible to extend the set of available candidate periods until a production period outside the current production window is encountered.

Let us denote by $k^+$ the smallest index $k > k_0$ of full production for which the associated period $t^k$ is strictly higher than the upper bound $\bar{w}_{k-1}$ of the previous full production. If such index does not exist, it is given the value $K + 1$ with $t^{K+1} = t_2$. It is defined as:

$$k^+ = \min \{ \{k \in [|k_0, K-1|]; t^{k+1} > \bar{w}_k\} \cup \{K+1\} \}$$

Similarly, let us denote by $k^-$ the greatest index $k < k_0$ of full production for which the associated period $t^k$ is strictly lower than the lower bound $\underline{w}_{k+1}$ of the next full production. If such index does not exist, it is given the value 0 with $t^0 = t_1$. It is defined as:

$$k^- = \max \{ \{k \in [|2, k_0|]; t^{k-1} < \underline{w}_k\} \cup \{0\} \}$$

Suppose that there are no available period of production in interval $[|\underline{w}_{k-}, \bar{w}_{k+}|]$, then problem $P(t_0)$ is unfeasible since no full production period in $[|\underline{w}_{k-}, \bar{w}_{k+}|]$ can be placed outside of that interval. This is absurd as per Theorem 1, hence there always exists an available period in $[|\underline{w}_{k-}, \bar{w}_{k+}|]$.

If $k^+ = K + 1$ and $k^- = 0$, the full production period in $t_0$ may be moved to any available period in $[|\underline{w}_1, \bar{w}_K|]$, while there cannot be any full production period outside that window. Remember that all other full production periods are optimally placed for problem $P'(t_0)$, and changing their position would not extend the set of available period for the $k_0$-th production period. Hence only one production move from $t_0$ to the cheapest available period in $[|\underline{w}_1, \bar{w}_K|]$ is required to find an optimal solution to $P(t_0)$. The theorem is verified in that case.

Otherwise, the set of candidate available periods could be further extended, by first moving the $(k^+ + 1)$-th (resp. $(k^- - 1)$-th) period in the production window of the $k^+$-th (resp. $(k^-)$-th) period. However that would not improve the solution since the choices of full production periods in intervals $[|t_1, \underline{w}_{k-} - 1|]$ and $[|\bar{w}_{k+} + 1, t_2|]$ are already optimal. Because of this optimality, the $k_0$-th period if moved takes the position of the $(k^+ + 1)$-th (resp. $(k^- - 1)$-th) period, while this latter period is moved to the cheapest period in the set of available periods. It is equivalent to move directly the full production to the cheapest period in its set of available periods. Such equivalence is illustrated below in Figures 3 and 4.

<figure><img src="image_4.png" /><figcaption>Figure 3: Example of an optimal move</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Figure 4: Example of an equivalent optimal move</figcaption></figure>
Problem $P(t_0)$ is then solved by restricting our study to the feasible subplan spanning from $w_{k-}$ to $\bar{w}_{k+}$ with at most $K-1$ full production periods. Hence the theorem is verified by induction. $\square$

We now define conditions to retrieve an optimal solution to problem $P'(t_0)$ from the optimal solution to problem $P'(t_0+1)$, for any fractional production period $t_0 \in [|t'_{min}, t'_{max} - 1|$].

**Theorem 3.** Let $(t_1, t_2, I^1, I^2)$ be a feasible subplan and $t_0 \in [|t'_{min}, t'_{max} - 1|$] a candidate fractional production period. An optimal solution to $P'(t_0)$ can be deduced from an optimal solution to $P'(t_0+1)$ by moving at most one production period from $[[t_1, t_0]]$ to $[[t_0 + 1, t_2]]$.

*Proof.* The values of $A$ and $B$ in $\{t_1, \dots, t_2\}$ remain identical when decreasing the fractional production period from $t_0+1$ to $t_0$, except at period $t_0$ where they might decrease. Consequently, at most one period $k_1$ (resp. $k_2$) of full production sees a lower (resp. upper) bound increase. Hence, the $k_1$-th production period could be moved to a cheaper period beyond its previous upper bound, and the $k_2$-th production period may have to be moved for feasibility purpose beyond its new lower bound.

The values of $A$ remains constant everywhere except on period $t_0$ when displacing the fractional production period from $t_0+1$ to $t_0$. The upper bound $\bar{w}_{k_1}$ may only increase if one had $A(t_0) = k_1$ in $P'(t_0+1)$ and $A(t_0) < k_1$ in $P'(t_0)$. Since there are no other changes in value of $A$, only the upper bound for period $k_1$ increases from a value in $[[t_1, t_0]]$ to a value in $[[t_0+1, t_2]]$. Hence it is possible to move that production period to a cheaper available period beyond $t_0+1$.

Similarly, the values of $B$ remains constant everywhere except on period $t_0$, and $B(t_0)$ may only decrease by 1 when displacing the fractional production period from $t_0+1$ to $t_0$. Hence $w_{k_2}$ may only increase if one had $B(t_0) = k_2$ in $P'(t_0+1)$ and $B(t_0) = k_2 - 1$ in $P'(t_0)$. Since there are no other changes in value of $B$, only the lower bound for period $k_2$ increases from a value in $[[t_1, t_0]]$ to the value $t_0+1$. Hence it is necessary to move that production period to an available period beyond $t_0+1$.

If there is only a change in bounds value for $k_1$ or $k_2$ but not for both, then there is only one production move at most from $[[t_1, t_0]]$ to $[[t_0+1, t_2]]$ and the proof is concluded. Otherwise if there is a change in bounds value both for $k_1$ and $k_2$, then either $t^{k_2} > t_0$ or the $k_2$-th production period must be moved for feasibility purpose. Notice that $k_1 < k_2$ since $w_{k_1} \le t_0 < w_{k_2}$. Hence in the case where $t^{k_2} \le t_0$, we have $t^{k_2} \in [|w_{k_1}, \bar{w}_{k_1}]$. Then by using inversion as shown in the proof of Theorem 2, the $k_1$-th and $k_2$-th production periods may be moved to the same set of available periods in $[[t_0+1, t_2]]$. According to arguments of the same proof as per Corollary 1, such a set is non-empty.

Since the current solution is optimal for $P'(t_0+1)$ and only the previously mentioned bounds have changed, the current period $t^{k_2}$ is cheaper than any feasible available period beyond $t_0$. Hence for feasibility and optimality purpose, only one of those two periods must be moved beyond $t_0$. Such a move can be done by successive inversions, hence only one production move from $[[t_1, t_0]]$ to $[[t_0+1, t_2]]$ is required to identify a feasible and optimal solution to problem $P'(t_0)$ from the optimal solution to problem $P'(t_0+1)$. $\square$

We are now able to implement an efficient dynamic resolution of a feasible subplan. Suppose the latest fractional period $t_{max}$ is known, as well as an optimal solution to the problem $P'(t_{max})$. Then it is possible to iteratively solve problems $P'$ and $P$ for all fractional production period within bounds $(t_{min}, t_{max})$, by moving at most two full production periods at each step.

## 5. Dynamic resolution of a subplan for the LS-CC-SUB

Let us consider a feasible subplan $(t_1, t_2, I^1, I^2)$. Suppose the upper bound $t'_{max}$ of the fractional production period for problem $P'$ is known, as well as an optimal solution to the problem $P'(t'_{max})$. By building upon the work of van Hoesel and Wagelmans (1993) for the unbounded problem, we propose an $O(T)$ algorithm to find the optimal solution to all problems $P'(t_0)$ and $P(t_0)$ for a fractional period $t_0$ in $[[t_{min}, t_{max}]]$. While the algorithmic developments to achieve optimality are close to the work of van Hoesel and Wagelmans (1993), significant efforts are made to also ensure feasibility due to the added constraint on inventory bounds of the studied problem.

Suppose that for a fractional production period $t_0 \in [|t_{min}, t'_{max} - 1|]$, an optimal solution to $P'(t_0+1)$ is known. In order to solve problem $P'(t_0)$, the fractional production period is first moved from $t_0+1$ to
$t_0$, while all full production periods remain the same. Consequently, $I_{t_0}$ increases by $f$ units. Then as per Theorem 3, an optimal solution to problem $P'(t_0)$ can be retrieved from the current solution with at most one move of full production from $[[t_1, t_0]]$ to $[[t_0 + 1, t_2]]$. Afterward and as per theorem 2, an optimal solution to problem $P(t_0)$ can be retrieved from the current solution by moving full production in $t_0$, if any, to the cheapest available period.

## 5.1. Dynamic resolution of the $P'$ problem

As per Theorem 3, a feasible and optimal solution to problem $P'(t_0)$ can be deduced from the one of problem $P'(t_0 + 1)$ with at most one move of full production from $[[t_1, t_0]]$ to $[[t_0 + 1, t_2]]$.

For all fractional production period $t_0$ and a solution $x$ to problem $P'(t_0)$ with a corresponding inventory value $I$, let $u^{t_0}$ and $s^{t_0}$ be the parameters defined as follows:

* Period $u^{t_0}$ is the earliest period in $[[t_0, t_2]]$ such that the inventory value is below the production capacity:

$$u^{t_0} = \min\{t \in [[t_0, t_2]]; I_t < C\} \cup \{t_2\}$$

* Period $s^{t_0}$ is the earliest period such that all following inventory values in $[[t_1, t_0]]$ are above the production capacity:

$$s^{t_0} = \max\{t_1\} \cup \{t \in [[t_1 + 1, t_0]]; I_{t-1} < C\}$$

Similarly, let $\delta^{t_0}$ and $\gamma^{t_0}$ be the parameters defined as follows:

* Period $\delta^{t_0}$ is the earliest and cheapest period in $[[t_0, u]]$ of available full production:

$$\delta^{t_0} = \arg\min\{cf(t'); x_{t'} = 0, t' \in [[t_0 + 1, u]]\}$$

* Period $\gamma_r^{t_0}$ is the most expensive production period in $[[s, r]]$, for all $r \in [[s, t_0]]$:

$$\gamma_r^{t_0} = \arg\max\{cf(t'); x_{t'} = 1, t' \in [[s, r]]\}, \quad \forall r \in [[s, t_0]]$$

Suppose that an optimal solution to problem $P'(t_0 + 1)$ is known, as well as parameters ($u^{t_0}$, $s^{t_0}$, $\delta^{t_0}$, $\gamma^{t_0}$) for the corresponding optimal solution to $P'(t_0 + 1)$. A feasible and optimal solution to problem $P'(t_0)$ may be retrieved from that solution to $P'(t_0 + 1)$ by moving production forward in time. Note that moving production forward in time decreases the inventory value $I$ on all intermediate periods by $C$. Hence feasibility conditions impose that any move of production forward in time must be from $[[s^{t_0}, t_0]]$ to $[[t_0 + 1, u^{t_0}}]$.

An optimal solution to $P'(t_0)$ may be retrieved by moving a the most expensive production period in $[[s^{t_0}, t_0]]$, indicated by $\gamma_r^{t_0}$, to the cheapest available in $[[t_0 + 1, u^{t_0}}]$ indicated by $\delta^{t_0}$. If $I_{t_0} \le S_{t_0}$ then the current solution for $P'(t_0)$ is already feasible, and this move is done only if it results in a cheaper production plan, i.e. if $cf(\gamma_{t_0}^{t_0}) > cf(\delta^{t_0})$. In the contrary if $I_{t_0} > S_{t_0}$, the current solution for $P'(t_0)$ is not feasible and that move must be done regardless to obtain a feasible and optimal solution.

An optimal solution to problem $P'$ may be dynamically found for all fractional production periods bounded by $(t'_{min}, t'_{max})$ from the knowledge of an optimal solution to problem $P'(t_{max})$. Finding an optimal solution to all problem $P'$ takes at most $t'_{max} - t'_{min}$ full production moves in total, in other words the number of required moves increase linearly with the number of periods in the subplan. However parameters $(u, s, \delta, \gamma)$ also have to be dynamically updated in constant time at each step of the dynamical process in order for the algorithm to be of linear complexity. The following algorithm represent all the related update operations.
**Algorithm 1** Update of (x, I) and (u, s, δ, γ)

**Input:** Fractional period $t_0$, Optimal solution $(x, I)$ to $P'(t_0 + 1)$, Parameters $(u, s, \delta, \gamma)$

1: $x_{t_0} \leftarrow x_{t_0} + f$

2: $x_{t_0+1} \leftarrow x_{t_0+1} - f$

3: $I_{t_0} \leftarrow I_{t_0} + f$

4: **if** $I_{t_0} < C$ **then**

5:     $u \leftarrow t_0$

6:     $\delta \leftarrow 0$

7:     **else if** $x_{t_0+1} = 0$ **and** ($\delta = 0$ or $cf(t_0 + 1) < cf(\delta)$) **then**

8:         $\delta \leftarrow t_0 + 1$

9:     **end if**

10: **if** $t_0 = s - 1$ **then**

11:         $s \leftarrow \max\{t_1\} \cup \{t' \in [|t_1 + 1, t|]; I_{t'-1} < C\}$

12:         $\gamma_r \leftarrow \arg\max\{cf(t'); x_{t'} = 1, t' \in [|s, r|]\}, \quad \forall r \in [|s, t_0|$

13: **end if**

14: **return** $(x, I, u, s, \delta, \gamma)$

Note that the update of $u$ and $\delta$ is done in constant time, while the overall successive computation of $s$ and $\gamma$ across the iterations is done in linear time (van Hoesel and Wagelmans, 1993). Therefore all operations to obtain parameters $(u, s, \delta, \gamma)$ at fractional period $t_0$ from those at fractional period $t_0 + 1$ for a known optimal solution to problem $P'(t_0 + 1)$ is done in linear time.

We now prove that updating parameters $(u^{t_0}, t_0 s, \delta^{t_0}, \gamma^{t_0})$ when a full production period is moved can be done in constant time. Such a result is proven to be true for the case without inventory bounds by van Hoesel and Wagelmans (1993). We extend it to the case with inventory bounds.

**Lemma 2.** Suppose that an optimal solution to problem $P'(t_0+1)$ is known, as well as parameters $(u^{t_0}, s^{t_0}, \delta^{t_0}, \gamma^{t_0})$ for the corresponding optimal solution to $P'(t_0 + 1)$. If production is moved, then $u^{t_0}$ and $\delta^{t_0}$ takes the value $t_0$.

*Proof.* Remember that a full production period may only be moved from period $\gamma_{t_0}^{t_0}$ to period $\delta^{t_0}$.

If that move is profitable, then $u$ is updated to $t_0$ because we must have $I_{t_0} < C + f$ in the initial solution to $P'(t_0)$, otherwise that move would have been feasible and profitable in $P'(t_0 + 1)$ (van Hoesel and Wagelmans, 1993).

If that move is not profitable and is made because the inherited solution is unfeasible, it means all production periods in $[|s, t_0|]$ are cheaper than any available periods in $[|t_0 + 1, u|]$. Moving forward a production period from $\gamma_{t_0}$ to $\delta$ ensures that the solution remains feasible for any fractional production period in $[|\gamma_{t_0}, t_0|]$ since it increases $J$ by $C$ on interval $[|\gamma_{t_0} + 1, t_0|]$. Therefore, once such a non-profitable feasibility move is made, only optimality moves are considered for the fractional period $t'_0$ in that interval $[|\gamma_{t_0}, t_0 - 1|]$, and from cheaper production period since $\gamma_{t_0}$ was the most expensive.

Since all available period in $[|t_0, u|]$ are also more expensive than $\gamma_{t_0}$ and period $u$ decreases when the fractional production decreases, any profitable move for $t'_0 \in [|\gamma_{t_0}, t_0 - 1|]$ must be targeting an available period lower than $t_0$. Finally since there are no feasibility move for fractional production in $[|\gamma_{t_0}, t_0 - 1|]$, any move for $t'_0 \in [|\gamma_{t_0}, t_0 - 1|]$ must be targeting an available period lower than $t_0$.

Since $\gamma_{t_0}$ is an available period after the feasible move from $\gamma_{t_0}$ to $\delta$, the cheapest available period in $[|\gamma_{t_0-1}, u|]$ is lower than $t_0$. Hence any feasibility or optimality move to find an optimal solution to problem $P'$ for the fractional period in interval $[|t_{min}, \gamma_{t_0-1}|]$ would target that cheapest available period lower than $[t_0$. If it is an optimality move, $u$ is updated to the current fractional period. Otherwise if it is a non-profitable feasibility move, the same reasoning can be applied once again until an optimality move is made or the last iteration is attained.

Therefore by induction, $u^{t_0}$ always takes the value $t_0$ if a full production period is moved to retrieve an optimal solution to problem $P'(t_0)$. Hence $\delta^{t_0}$ also takes the value $t_0$ in that case. $\square$
We have proved parameters $u$ and $\delta$ are updated in constant time after a production move. We now propose a property that leads to a similar observation for parameters $s$ and $\gamma$. Such a result is proven to be true for the case without inventory bounds by van Hoesel and Wagelmans (1993). We extend it to the case with inventory bounds.

**Lemma 3.** Suppose that an optimal solution to problem $P'(t_0+1)$ is known, as well as parameters ($u^{t_0}$, $s^{t_0}$, $\delta^{t_0}$, $\gamma^{t_0}$) for the corresponding optimal solution to $P'(t_0+1)$. If production is moved to solve $P'(t_0)$, then the resulting optimal solution is also optimal for all problems $P'(t)$ such that $t \in [[\gamma_{t_0}^{t_0}, t_0]]$.

*Proof.* If production has been moved for optimality purpose, there are no further optimality move for any $P'$ problem until fractional production in $s-1$ is reached (van Hoesel and Wagelmans, 1993). Moreover there are no feasibility move until fractional production reaches $\gamma_{t_0}-1$ since all $J$ values on interval $[[\gamma_{t_0}+1, t_0]]$ are increased by $C$. Hence the lemma is verified in case of an optimality move of full production.

Otherwise, if production has been moved for non-profitable feasibility, there are no further feasibility move until fractional production in $\gamma_{t_0}-1$ is reached since all inventory values $I$ on interval $[[\gamma_{t_0}+1, t_0]]$ are decreased by $C$. We prove in what follows that there are no optimality move either until fractional production in $\gamma_{t_0}-1$ is reached.

The non-profitable feasibility move has to be from the period $\gamma_{t_0}^{t_0}$ to the more expensive period $\delta^{t_0}$. Suppose now that after that move, there exists a fractional period $t'_0 \in [[\gamma_{t_0}^{t_0}, t_0-1]]$ such that $\gamma_{t'_0}^{t'_0}$ is more expensive than $\delta^{t'_0}$. Obviously one has $\delta^{t'_0} \le t_0$, otherwise there would have existed a profitable feasibility move instead of the non-profitable one.

Note that the inventory value of the optimal solution to problem $P'(t_0+1)$ between period $\gamma_{t_0}^{t_0}$ and $t_0$ was higher than $C$, since the non-profitable feasibility move that followed did not cause unfeasibility. Therefore there was the possibility of a profitable full production move from $\gamma_{t'_0}^{t'_0}$ to $\delta^{t'_0}$. Such a move did not happen, despite considering the solution to $P'(t_0+1)$ as optimal, which is absurd.

Therefore such fractional period $t'_0$ does not exist. Hence in case of a non-profitable feasibility move at fractional period $t_0$, there cannot be an optimal move until fractional period reaches value $\gamma_{t_0}^{t_0}-1$.

We conclude than when production has been moved, there are no further move until fractional production in $\gamma_{t_0}-1$ is reached. $\square$

We have proved that after a production move from period $\gamma_{t_0}^{t_0}$ to period $\delta^{t_0}$, there are no further production move for the fractional production period in $[[\gamma_{t_0}^{t_0}, t_0]]$. Hence there is no need to update the parameters $s$ and $\gamma$ on those intervals.

Moreover note that, after that move, the inventory values in interval $[[s^{t_0}, \gamma_{t_0}^{t_0}-1]]$ do not change. In other words, we have for all period $t \in [[s^{t_0}, \gamma_{t_0}^{t_0}-1]]$, the values $s^t$ and $\gamma^t$ that remain identical to $s^{t_0}$ and $\gamma^{t_0}$, at the exception of $\gamma_{t_0}^t$ which takes the value $\gamma_{t_0-1}^t$ since there are no full production at period $\gamma_{t_0}^{t_0}$ anymore.

Hence, we have proved parameters $s$ and $\gamma$ are updated in constant time after a production move.

By leveraging all previous observations, we propose a linear-time algorithm to solve all problem $P'$ from the initial knowledge of the optimal solution to problem $P'(t'_{max})$.
**Algorithm 2** Dynamic resolution of the P' problems

**Input:** Subplan $(t_1, t_2, I^1, I^2)$, bounds $(t'_{min}, t'_{max})$, optimal solution $(x, I)$ to $P'(t'_{max})$

1: $t_0 \leftarrow t'_{max}$

2: Initialization of $u, \delta, s, \gamma$ for the current fractional period $t_0$

3: OptMove $\leftarrow$ "Yes"

4: **while** $t_0 > t'_{min}$ **do**

5: $t_0 \leftarrow t_0 - 1$

6: Update $(x, I, u, s, \delta, \gamma)$ with Algorithm 1

7: **if** $t_0 < s$ **then**

8: OptMove $\leftarrow$ "Yes"

9: **end if**

10: **if** (OptMove = "Yes" and $cf(\gamma_{t_0}) > cf(\delta)$) or $I_{t_0} > S_{t_0}$ **then**

11: $x_{\gamma_{t_0}} \leftarrow x_{\gamma_{t_0}} - C$

12: $x_{\delta} \leftarrow x_{\delta} + C$

13: **for** $t' \in [|\gamma_{t_0}, t_0|$] **do**

14: $I_{t'} \leftarrow I_{t'} - C$

15: **end for**

16: $u \leftarrow t_0$

17: **if** $cf(\gamma_{t_0}) \le cf(\delta)$ **then**

18: $\gamma_{\gamma_{t_0}} \leftarrow \gamma_{\gamma_{t_0}-1}$

19: **else**

20: OptMove $\leftarrow$ "No"

21: **end if**

22: $\delta \leftarrow t_0$ if $x_{t_0} = 0$ otherwise $\delta \leftarrow 0$

23: **end if**

24: Current plan of production $x$ is an optimal solution to problem $P'(t_0)$

25: **end while**

26: **return** Solutions

This algorithm is almost identical to the one proposed by van Hoesel and Wagelmans (1993), except for the management of the feasibility production move. Our contributions are highlighted by Lemmas 2 and 3, proving that this algorithm can be applied with minor changes to the case with inventory bounds.

Beside the update of $I$ and $J$ after each production move, it only requires additional operations of constant-time complexity in the while-loop. As for the update of $I$, it corresponds to an enumeration of all period from $\gamma_{t_0}$ to $t_0$. As per Lemma 3, there is no other production move until the fractional production period is of value $\gamma_{t_0}$. Hence throughout the iterations, the update of $I$ enumerates at most once all periods in $[[t_1, t_2]]$, and Algorithm 2 is of linear complexity.

## 5.2. Retrieving the optimal solution of the P problem

Let $t_0$ be the current fractional production period, and $q^{t_0}$ and $\eta^{t_0}$ be the parameters defined as follows:

* Period $q^{t_0}$ is the latest period in $[[t_1, t_0]]$ such that the remaining storage capacity is below the production capacity:

$$q^{t_0} = \max\{t_1\} \cup \{t; t \in [[t_1+1, t_0]], S_{t-1} - I_{t-1} < C\}$$

* Period $\eta^{t_0}_{q,v}$ is the earliest and cheapest period in $[[q, v]]$ of available full production, for all $v \in [[q, t_0]]$:

$$\eta^{t_0}_{q,v} = \arg\min\{cf(t'); x_{t'} = 0, t' \in [[q, v]]\}, \quad \forall v \in [[q, t_0]]$$

In order to find an optimal solution to $P(t_0)$ from the optimal solution to $P'(t_0)$, it is sufficient to move the full production in $t_0$, if any, to the cheapest available period as per theorem 2. That cheapest available period is indicated by parameter $\zeta = \arg\min\{cf(\eta_{q,t_0-1}), cf(\delta)\}$ for the current solution to problem $P'(t_0)$.

If parameter $q$ is known for problem $P'(t_0+1)$, then it can be determined for problem $P'(t_0)$ as follows. Since full production periods are only moved forward in time, the value of $J_t$ for $t < t_0$ does not decrease. Hence $q$
needs only to be updated if $q = t_0 + 1$, by finding the latest period $t \in [|t_1, t_0|$] such that $S_{t-1} - I_{t-1} < C$. Therefore, re-evaluating all values of $\eta$ and updating $q$ is only necessary when the current value of $q$ drops below the fractional period $t_0$.

However, the value of $q$ may change when a full production period is moved forward in time, as it may be the case when determining the optimal solution to problem $P'(t_0)$ from the optimal solution to problem $P'(t_0+1)$ by moving a production period from $\gamma_{t_0}$ to $\delta$. Hence, the values of $q$ and $\eta_q$ must also be updated in that case, and again in linear complexity. First, if $\gamma_{t_0} > q$ then period $\gamma_{t_0}$ becomes a candidate cheapest available period after the full production is moved. Therefore $\eta_q$ must be updated accordingly with the following algorithm.

<caption>**Algorithm 3** Update of $\eta_q$ after a production move</caption>

**Input:** Fractional period $t_0$, Parameters $(\gamma_{t_0}, q, \eta_q)$
1: **if** $q \le \gamma_{t_0}$ **then**
2:   **for** $t \in [|\gamma_{t_0}, t_0|$] **do**
3:     **if** $\eta_{q,t_0} = 0$ **or** $cf(\eta_{q,t_0}) > cf(\gamma_{t_0})$ **then**
4:       $\eta_{q,t_0} \leftarrow \gamma_{t_0}$
5:     **end if**
6:   **end for**
7: **end if**
8: **return** $\eta_q$

Then, one must also consider that when a full production period is moved forward in time from $\gamma_{t_0}$ to $\delta$, then the inventory value $I$ for $t \in [|\gamma_{t_0}, \delta - 1|$] decreases by $C$. Hence the value of $q$ may decrease. In order to preserve the linear complexity, we introduce a parameter $q'$ initialized to $q' = q$. That parameter $q'$ and $\eta_{q'}$ are updated as follows after a full production period is moved:

<caption>**Algorithm 4** Update of $q', \eta_{q'}$ after a production move</caption>

**Input:** Fractional period $t_0$, Parameters $(\gamma_{t_0}, q, q', \eta_{q'})$
1: $q' \leftarrow \min(q, \gamma_{t_0})$
2: $\eta_{q',v} \leftarrow \arg\min\{cf(t'); x_{t'} = 0, t' \in [|q', v|]\}, \forall v \in [|q', q|]$

Notice that the optimal period $\zeta$ to which a full production period is moved in order to retrieve the optimal solution to $P(t_0)$ may be determined such that $\zeta \leftarrow \arg\min\{cf(\eta_{q',q}), cf(\eta_{q,t_0-1}), cf(\delta)\}$. Finally, we demonstrate how to efficiently update parameters $q$ and $\eta$ at fractional period $t_0$ from those at fractional period $t_0 + 1$ for a known optimal solution to problem $P'(t_0 + 1)$. The following algorithm represents all the related update operations.

<caption>**Algorithm 5** Update of $q, q'$ and $\eta$</caption>

**Input:** Fractional period $t_0$, Current solution $(x, I)$, Parameters $(u, q, \eta)$
1: **if** $q = t + 1$ **then**
2:   $q \leftarrow \max\{t_1\} \cup \{t'; t' \in [|t_1 + 1, t_0|], S_{t'-1} - I_{t'-1} < C\}$
3:   $\eta_{q,v} \leftarrow \arg\min\{cf(t'); x_{t'} = 0, t' \in [|q, v|]\}, \forall v \in [|q, t_0|]$

Using all previously constructed algorithm and building upon Algorithm 2, we propose the following algorithm solving the subplan. It enumerates all feasible fractional production period, solving at each iteration the problem $P'$ and deducing the corresponding to problem $P$. Note it requires as input the knowledge of an initial optimal solution to problem $P'(t'_{max})$ which is discussed in section 6.
<caption>**Algorithm 6** Dynamic resolution of the subplan problem</caption>

**Input:** Subplan $(t_1, t_2, I^1, I^2)$, bounds $(t_{min}, t_{max})$, optimal solution $(x, I)$ to $P'(t'_{max})$
1: $t_0 \leftarrow t_{max}$
2: Initialization of $u, \delta, q, \eta, s, \gamma, q'$ for the current fractional period $t_0$
3: OptMove $\leftarrow$ "Yes"
4: **while** $t_0 > t_{min}$ **do**
5: &nbsp;&nbsp;&nbsp;&nbsp;$t_0 \leftarrow t_0 - 1$
6: &nbsp;&nbsp;&nbsp;&nbsp;Update $(x, I, u, s, \delta, \gamma)$ with Algorithm 1
7: &nbsp;&nbsp;&nbsp;&nbsp;Update $(q, q', \eta)$ with Algorithm 5
8: &nbsp;&nbsp;&nbsp;&nbsp;**if** $t_0 < s$ **then**
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;OptMove $\leftarrow$ "Yes"
10: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
11: &nbsp;&nbsp;&nbsp;&nbsp;**if** (OptMove = "Yes" and $cf(\gamma_{t_0}) > cf(\delta)$) or $I_{t_0} > S_{t_0}$ **then**
12: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$x_{\gamma_{t_0}} \leftarrow x_{\gamma_{t_0}} - C$
13: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$x_{\delta} \leftarrow x_{\delta} + C$
14: &nbsp;&nbsp;&nbsp;&nbsp;**for** $t' \in [[\gamma_{t_0}, t_0]]$ **do**
15: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$I_{t'} \leftarrow I_{t'} - C$
16: &nbsp;&nbsp;&nbsp;&nbsp;**end for**
17: &nbsp;&nbsp;&nbsp;&nbsp;Update $\eta_q$ with Algorithm 3
18: &nbsp;&nbsp;&nbsp;&nbsp;Update $(q', \eta_{q'})$ with Algorithm 4
19: &nbsp;&nbsp;&nbsp;&nbsp;$u \leftarrow t_0$
20: &nbsp;&nbsp;&nbsp;&nbsp;**if** $cf(\gamma_{t_0}) \le cf(\delta)$ **then**
21: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\gamma_{\gamma_{t_0}} \leftarrow \gamma_{\gamma_{t_0}} - 1$
22: &nbsp;&nbsp;&nbsp;&nbsp;**else**
23: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;OptMove $\leftarrow$ "No"
24: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
25: &nbsp;&nbsp;&nbsp;&nbsp;$\delta \leftarrow t_0$ if $x_{t_0} = 0$ otherwise $\delta \leftarrow 0$
26: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
27: &nbsp;&nbsp;&nbsp;&nbsp;**if** Full production in period $t_0$ **then**
28: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\zeta \leftarrow \arg\min\{cf(\eta_{q'}, q), cf(\eta_{q, t_0-1}), cf(\delta)\}$
29: &nbsp;&nbsp;&nbsp;&nbsp;Determine solution to $P(t_0)$ by moving full production from $t_0$ to $\zeta$
30: &nbsp;&nbsp;&nbsp;&nbsp;**else**
31: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;The solution to $P(t_0)$ is equivalent to the solution to $P'(t_0)$
32: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
33: &nbsp;&nbsp;&nbsp;&nbsp;**end while**
34: **return** Solutions

The presented algorithm builds upon algorithm 2 and is an original extension of the work of van Hoesel and Wagelmans (1993), with an added consideration of parameters $q$ and $\eta$ to retrieve the optimal solution of problem $P$ throughout the enumeration of all fractional production periods. Beside the call to algorithms 5, 3 and 4, all added operations are done in constant-time complexity.

Algorithm 5 is only called when the current value of parameter $q$ is equal to $t+1$, for $t$ the fractional production period enumerated from $t_{max}$ to $t_{min}$. The new value of $q$ is then evaluated by enumerating period from the current period $t$ to $t_1$ and stopping at the first period $t'$ such that $S_{t'-1} - I_{t'-1} < C$. Similarly, $\eta_q$ is updated by an enumeration of periods from $t$ to the new value of $q$. Hence the successive update of $q$ and $\eta_q$ only requires to enumerate all periods from $t_2$ to $t_1$ throughout the iterations, and is done in linear time.

Remember that according to Lemma 3, after production is moved from period $\gamma_{t_0}^{t_0}$ to period $\delta^{t_0}$, there are no further production to be moved to solve problem $P'$ for the fractional production period in $[[\gamma_{t_0}^{t_0}, t_0]]$. Moreover note that Algorithm 3 and Algorithm 4 are only called after a full production period is moved.

Algorithm 3 enumerates all periods from the current value of $\gamma_{t_0}$ to $t_0$. As per Lemma 3 after production is moved, Algorithm 3 is not called again until the fractional production period is equal to $\gamma_{t_0}$. Therefore, that algorithm enumerates at most once all periods from $t_2$ to $t_1$ and its calls throughout the while-loop is of linear complexity.
Algorithm 4 updates parameter $q'$ and $\eta_{q'}$. More specifically, parameter $q'$ takes the value $q$ if it is higher than $\gamma_{t_0}$, or the value $\gamma_{t_0}$ otherwise. In the first case, the update of $\eta_{q'}$ is in constant-time complexity. In the second case, it requires the enumeration of all periods in interval $[\gamma_{t_0}, q]$. As per Lemma 3, this algorithm is not called again until the fractional production period is equal to $\gamma_{t_0}$. Since we consider in that case that $\gamma_{t_0}$ is lower than $q$, Algorithm 5 would have been called before the fractional production period reaches the value $\gamma_{t_0}$, updating the value of $q$ in the process to a period lower than or equal to $q'$. Hence, Algorithm 4 enumerates at most once all periods from $t_2$ to $t_1$ and its calls throughout the while-loop is of linear complexity.

Therefore Algorithm 6 is of linear complexity, and solving all subplans is done in cubic time, given the knowledge of an initial optimal solution to problem $P'(t'_{max})$ for each subplan. We discuss in the following section this initialization for all subplans in overall cubic time, so that the LS-CC-SUB may be solved in $O(T^3)$ worst-case complexity.

## 6. Initialization of the dynamic resolution for all subplans

For a given starting period $t_1 \in [|1, T|$] and starting, ending inventory value $I^1, I^2 \in \{0, 1\}$, the initialization is done dynamically for all subplans $(t_1, t_2, I^1, I^2)$ with $t_2 \in [|t_1, T|$] by solving all corresponding $P'(t'_{max})$ problems.

We extend results from van Hoesel and Wagelmans (1993) to present how to efficiently obtain an optimal solution to problem $P'(t'_{max})$ for subplan $(t_1, t_2, I^1, I^2)$ from the one for subplan $(t_1, t_2 + 1, I^1, I^2)$

**Theorem 4.** For any $t_2 \in [|t_1, T - 1|]$, the optimal solution of problem $P'(t'_{max})$ for subplan $(t_1, t_2, I^1, I^2)$ can be deduced from the one of subplan $(t_1, t_2 + 1, I^1, I^2)$ with at most one change in full production periods.

*Proof.* In order to simplify the notation, we denote by $t''_{max}$ and $t''_{max}$ the respective upper bound value of the fractional period for subplan $(t_1, t_2, I^1, I^2)$ and $(t_1, t_2 + 1, I^1, I^2)$.

The difference in total required production between subplans $(t_1, t_2, I^1, I^2)$ and $(t_1, t_2 + 1, I^1, I^2)$ is $d_{t_2+1} + I^2$. $(S_{t_2+1} - S_{t_2})$. Hence as per inequalities (10)-(12), this difference in production is lower than the production capacity and there is as much or one less full production period in subplan $(t_1, t_2, I^1, I^2)$ than in subplan $(t_1, t_2 + 1, I^1, I^2)$.

Period $t''_{max}$ is an upper bound on the value of all full production period for both subplan $(t_1, t_2 + 1, I^1, I^2)$ and subplan $(t_1, t_2, I^1, I^2)$, because of inequalities (10)-(11). Hence, any full production period in the optimal solution to problem $P'(t''_{max})$ for subplan $(t_1, t_2 + 1, I^1, I^2)$ that is under $t'_{max}$ remains optimal for problem $P'(t'_{max})$ of subplan $(t_1, t_2, I^1, I^2)$. Indeed from one subplan to another, it remains below its current upper bound, while the lower bound remain constant despite the change in fractional production period as per results obtained in section 4. Therefore, there are no changes needed to the value of full production periods under $t'_{max}$ when the optimal solution of problem $P'(t'_{max})$ for subplan $(t_1, t_2, I^1, I^2)$ is deduced from the one of subplan $(t_1, t_2 + 1, I^1, I^2)$.

Moreover, consider subplan $(t_1, t_2 + 1, I^1, I^2)$ with $K$ required full production period and a fractional production of value $f$. Suppose that in the optimal solution to the latter, the latest period of full production is denoted $t^C$. Then according to inequalities (10)-(11), we have: $I^2 \cdot S_{t_2} + d_{t^C, t_2} \ge f$. In other word, in the optimal solution to problem $P'(t''_{max})$ for subplan $(t_1, t_2 + 1, I^1, I^2)$, there cannot be more than one full production period higher than the latest period of fractional production for subplan $(t_1, t_2, I^1, I^2)$.

Therefore, at most one full production period must be moved when deducing an optimal solution to $P'(t'_{max})$ for subplan $(t_1, t_2, I^1, I^2)$ from the one for subplan $(t_1, t_2 + 1, I^1, I^2)$.

□

When deducing the optimal solution of problem $P'(t'_{max})$ for subplan $(t_1, t_2, I^1, I^2)$ from the one of subplan $(t_1, t_2 + 1, I^1, I^2)$, the procedure is straight forward if no move of full production period is required, either because the latest production period is deleted or because all production periods are under $t'_{max}$.

Otherwise, a production periods higher than $t'_{max}$ must be reallocated to a feasible available period under $t'_{max}$, or a production period under $t'_{max}$ must be deleted. Similarly to section 4, we introduce a parameter $k^-$ such that:

$$k^- = \max \{ \{k \in [|2, K|]; t^{k-1} < \underline{w}_k\} \cup \{0\} \}$$
Then the reallocation or the deletion must be done in interval $[|w_{k-}, t'_{max}|]$. This procedure is done in linear time by enumerating all periods in that interval.

Hence performing the initialization for all subplan $(t_1, t_2, I^1, I^2)$ takes as much time as solving the problem $P'(t^1_{max})$ for subplan $(t_1, T, I^1, I^2)$ and linearly deduce the optimal solution for all subplan $(t_1, t_2, I^1, I^2)$ with $t_2 \in [|t_1, T-1|]$. Therefore all initializations can be done in $O(T^3)$.

## References

Akbalik, A., Penz, B., and Rapine, C. (2015). Capacitated lot sizing problems with inventory bounds. *Annals of Operations Research*, 229:1–18.

Bitran, G. and Yanasse, H. (1981). Computational complexity of the capacitated lot size problem. *Management Science*, 28.

Brahimi, N., Absi, N., Dauzère-Pérès, S., and Nordli, A. (2017). Single-item dynamic lot-sizing problems: An updated survey. *European Journal of Operational Research*, 263(3):838–863.

Brahimi, N., Dauzere-Peres, S., Najid, N. M., and Nordli, A. (2006). Single item lot sizing problems. *European Journal of Operational Research*, 168(1):1–16.

Erenguc, S. and Aksoy, Y. (1990). A branch and bound algorithm for a single item nonconvex dynamic lot sizing problem with capacity constraints. *Computers and Operations Research*, 17(2):199–210.

Florian, M. and Klein, M. (1971). Deterministic production planning with concave costs and capacity constraints. *Management Science*, 18:12–20.

Love, S. F. (1973). Bounded production and inventory models with piecewise concave costs. *Management Science*, 20(3):313–318.

van Hoesel, S. and Wagelmans, A. (1993). An $o(t^3)$ algorithm for the economic lot-sizing problem with constant capacities. *Management Science*, 42:142–150.

Wagelmans, A., van Hoesel, S., and Kolen, A. (1992). Economic lot sizing: An $o(n \log n)$ algorithm that runs in linear time in the wagner-whitin case. *Operations Research*, 40:145–156.

Wolsey, L. (2005). Lot-sizing with production and delivery time windows. *Mathematical Programming*, 107:471–489.