Two-level lot-sizing with raw-material perishability and deterioration

Abstract

In many production systems, it is common to face significant rates of product deterioration, referring to physical exhaustion, loss of functionality and volume, or even obsolescence. This deterioration property, known as perishability, prevents such products from being used after their expiration time. We present lot-sizing problems that incorporate raw-material perishability and analyse how these considerations enforce specific constraints on a set of fundamental decisions, particularly for multi-level structures. We study three variants of the two-level lot-sizing problem incorporating different types of raw-material perishability: (a) fixed shelf-life, (b) functionality deterioration, and (c) functionality-volume deterioration. We propose mixed-integer programming formulations for each of these variants and perform computational experiments with sensitivity analyses. We analyse the added value of explicitly incorporating perishability considerations into production planning problems. For this, we compare the results of the proposed formulations with those obtained by implementing a sequential approach that adapts a standard two-level lot-sizing solution with a Silver-Meal-based rolling-horizon algorithm.

Keywords:

• Raw-material perishability
• lot-sizing;$·$ shelf-life
• deterioration
• production planning
• two-level lot-sizing
• mixed-integer programming
• batch ordering

Disclosure statement

No potential conflict of interest was reported by the author(s).

Funding

This work was partially supported by Natural Sciences and Engineering Research Council of Canada, COLCIENCIAS and the Universidad Pontificia Bolivariana Seccional Bucaramanga (Bucaramanga, Colombia). This support is gratefully acknowledged.

Appendix A. Description of test instances

All problem instances used to perform the computational experiments in Section 4 were randomly generated as follows. Three parameters were set a priori as a basis for comparison: planning horizon (n), shelf-life (β), and batch-size (b). In particular, we tested instances with $n\in \{18,20,22\},\beta \in \{2,4,6,8\}$, and $b\in \{50,100,150,200,250\}$. Another parameter set a priori is r = 3 for all considered instances. The remaining parameters were randomly generated using continuous or discrete uniform distributions, depending on the parameter, as follows:

• Demand: $d_t\sim U\left[150,300\right]$

• Unit production time: $a\sim U\left[2.5,3.5\right]$

• Unit production cost: $p_t\sim U\left[10.0,13.0\right]$

• Fixed set-up cost: $q_t\sim U\left[380.0,420.0\right]$

• Unit storage cost: $h_t\sim U\left[5.0,7.0\right]$

• Unit raw-material cost: ${\zeta }_t\sim U\left[1.0,3.0\right]$

• Upper ordering limit: $K_t\sim U\left[K_{\mathit{\text{coef}}}\times 4.5,K_{\mathit{\text{coef}}}\times 4.75\right],$

where the K_t values were generated considering the product of the average demand and the bill of material r, divided by the batch size b. With the purpose of integrating variability in a controlled manner, for the remaining parameters, three different value levels were generated each for 1/3 of the instances.

• Fixed order-placement cost: A high level using ${\rho }_t\sim U\left[500,550\right]$, a medium level using ${\rho }_t\sim U\left[250,300\right]$, and a low level using ${\rho }_t\sim U\left[150,200\right]$.

• Raw-material unit storage cost: A high level using ${\gamma }_t\sim U\left[8.0,12.0\right]$, a medium level using ${\gamma }_t\sim U\left[3.0,7.0\right]$, and a low level using ${\gamma }_t\sim U\left[1.0,2.0\right]$.

The capacitated instances used the following:

• Available process capacity: The C_t values were generated considering the upper demand limit 300 as follows: a high level using $C_t\sim U\left[300\times 4.5,300\times 4.75\right]$, a medium level using $C_t\sim U\left[300\times 4.25,300\times 4.5\right]$, and a low level using $C_t\sim U\left[300\times 4.0,300\times 4.25\right]$.

For the 2LS-FD and 2LS-FVD problem variants, the functionality deterioration rate $f(\delta )$ and volume deterioration rate $\nu (\delta )$ functions were randomly generated as follows:

• Functionality deterioration rate functions $f(\delta )$: for $0\le \delta <\beta$, where $\delta =(t-u),f(0)=p_t,f(1)=(p_t)(1+ran{d}_1)$, where $ran{d}_1\sim U\left(0,\frac{1}{\beta -1}\right),f(2)=(p_t)(1+ran{d}_2)$, where $ran{d}_2\sim U\left(\frac{1}{\beta -1},\frac{2}{\beta -1}\right)$, and so on.

• Volume deteriorations rate functions $\nu (\delta )$: for $0\le \delta <\beta$ where $\delta =(t-u),\nu (0)=ran{d}_0$, where $ran{d}_0\sim U\left(0,\frac{1}{\beta -1}\right),\nu (1)=ran{d}_1$, where $ran{d}_1\sim U\left(\frac{1}{\beta -1},\frac{2}{\beta -1}\right)$, and so on.

Appendix B. A standard two-level lot-sizing model

As described in Section 3, the standard two-level lot-sizing 2LS problem considers a production system in which one item (finished product) is to be produced and another item (raw-material), an input of the first, is to be procured from a supplier over a planning horizon with n time periods, $T=\{1,\dots ,n\}$. Solving the 2LS problem is to determine the production, procurement and inventory plans for the two items to meet the demands of the planning horizon, while minimising the corresponding costs.

To evaluate the added value of integrating raw-material perishability into classical lot-sizing problems, we initially performed a comparative analysis on the optimal solutions obtained with our MIP formulations and those of the 2LS model.

For each of our three problem variants, we evaluate the solutions of the 2LS. If they are feasible for the counterpart problems with raw-material deterioration, these solutions are compared with the optimal solutions of the proposed MIP formulations. Table 3 presents these results for a set of instances with n = 7 where the only varying parameters are $\beta =\{2,3,4\}$ and $b=\{40,80,100,150,200,250\}$. The same instances are used for the computational experiments presented in Section 4.1.

Table 3. Average standard 2LS solution deviations.

The first two columns in Table 3 specify the type of problem variant solved and the β values of the instances. The third column shows the percentage of instances for which the standard 2LS solution is infeasible (%inf) when adapted to solve its counterpart problem variant. The next column shows the average deviation (%dev) of the feasible solutions from the optimal solution of the actual problem considering raw-material perishability. The deviations are computed as %$\text{dev}=\left[\left({\text{SOL}}_{2\text{LS}}-\text{OPT}\right)/\text{OPT}\right]\times 100$, where ${\text{SOL}}_{2\text{LS}}$ is the objective function value of the feasible solution and OPT the optimal solution value. Finally, the last two columns show the percentage of instances with %dev greater than 10% and the maximum %dev observed, respectively.

Appendix C. A sequential approach

The goal of the sequential approach is to adapt the initial 2LS solutions to find feasible and possibly improved solutions for the considered problem variants. We begin by defining the terms:

${\widehat{x}}_t$ production decisions to fix obtained from standard 2LS solution for $1\le t\le n$, where ${\widehat{x}}_t={\sum }_{u=1}^t{w}_{ut}$.

${\widehat{X}}_{ut}$ fixed cumulative production to cover from period u to t.

${\overline{Q}}_{ut}$ order quantity (raw-material batches) in period u to cover fixed production up to t.

${\overline{z}}_{ut}$ binary raw-material for order placement variable.

${\overline{w}}_{ut}$ variables used to modified the original w_ut variables within the heuristic to avoid violation of the $\left(t-u\right)<\beta$ condition.

ACP_ut average cost per period for an order placed in period u to cover fixed production requirements up to t, where:

$$AC{P}_{ut}=\frac{{\rho }_u{\overline{z}}_u+{\zeta }_u{\overline{Q}}_{ut}+\sum _{t=u}^{{\Theta }_u}{p}_{ut}^i{\overline{w}}_{ut}+{\varphi }_u\left(b{\overline{Q}}_{ut}-\sum _{t=u}^{{\Theta }_u}{\overline{w}}_{ut}\right)}{(t-u)+1},$$ where $i=FS$ for the 2LS-FS variant and $i=FD$ for the 2LS-FD variant. We note that original Silver-Meal heuristic cannot be directly applied to any our problem variants and thus, an extended version is developed. For the 2LS-FS and 2LS-FD variants, the procedure used in the second step of the sequential approach are summarised in Algorithm 1.

Algorithm 1.

Sequential approach for 2LS-FS and 2LS-FD

1: Solve standard 2LS to obtain ${\widehat{y}}_t$, w_ut for $u,t\in T,u\le t$

2: $u\leftarrow 1$

3: while t < n do

4: $t\leftarrow u$

5: ${\widehat{X}}_{ut}\leftarrow \frac{{\sum }_{t=u}^n{w}_{ut}}{r}$

6: if ${\widehat{X}}_{ut}=0$ then

7: ${\overline{Q}}_{ut}\leftarrow 0$

8: ${\overline{z}}_u\leftarrow 0$

9: else

10: ${\overline{Q}}_{ut}\leftarrow \text{max}\left\{\lceil \frac{r{\widehat{X}}_{ut}}{b}\rceil ,L\right\}$

11: ${\overline{z}}_u\leftarrow 1$

12: end if

13: ${\overline{w}}_{ut}\leftarrow r{\widehat{x}}_t$

14: Evaluate ACP_ut

15: if $AC{P}_{ut}>AC{P}_{u,t-1}$ or $t+1={\Theta }_u$ then

16: go to step 20

17: else

18: $t\leftarrow (t+1)$ and go to step 5

19: end if

20: $z_u\leftarrow {\overline{z}}_{u,t-1},Q_u\leftarrow {\overline{Q}}_{u,t-1}$, and $w_{u,t-1}\leftarrow {\overline{w}}_{u,t-1}$

21: $u\leftarrow (u+1)$ and go to step 4

22: end while

23: return $z_u,Q_u,w_{ut}$ for $u,t\in T,0\le (t-u)<\beta$

For the 2LS-FVD variant, ACP_ut is computed as follows: $$AC{P}_{ut}=\frac{{\rho }_u{\overline{z}}_u+{\zeta }_u{\overline{Q}}_{ut}+\sum _{t=u}^{{\Theta }_u}{p}_{ut}^{FVD}{w}_{ut}+\sum _{t=u}^{{\Theta }_u}\left({\gamma }_u{c}_{ut}+{\varphi }_u{e}_{ut}\right)}{(t-u)+1},$$ and the steps are shown in Algorithm 2.

Algorithm 2.

Sequential approach for 2LS-FVD

1: Solve standard 2LS, return ${\widehat{y}}_t$, w_ut for $u,t\in T,u\le t$

2: $u\leftarrow 1$

3: while t < n do

4: $t\leftarrow u$

5: if u = t then

6: if ${\widehat{x}}_u$ = 0 then

7: ${\overline{Q}}_{ut}\leftarrow 0$

8: ${\overline{z}}_u\leftarrow 0$

9: else

10: ${\overline{Q}}_{ut}\leftarrow \text{max}\left\{\lceil \frac{r{\widehat{x}}_u}{b}\rceil ,L\right\}$

11: ${\overline{z}}_u\leftarrow 1$

12: end if

13: else

14: if ${\widehat{x}}_u$ = 0 then

15: ${\overline{Q}}_{ut}\leftarrow 0$

16: ${\overline{z}}_u\leftarrow 0$

17: else

18: ${\overline{Q}}_{ut}\leftarrow \text{max}\left\{\lceil \frac{\left[\frac{{\overline{c}}_{ut}}{\left(1-\nu (0)\right)}+r{\widehat{x}}_u\right]}{b}\rceil ,L\right\}$

19: ${\overline{z}}_u\leftarrow 1$

20: end if

21: end if

22: Evaluate ${\overline{w}}_{ut},{\overline{c}}_{ut}$, and ${\overline{e}}_{ut}$ for all $u\le t\le {\Theta }_u$

23: Evaluate ACP_ut

24: if $AC{P}_{ut}>AC{P}_{u,t-1}$ or $t+1={\Theta }_u$ then

25: go to step 29

26: else

27: $t\leftarrow (t+1)$ and go to step 18

28: end if

29: $z_u\leftarrow {\overline{z}}_{u,t-1},Q_u\leftarrow {\overline{Q}}_{u,t-1}$ for $u\le t\le {\Theta }_u$

30: $w_{u,t-1}\leftarrow {\overline{w}}_{u,t-1},c_{u,t-1}\leftarrow {\overline{c}}_{u,t-1}$, and $e_{u,t-1}\leftarrow {\overline{e}}_{u,t-1}$ for $u\le t\le {\Theta }_u$

31: $u\leftarrow (u+1)$ and go to step 4

32: end while

33: return $z_u,Q_u,w_{u,t},c_{ut},e_{ut}$ for $u,t\in T,0\le (t-u)<\beta$

Where ${\overline{w}}_{ut}=r{\widehat{x}}_t$; ${\overline{c}}_{ut}=\left({\overline{c}}_{u,t-1}-r{\widehat{x}}_t\right)\left(1-\nu (\delta )\right)$ and ${\overline{c}}_{uu}=r{\widehat{x}}_{u+1}$, and ${\overline{e}}_{ut}=\left({\overline{c}}_{u,t-1}-r{\widehat{x}}_t\right)\left(\nu (\delta )\right)$ and ${\overline{e}}_{uu}=\left(b{\overline{Q}}_{ut}-{\widehat{x}}_t\right)\left(\nu (\delta )\right)$.