Capacitated lot sizing problems with inventory bounds

Abstract

In this paper, we study the single-item and the multi-item capacitated lot sizing problem in presence of inventory bounds (CLSP-IB). That is, in any period, both the quantity produced and the stock on hand are limited. For the single-item CLSP-IB with a stationary production capacity, time-dependent inventory bounds and concave costs, we show that the problem can be solved in time $O(T^4)$ by adapting a well-known algorithm in the literature. Restricting to non-speculative costs, we propose an $O(T^3)$ time dynamic programming algorithm. For the multi-item CLSP-IB, we consider the lot-sizing problem with item dedicated machines and a common capacitated storage space shared by all the items. We show that this problem is $\text{ NP }$-hard in the strong sense even if all the cost parameters and capacities of the instance are stationary and identical for each item.

Appendix: Illustrative example for the complexity reduction

We give an example to show the idea of the reduction theoretically explained above. We consider $n=6, T=n+1=7, P=\frac{n(n+1)}{2}=21$. The subsets $S$ are given as follows: $S_1=\{x_1,x_2,x_3\}, S_2=\{x_2,x_3,x_4\}, S_3=\{x_3,x_4,x_5\}, S_4=\{x_4,x_5,x_6\}, S_5=\{x_1,x_2,x_6\}, S_6=\{x_1,x_5,x_6\}$

The two sets of items are considered as: $A_1,\ldots ,A_6$ and $F_1,\ldots ,F_6$. We give in Fig. 6 the demand configuration of items $A$.

Fig. 6

Demand for items $A_1,\ldots ,A_6$

We observe that at the end of each period $i$, there is a positive storage quantity $P-\frac{i(i+1)}{2}$ in the warehouse. Those quantities must be stored in order to satisfy the demand exceeding the production capacity in periods $i+1$. The stored quantities of items A are shown in Fig. 7.

Fig. 7

Quantity of items $A_i$ to store at the end of each period

The storage space is recomputed for each period and the new values are given in Fig. 8. One can easily deduce that items A are produced at full production capacity over seven periods with a total cost of $n(n+1)=6.7=42$.

Fig. 8

Remaining space at warehouse after the storage of items $A_i$

Concerning the items $F_i$, demand configurations are given in Fig. 9 and the data is as follows:

$$\begin{aligned} d_{F_1}&= \{20,19,18,21,21,21,6\}, \\ d_{F_2}&= \{21,19,18,17,21,21,9\}, \\ d_{F_3}&= \{21,21,18,17,16,21,12\}, \\ d_{F_4}&= \{21,12,21,17,16,15,15\},\\ d_{F_5}&= \{20,19,21,21,21,15,9\}, \\ d_{F_6}&= \{20,21,21,21,16,15,12\} \end{aligned}$$

We remark that in order to satisfy the demand of each $F_i$ over periods 1–6, one has to produce those items in periods $\{1,\ldots ,6\}$ (see Lemma 2). The latter has a cost of $n^2=36$. The question asked by the instance is to know if a production policy with a cost at most $Z=2n^2 + \frac{5n}{3}$ exists. For this example, $Z=82$ for $n=6$. We have already a total cost of 78. Thus, in an optimal solution we can make at most four setups in period 7 for all items F. We have to anticipate the demand of at least 2 items from the period 7 to the previous periods. However, we are constrained by the storage space: we can only anticipate at most 2 items demand. This corresponds to the search of an exact cover. Some covers are for example: $(F_1 \, \hbox {and} \, F_4)$ or $(F_2 \, \hbox {and} \, F_6)$ or $(F_3 \, \hbox {and} \, F_5)$.

Fig. 9

Demand configuration for items $F_1,\ldots ,F_6$