New Valid Inequalities for a Multi-echelon Multi-item Lot-Sizing Problem with Returns and Lost Sales

Abstract

This work studies a multi-echelon multi-item lot-sizing problem with remanufacturing and lost sales. The problem is formulated as a mixed-integer linear program. A new family of valid inequalities taking advantage of the problem structure is introduced and used in a customized branch-and-cut algorithm. The provided numerical results show that the proposed algorithm outperforms both the generic branch-and-cut algorithm embedded in a standard-alone mathematical solver and a previously published customized branch-and-cut algorithm.

This work was partially funded by the National Agency for Research and Development (ANID)/Scholarship Program/DOCTORADO BECAS CHILE/2018 - 72190160.

1 Introduction

Industrial companies face an increasing pressure from customers and governments to become more environmentally responsible and mitigate the environmental impact of their products. One way of achieving this objective is to remanufacture the products once they have reached their end of life. Remanufacturing is defined as a set of processes transforming used products into like-new products, mainly by rehabilitating damaged components. By reusing the materials and components embedded in used products, remanufacturing both contributes in reducing pollution emissions and natural resource consumption, making production processes more environment-friendly.

The present work considers a remanufacturing system involving three production echelons: disassembly of used products brought back by customers, refurbishing of the recovered parts and reassembly into like-new finished products. We aim at optimizing the production planning for the corresponding three-echelon system over a multi-period horizon. Within a remanufacturing context, production planning includes making decisions on the used products returned by customers, such as how much and when used products should be disassembled, refurbished or reassembled in order to build new or like-new products. The main objective is to meet customers’ demand for the remanufactured products in the most cost-effective way.

We consider the case where the production on a machine requires setup operations such as machine calibration and incurs fixed setup costs. As a naive perception, to reduce these setup costs, production should be run using large lot sizes. However, this generates desynchronized patterns between the customers’ demand and the production plan leading to costly high levels of inventory. Lot-sizing models thus aim at reaching the best possible trade-off between minimizing the setup costs and minimizing the inventory holding costs, taking into account both the customers’ demand satisfaction and the practical limitations of the system. In the present work, we investigate the problem of reaching the best possible trade-off between setup and inventory holding costs within a remanufacturing environment and introduce an additional lost sales cost to be paid when the customers’ demand is not satisfied on time. We thus study a 3-echelon lot-sizing problem with returns and lost sales.

Only a few works have addressed such multi-echelon production systems through exact solution approaches. A first attempt at tackling this difficulty can be found in [12]. Quezada et al. [12] considered the problem in a stochastic setting, taking into account uncertainties on the problem input parameters. They proposed a multi-stage stochastic approach based on the use of scenario trees. The problem was formulated as a MILP and solved through a new customized branch-and-cut algorithm. This algorithm relied on valid inequalities focused on strengthening the formulation of the single-echelon uncapacitated lot-sizing sub-problems embedded in the main problem. Although this approach was successful at providing near optimal solutions for small to medium size instances, some numerical difficulties were encountered to solve the larger instances. Intuitively, this difficulty might be partly due to the fact that the valid inequalities used to strengthen the formulation considered uncapacitated single-echelon sub-problems. They did not take into account the fact that, even if the production resources are assumed uncapacitated, the amount of products that can be processed on a resource at a given time period is limited among others by the amount of available used products returned up to this time period and by the yield of the disassembly process, i.e. by the proportion of disassembled parts that are in a sufficiently good state to be refurbished and reused in a remanufactured product. Hence, using valid inequalities taking into account this aspect of the problem might contribute in further strengthening its MILP formulation and decrease the computational effort needed to solve large-size instances.

To the best of our knowledge, the formulation of valid inequalities that explicitly take into account the impact of a limited returns quantity on the production plan has not yet been studied for a multi-echelon remanufacturing system. The present work aims at partially closing this gap by proposing new valid inequalities for this problem. However, in view of the theoretical and numerical difficulties encountered when developing new valid inequalities, we focus on the deterministic variant of the problem. Our contributions are thus twofold. First, we propose a new family of valid inequalities for the problem under study. These valid inequalities can be seen as an extension of valid inequalities previously known for the uncapacitated single-echelon lot-sizing problem with lost sales (the (k, U) inequalities first introduced in [8]) to take into account, at each echelon of the studied multi-echelon production system, the constraints on the production plan coming from the limited availability of the returns. We prove that these new valid inequalities are at least as strong as the previously known inequalities. Second, we develop a branch-and-cut algorithm based on the newly proposed valid inequalities and seek to assess its computational performance by comparing it with the one of a stand-alone mathematical programming solver and the one of a branch-and-cut algorithm based on previously known valid inequalities. The numerical results show the usefulness of the proposed inequalities at solving the problem under study.

The remainder of this paper is organized as follows. We first provide a brief overview of the related literature in Sect. 2. The problem description, together with its MILP formulation, are provided in Sect. 3. We then present the proposed new family of valid inequalities in Sect. 4. Computational results are summarized in Sect. 5. Finally, Sect. 6 gives a conclusion and some research perspectives.

2 Related Works

Throughout the last decade, several works sought to strengthen the MILP formulation of single-echelon lot-sizing problems involving remanufacturing, either through extended reformulations or through valid inequalities.

Helmrich et al. [13] discussed several MILP formulations of the uncapacitated single-item single-echelon lot-sizing problem with remanufacturing and introduced new valid inequalities by adapting the previously known (l, S, WW) proposed by [10] to their problem. The inequalities developed in [13] are based on the assumption that all returned products are either processed or kept in stock and do not consider the possibility that some of the returns may be discarded in case of an unbalance between returns quantity and demand. They can therefore not be directly used for the problem under study here. Similarly, [5] proposed a multi-commodity reformulation and a new set of valid inequalities for this problem. In particular, they further strengthened the (l, S, WW) inequalities presented in [13] by considering that the amount of finished products remanufactured in a given period t is limited by the cumulative quantity of returned products brought back up to t. Ali et al. [2] enriched the previous works by highlighting a theoretical property with regards to the equivalence of the shortest path and facility location reformulations. They also carried out a polyhedral analysis of a related sub-problem based on the single node fixed-charge network problem, proving the validity of several flow cover inequalities and their facet-defining conditions as well. Akartunali and Arulselvan [1] studied both the uncapacitated and capacitated variants of this single-item single-echelon lot-sizing problem. They showed that the uncapacitated problem cannot have a fully polynomial time approximation scheme (FPTAS) and provided a pseudo-polynomial algorithm to solve the problem. They also provided valid inequalities based on the flow-cover inequalities for the problem with a limited production capacity. Finally, we refer the reader to [4] for a recent survey on single-item lot-sizing problems with remanufacturing.

We note that all the above mentioned works focus on single-item single-echelon problems and do not consider the fact that remanufacturing may involve several processing steps, i.e. several production echelons, in order to transform the returned used products into like-new products. Moreover, these works consider hybrid manufacturing/remanufacturing systems and assume that, thanks to the presence of an uncapacitated manufacturing system, it will always be possible to satisfy the demand for finished products on time. In contrast, we investigate a pure remanufacturing system and consider that the demand will be lost in case the quantity and/or the quality of the returned products are insufficient to meet it on time. This means among others that the inequalities introduced in [5, 13] and [2] are not valid for our problem and that new valid inequalities taking into account its specific features are needed.

3 Problem Description and Modeling

3.1 Production System

We consider a remanufacturing system comprising three main production echelons: disassembly, refurbishing and reassembly. We seek to plan the production activities in this system over a horizon comprising a discrete set $\mathcal {T}=\{1,.., T\}$ of periods. The system involves a set $\mathcal {I}$ of items. Among these ones, item $i=0$ represents the used products returned by customers in limited quantities at each period. A used product is composed of I parts. Let $\alpha _i$ be the number of parts i embedded in a used product. The returned products are first disassembled to obtain a set $\mathcal {I}_r=\{1,...,I\}$ of recoverable parts. Due to the usage state of the used products, some of the parts obtained during disassembly have to be discarded. In order to reflect the variations in the quality of the used products, i.e. the yield of the disassembly process, we let $\pi _i^{t}$ denote the proportion of parts which will be recoverable at each time period t for each item $i = \{1, \dots , I \}$. The recoverable parts are then refurbished on dedicated refurbishing processes. The set of $\mathcal {I}_s=\{I+1,...,2I\}$ of serviceable parts obtained after refurbishing are reassembled into remanufactured products which have the same bill-of-material as the used products. These remanufactured products, indexed by $i=2I+1$, are used to satisfy the dynamic demand of customers.

The system comprises a set $\mathcal {P}=\{0,..., I+1\}$ of production processes: $p=0$ corresponds to the disassembly process, $p\in \{1,...,I\}$ corresponds to the process refurbishing the recoverable part indexed by p into the serviceable part indexed by $p+I$ and $p=I+1$ corresponds to the reassembly process. All these processes are assumed to be uncapacitated. However, the system might not be able to satisfy the customer demand on time due to part shortages if there are not enough used products returned by customers or if their quality is low. In this situation, the corresponding demand is lost incurring a high penalty cost to account for the loss of customer goodwill. Moreover, some used products and recoverable parts are allowed to be discarded. This option might be useful in case more used products are returned than what is needed to satisfy the demand for remanufactured products and in case there is a strong unbalance between the part-dependent disassembly yields leading to an unnecessary accumulation in inventory of the easy-to-recover parts.

All input parameters of the problem are time-dependent: ${r^t}$ denotes the quantity of collected used products, ${d^t}$ the customers’ demand and $\pi _{i}^{t}$ the proportion of recoverable parts $i \in \mathcal {I}_r$ obtained by disassembling one unit of returned product at period t. As for the costs, for each period t, we have the setup cost ${f}_{p}^t$ for process $p \in \mathcal {P}$, the unit inventory cost ${h_{i}^t}$ for part $i \in \mathcal {I}$, the unit lost-sales penalty cost ${l}^t$, the unit cost $q_{i}^{t}$ for discarding item $i \in \mathcal {I}_r \cup \lbrace 0 \rbrace$ and the unit cost $g^t$ for discarding the unrecoverable parts obtained while disassembling one unit of returned product (Fig. 1).

Fig. 1.

Studied remanufacturing system

3.2 Natural Formulation

In order to build a mathematical model for the problem, we introduce the following decision variables at time period $t \in \mathcal {T}$: $X^{t}_{p}$ the quantity of parts processed on process $p \in \mathcal {P}$, $Y^{t}_{p} \in \{0,1\}$ the setup variable for process $p \in \mathcal {P}$, $S^{t}_{i}$ the inventory level of part $i \in \mathcal {I}$, $Q^{t}_{i}$ the quantity of part $i \in \mathcal {I}_r \cup \{0\}$ discarded and $L^{t}$ the lost sales of remanufactured products. This leads to the following MILP model.

$$\begin{aligned}&\min \sum _{t \in \mathcal {T}} \Big ( \sum _{p \in \mathcal {J}} {f}_{p}^t Y_{p}^{t} + \sum _{i \in \mathcal {I}} h_{i}^t S_{i}^{t}+ l^t L^t + \sum _{i \in \mathcal {I}_r \cup \{0\}} q_{i}^t Q_{i}^t + g^{t} X_{0}^t \Big ) \end{aligned}$$

(1)

$$\begin{aligned}&X_{p}^{t}\le M_p^t Y_{p}^{t}&\forall p \in \mathcal {J}, \forall t \in \mathcal {T} \end{aligned}$$

(2)

$$\begin{aligned}&S_{0}^{t} = S_{0}^{t-1} + r^t - X_{0}^{t} - Q_{0}^t&\forall t \in \mathcal {T} \end{aligned}$$

(3)

$$\begin{aligned}&S_{i}^{t} = S_{i}^{t-1} + \pi _{i}^t \alpha _i X_{0}^t - X_{i}^t - Q_{i}^t&\forall i \in \mathcal {I}_{r}, \forall t \in \mathcal {T}\end{aligned}$$

(4)

$$\begin{aligned}&S_{i}^{t} = S_{i}^{t-1} + X_{i-I}^t - \alpha _i X_{I + 1}^t&\forall i \in I_{s},\forall t \in \mathcal {T}\end{aligned}$$

(5)

$$\begin{aligned}&S_{2I + 1}^t= S_{2I + 1}^{t-1} + X_{I + 1}^t- d^t +L^t&\forall t \in \mathcal {T}\end{aligned}$$

(6)

$$\begin{aligned}&S_{i}^0= 0&\forall i \in \mathcal {I} \end{aligned}$$

(7)

$$\begin{aligned}&S_{i}^t\ge 0&\forall i \in \mathcal {I} ,\forall t \in \mathcal {T}\end{aligned}$$

(8)

$$\begin{aligned}&X_{p}^t \ge 0,Y_{p}^{t}\in \{ 0,1\}&\forall p \in \mathcal {J}, \forall t \in \mathcal {T} \end{aligned}$$

(9)

The objective function (1) aims at minimizing the total remanufacturing cost over the whole planning horizon, i.e., the sum of the setup, inventory holding, lost sales and disposal costs. Constraints (2) link the production quantity variables to the setup variables. Constraints (3)–(6) are the inventory balance constraints. More specifically, Constraints (3) ensure that any returned product is either disassembled, discarded, or kept in stock. Constraints (4) guarantee that any item obtained from the disassembly process is either refurbished, discarded, or kept in stock. Constraints (5) ensure that any refurbished item is either used in the reassembly process or kept in stock. Constraints (6) ensure that any remanufactured/finished product is either used to satisfy the demand or kept in stock and that, if there is not enough remanufactured products to satisfy the demand, the unsatisfied demand is lost. Without loss of generality, we assume that the initial inventory, $S_{i}^0$, is set to 0 for each item $i \in \mathcal {I}$ ( see Constraints (7)). Finally, Constraints (8)–(9) provide the domain of the decision variables.

Note that the value of each constant $M_p^t$ can be set by using an upper bound on the quantity that can be processed on process p at each time period t. This quantity is limited by two elements: the availability of the used products already returned by customers and the future demand for remanufactured products. We thus have, for each period t:

• $M_{0}^t = \min \left\{ \sum \limits _{1 \le \kappa \le t} r^{\kappa }, \frac{\sum \limits _{t \le \kappa \le T } d^{\kappa }}{\min \limits _{i=1,\dots ,I} \pi _{i}^t} \right\}$

• $M_{p}^t = \alpha _p \min \bigg \{ \sum \limits _{1 \le \kappa \le t} r^{\kappa } \hat{\pi }_{p}^{\kappa , t}, \sum \limits _{1\le \kappa \le T} d^{\kappa } \bigg \}$, for $p \in \mathcal {I}_r$.

• $M_{I+1}^t = \min \left\{ \mathop {\min }\limits _{p \in \mathcal {I}_r }\left\{ \sum \limits _{1 \le \kappa \le t} r^{\kappa } \hat{\pi }_{p}^{\kappa ,t} \right\} , \sum \limits _{t \le \kappa \le T} {d^\kappa } \right\}$

where $\hat{\pi }_p^{\kappa ,t} = \text {argmax} \{ \pi ^{\theta }_p, \theta = \kappa , \dots , t\}$ denotes the maximum disassembly yield that can be obtained for recoverable item p over the time interval $[\kappa ,t]$.

3.3 Echelon Stock Reformulation

We now provide a reformulation of the problem using the echelon stock concept [11]. The echelon stock of a product in a multi-echelon production system corresponds to the total quantity of the product held in inventory, either as such or as a component within its successors in the bill-of-material. We thus denote by $E_i^t$ the echelon stock level of item $i \in \mathcal {I} \setminus \{0\}$ at the end of period t. Replacing variables $S_i^t$ by variables $E_i^t$ in Problem (1)–(9) leads to the following MILP formulation:

$$\begin{aligned}&\min \sum _{t \in \mathcal {T}} \Big ( \sum _{p \in \mathcal {J}} {f}_{p}^tY_{p}^{t} + h_{i}^tS_{0}^{t} + \sum _{i \in \mathcal {I} \setminus \{0\}} eh_{i}^tE_{i}^{t}+ \sum _{i \in \mathcal {I}_r \cup \{0\}} q_{i}^tQ_{i}^t+ g_0^{t} X_{0}^t \Big ) \end{aligned}$$

(10)

$$\begin{aligned}&X_{p}^{t}\le M_p^t Y_{p}^{t}&\forall p \in \mathcal {J}, \forall t \in \mathcal {T}\end{aligned}$$

(11)

$$\begin{aligned}&S_{0}^{t} = S_{0}^{t-1} + r^t- X_{0}^{t} - Q_{0}^t&\forall t \in \mathcal {T} \end{aligned}$$

(12)

$$\begin{aligned}&E_{i}^{t} = E_{i}^{t-1} + \pi _{i}^t\alpha _i X_{0}^t- \alpha _i (d^t -L^t) - Q_{i}^t&\forall i \in \mathcal {I}_{r}, \forall t \in \mathcal {T} \end{aligned}$$

(13)

$$\begin{aligned}&E_{i}^{t} = E_{i}^{t-1} + X_{i-I}^t- \alpha _i (d^t - L^t)&\forall i \in I_{s},\forall t \in \mathcal {T}\end{aligned}$$

(14)

$$\begin{aligned}&E_{2I + 1}^t= E_{2I + 1}^{t-1} + X_{I + 1}^t - d^t + L^t&\forall t \in \mathcal {T}\end{aligned}$$

(15)

$$\begin{aligned}&S_{0}^{0} = 0 \end{aligned}$$

(16)

$$\begin{aligned}&E_{i}^{0} = 0&\forall i \in \mathcal {I} \setminus \{0\} \end{aligned}$$

(17)

$$\begin{aligned}&E_{i}^{t} - E_{I+i}^{t} \ge 0&\forall i \in \mathcal {I}_r, \forall n \in \mathcal {T}\end{aligned}$$

(18)

$$\begin{aligned}&E_{i}^t - \alpha _{i}E_{2I+1}^t \ge 0&\forall i \in \mathcal {I}_s, \forall n \in \mathcal {T} \end{aligned}$$

(19)

$$\begin{aligned}&E_{i}^t \ge 0&\forall i \in \mathcal {I} ,\forall t \in \mathcal {T}\end{aligned}$$

(20)

$$\begin{aligned}&S_{0}^t,L^t \ge 0&\forall t \in \mathcal {T}\end{aligned}$$

(21)

$$\begin{aligned}&X_{p}^t\ge 0,Y_{p}^{t} \in \{ 0,1\}&\forall p \in \mathcal {J}, \forall t \in \mathcal {T} \end{aligned}$$

(22)

The objective function (10) aims at minimizing the total cost over the whole planning horizon. Constraints (11) link the production quantity variables to the setup variables. Constraints (12)–(15) are the inventory balance constraints. Constraints (12) use the classical inventory variables, whereas Constraints (13)–(15) make use of the echelon inventory variables. Constraints (16)–(17) translate the fact that the initial inventory of each item is assumed to be equal to 0. Constraints (18)–(19) ensure consistency between the echelon inventory at the different echelons of the bill-of-material and guarantee that the physical inventory of each product, $S_{i}^t$, remains non-negative for all $i \in \mathcal {I}$ . Finally, Constraints (20)–(22) define the domain of the decision variables.

The use of the echelon stock reformulation (11)–(22) enables us to decompose the initial problem into a series of single-echelon sub-problems by relaxing the linking constraints (18)–(19). Each of these sub-problems is an uncapacitated single-echelon single-item lot-sizing problem with lost sales, whose formulation can be strengthened by the (k, U) valid inequalities proposed in [8]. We refer the reader to [12] for a detailed description of each subproblem and the single-echelon (k, U) inequalities applied to each subproblem. Nonetheless, this decomposition into single-echelon uncapacitated sub-problems overlooks the fact that the production on each process at a given period is limited by the amount of used products returned up to this period. Therefore, in what follows, we investigate a class of valid inequalities in which these aspects of the problem are explicitly considered.

4 Single-Echelon $(\ell , k,U)$ Inequalities

We now seek to strengthen the single-echelon (k, U) inequalities investigated in [8] and [12] by considering the limited quantity of returned products available at each time period in the system. The $(\ell , k,U)$ inequalities are defined as follows:

Proposition 1

Let $0 \le \ell \le k \le T$ be two periods of the planning horizon.

Let $U \subseteq \{k+1,...,T\}$ be a subset of periods and $t^* = \max \{ \tau : \tau \in U \}$ be the last time period belonging to U.

The following inequalities are valid for Problem (11)–(22):

$$\begin{aligned}&S_0^\ell \hat{\pi }^{\ell , t^*}_i + \alpha _i^{-1}E^k_{i} + \sum \limits _{k < t \le t^*} \phi _i^t Y^t_0 \ge \sum \limits _{ t \in U} (d^t-L^t)&\forall i \in \mathcal {I}_r \end{aligned}$$

(23)

$$\begin{aligned}&S_0^\ell \hat{\pi }^{\ell , t^*}_i + \alpha _i^{-1}(E^\ell _{i}-E^\ell _{i+I}) + \alpha _i^{-1} E^k_{i+I} + \sum \limits _{k < t \le t^*} \phi _i^t Y^t_i \ge \sum \limits _{ t \in U} (d^t-L^t)&\forall i \in \mathcal {I}_r \end{aligned}$$

(24)

$$\begin{aligned}&S_0^\ell \hat{\pi }^{\ell , t^*}_i + (\alpha _i^{-1}E^\ell _{i} - E^\ell _{2I+I}) + E^k_{2I+1} + \sum \limits _{k < t \le t^*} \phi _i^t Y^t_{I+1} \ge \sum \limits _{ t \in U} (d^t-L^t)&\forall i \in \mathcal {I}_r \end{aligned}$$

(25)

with $\phi _i^t = \min \Big \{\sum \limits _{ \ell < \nu \le t} r^{\nu } \hat{\pi }^{\nu , t}_i ,\sum \limits _{\nu \in U : t \le \nu } d^{\nu } \Big \}$

Proof

Let (X, Y, S, E, L, Q) be a feasible solution of Problem (10)–(22). We show that this solution complies with inequalities (23) for any pair of periods $(\ell , k)$, any subset $U \subset \{k+1,..., T\}$ and any recoverable item $i \in \mathcal {I}_r$.

Let $\tau \in [k+1, t^*]$ be the first production period in which $\phi _i^{\tau }=\sum \limits _{\nu \in U : \tau \le \nu } d^{\nu }$. By convention, $\tau =t^*+1$ if there is no such period.

We have $\phi _i^{\tau } Y_0^{\tau } = \sum \limits _{t \in U : \tau \le t} d^{t} \ge \sum \limits _{ t \in U: \tau \le t} (d^{t}-L^{t})$.

We consider two cases.

– Case 1: there is no production on $p=0$ over the interval $[k+1; \tau -1]$

In this case, $Y_0^t=0$ and $X_0^t=0$ for all periods t in $[k+1,\tau -1]$. As no disassembly occurs over $[k+1, \tau -1]$, all the recoverable items needed to satisfy the demand over this time interval, and in particular needed to satisfy $\sum \limits _{ t \in U; t\le \tau -1 } (d^t-L^t)$, should already have been disassembled previously and be in stock at the end of period k. This gives $\alpha _i^{-1}E^k_{i} \ge \sum \limits _{ t \in U: t \le \tau -1} (d^t-L^t)$. We thus have:

$$\begin{aligned} S_0^\ell \hat{\pi }^{\ell , t^*}_i + \alpha _i^{-1}E^k_{i} + \sum \limits _{k < t \le t^*} \phi _i^t Y^t_0 \ge \alpha _i^{-1}E^k_{i} + \phi _i^{\tau } Y_0^{\tau } \ge \sum \limits _{ t \in U} (d^t-L^t) \end{aligned}$$

Inequality (23) is thus valid in this case.

– Case 2: there is at least one production period on $p=0$ over interval $[k+1; \tau -1]$

Let $\theta$ be the last period of production on $p=0$ over the interval $[k+1; \tau -1]$. By definition of $\theta$, we have: $\phi _i^{\theta } = \sum \limits _{\ell < \nu \le \theta } ( r^{\nu } \hat{\pi }^{\nu , \theta }_i)$.

By summing up the inventory balance constraints (13) over periods $k+1$,...,$\tau -1$ and using the fact that variables $E_i^k$ and $Q_i^t, \forall t=k+1, \dots , \tau -1$, are non-negative, we have:

$$\begin{aligned} \alpha _i^{-1} E_i^k + \sum _{t=k+1}^{\tau -1} \pi _i^t X_0^t\ge \sum _{t=k+1}^{\tau -1} (d_t-L_t) \end{aligned}$$

(26)

By definition of $\tau$, $\theta$ and $\ell$, we have:

$$\begin{aligned} \sum _{t=k+1}^{\tau -1} \pi _i^t X_0^t= \sum _{t=k+1}^{\theta } \pi _i^t X_0^t \le \sum _{t=\ell +1}^{\theta } \pi _i^t X_0^t \end{aligned}$$

(27)

This gives:

$$\begin{aligned} \alpha _i^{-1}E_i^k + \sum _{t=\ell +1}^{\theta } \pi _i^t X_0^t\alpha _i^{-1}&\ge E_i^k + \sum _{t=k+1}^{\tau -1} \pi _i^t X_0^t \end{aligned}$$

(28)

$$\begin{aligned}&\ge \sum _{t=k+1}^{\tau -1} (d_t-L_t) \end{aligned}$$

(29)

$$\begin{aligned}&\ge \sum \limits _{t \in U: t\le \tau -1} (d_t-L_t) \end{aligned}$$

(30)

We now compute an upper bound of $\sum _{t=\ell +1}^{\theta } \pi _i^t X_0^t$. This one is obtained by first computing the linear combination $\sum _{t=\ell +1}^{\theta } \Big ( \hat{\pi }^{t, \theta }_i \Big ) \times$ (12)$_{t}$. This gives:

$$\begin{aligned} \sum _{t=\ell +1}^{\theta } \Big (\hat{\pi }^{t, \theta }_i \Big ) S_0^t = \sum _{t=\ell +1}^{\theta } \Big (\hat{\pi }^{t, \theta }_i \Big ) \Big [S_0^{t-1} + r^t - X_0^t -Q_0^t\Big ] \end{aligned}$$

(31)

By the non-negativity of variables $Q^t_0$ and $S^t_0$ and the fact that $\hat{\pi }^{t,\theta }_i\ge \hat{\pi }^{t+1,\theta }_i$, we have:

$$\begin{aligned}&\sum _{t=\ell +1}^{\theta } \pi _i^t X_0^t&\le \sum _{t=\ell }^{\theta } \hat{\pi }^{t, \theta }_i X_0^t \end{aligned}$$

(32)

$$\begin{aligned}&\le \sum _{t=\ell +1}^{\theta } \Big (\hat{\pi }^{t, \theta }_i \Big ) S_0^{t-1} - \sum _{t=\ell +1}^{\theta } \Big (\hat{\pi }^{t, \theta }_i \Big ) S_0^t + \sum _{t=\ell +1}^{\theta } \Big (\hat{\pi }^{t, \theta }_i \Big ) r^t\end{aligned}$$

(33)

$$\begin{aligned}&\le \Big (\hat{\pi }^{\ell , \theta }_i \Big ) S_0^{\ell } + \sum _{t =\ell +1}^{\theta } \Big (\hat{\pi }^{t, \theta }_i \Big ) r^t \end{aligned}$$

(34)

$$\begin{aligned}&\le \Big (\hat{\pi }^{\ell , t^*}_i \Big ) S_0^{\ell } + \phi _i^{\theta } Y_0^{\theta } \end{aligned}$$

(35)

Replacing $\sum _{t=\ell }^{\theta } \pi _i^t X_0^t$ in Inequalities (30) by its upper bound provided by  (35), we have:

$$\begin{aligned} \alpha _i^{-1}E_i^k + \Big (\hat{\pi }^{\ell , t^*}_i \Big ) S_0^{\ell } + \phi _i^{\theta } Y_0^{\theta } \ge \sum \limits _{t \in U: t\le \tau -1} (d_t-L_t) \end{aligned}$$

(36)

Finally, we have:

$$\begin{aligned} S_0^\ell \hat{\pi }^{\ell , t^*}_i + \alpha _i^{-1}E^k_{i} + \sum \limits _{k < t \le t^*} \phi _i^t Y^t_0&\ge S_0^\ell \hat{\pi }^{\ell , t^*}_i + \alpha _i^{-1}E^k_{i} + \phi _i^{\theta } Y_0^{\theta } + \phi _i^{\tau } Y_0^{\tau } \\&\ge \sum \limits _{t \in U: t\le \tau -1} (d_t-L_t) + \sum \limits _{t \in U: t\ge \tau } (d_t-L_t) \\&\ge \sum \limits _{t \in U } (d_t-L_t) \end{aligned}$$

This concludes the proof of validity for Inequality (23). The same arguments can be used to prove the validity of Inequalities (24) and (25). $\square$

It is worth mentioning that the (k, U) inequalities used in [12] to strengthen the formulation (10)–(22) can be seen as a particular case of the more general family of $(\ell , k,U)$ inequalities (23)–(25) proposed in this work. Namely, by setting $\ell$ to 0 and by computing the value of $\phi ^t$ without taking the returns into account (i.e. by setting $\phi ^t$ to $\sum \limits _{\nu \in U : t \le \nu } d^{\nu }$), each $(\ell , k,U)$ inequality (23)–(25) becomes a (k, U) inequality.

Proposition 2

The linear relaxation of formulation (10)–(22) strengthened by valid inequalities (23)–(25) is at least as tight as the linear relaxation strengthened by the (k, U) valid inequalities used in [12].

Proof

Let $P_{LR}$ be the linear relaxation of polyhedron given by inequalities (11)–(22), (23)–(25) and $\tilde{P}_{LR}$ be the linear relaxation of polyhedron given by inequalities (11)–(22) and the (k, U) inequalities. As any (k, U) inequality is a valid inequality (23)–(25) with $\phi ^t= \sum \limits _{\nu \in U : t \le \nu } d^{\nu }$ and $\ell = 0$, we have $P_{LR} \subseteq \tilde{P}_{LR}$. $\square$

The main implication of Proposition 2 is that the lower bound obtained by strengthening the formulation (10)–(22) with the $(\ell , k,U)$ inequalities is at least as tight as the lower bound obtained while using the single-echelon (k, U) inequalities.

We now briefly discuss the resolution of the separation problem for the $(\ell , k,U)$ valid inequalities. Recall that this problem consists in finding an inequality (23)–(25) violated by a given solution $(\tilde{X}, \tilde{Y}, \tilde{S}, \tilde{E}, \tilde{L}, \tilde{Q})$ of the linear relaxation of Problem (11)–(22) or prove that no such inequality exists. In the present case, in order to find the most violated inequality among e.g. inequalities (23), we should find, for each period $k=1,...,T$, the set U of time periods and the period $\ell$ that maximize the difference between the right-hand and the left-hand side of the inequality. This is not trivial, in particular because the value of each coefficient $\phi ^t_i$ simultaneously depends on U and $\ell$. We thus consider a heuristic separation algorithm in our computational experiments. This one can be summarized as follows. For a given process p and time period k:

• 1. For each period $t=k+1,...,T$, add t to U if $d^t (1-\sum _{\tau =k+1}^t \tilde{Y}_p^{\tau })-\tilde{L}^t>0$.

• 2. For each period $\ell =0,...,k$,

  – compute the value of each coefficient $\phi _i^t = \min \Big \{\sum _{ \ell < \nu \le t} r^{\nu } \hat{\pi }^{\nu , t}_i, \sum _{\nu \in U : t \le \nu } d^{\nu } \Big \}$

  – compute the left-hand side of the inequality (23) (resp. (24) and (25)).

• 3. Set $\ell$ to the period index which minimizes this left-hand side value.

This algorithm has a time complexity of $\mathcal {O}(T^2)$ as the computation of set U in step 1 and of coefficients $\phi _i$ in step 2 both require $\mathcal {O}(T^2)$ operations.

5 Computational Experiments

In this section, we focus on assessing the performance of the proposed valid inequalities when used within a customized branch-and-cut algorithm. We compare the performance of this algorithm with the one of the generic branch-and-cut algorithm embedded in a mathematical programming solver and the one of a branch-and-cut algorithm using single-echelon (k, U) inequalities.

5.1 Instance Generation

We considered two sets of instances: Set 1 instances involve $T=25$ periods and $I=10$ parts whereas Set 2 instances involve $T=35$ periods and $I=10$ parts. Within each set, the instances were randomly generated by adapting the procedure presented in [6]. More precisely, we considered four values of the setup-holding cost ratio $f/h \in \lbrace 600, 1200, 1800, 2400 \rbrace$, two values for the production-holding cost ratio $g/h \in \lbrace 2, 4 \rbrace$ and three values of the returns-demand quantity ratio $r/d \in \lbrace 1,2,3 \rbrace$. For each set and each possible combination of f/h, g/h, r/d, ten random instances were generated, resulting in a total of 480 instances.

For each instance, the value of each problem parameter was set as follows.

• Demand $d^t$ was uniformly distributed in the interval [0, 100] and the returns quantity $r^t$ was uniformly distributed in the interval $[0.8(r/d)\bar{d}, 1.2(r/d)\bar{d}]$, where $\bar{d}=\frac{\sum d^t}{T}$ is the average demand per period.

• The proportion of recoverable parts $\pi _i^t$ was uniformly distributed in the interval [0.4, 0.6].

• The bill-of-materials coefficients $\alpha _i= \alpha _{i+I}, i\in \mathcal {I}_r$, were randomly generated following a discrete uniform distribution over [1; 6] and we set $\alpha _0=\alpha _{2I+1}=1$.

• The holding cost $h^t_0$ for the returned product $i=0$ was fixed to 1. The holding cost $h^t_i$ for each recoverable item $i \in \mathcal {I}_r$ was randomly generated following a discrete uniform distribution over interval [2, 7]. Similarly, the holding cost $h^t_i$ for each serviceable item $i \in \mathcal {I}_s$ was randomly generated following a discrete uniform distribution over interval [7, 12]. Finally, in order to ensure non negative echelon costs, we set the value of the inventory holding cost for the remanufactured product, $h^t_{2I+1}$, to $\sum _{i=1}^I \alpha _i h_{I+i}^t+ \epsilon$, where $\epsilon$ follows a discrete uniform distribution over interval [80, 100].

• The production cost $g^t$ was uniformly distributed in the interval $[0.8(g/h)\bar{h},$ $1.2(g/h)\bar{h}]$, where $\bar{h} = \frac{\sum h^t_{2I+1}}{T}$ is the average holding cost.

• The setup cost $f^t$ was uniformly distributed in the interval $[0.8(f/h)\bar{h}, 1.2(f/h)\bar{h}]$.

• Discarding costs were set to $q_i^t = 0.8\bar{h}^t_i$, where $\bar{h}^t_i = \frac{1}{T} \sum _{\kappa =t}^T h^{\kappa }_i$ The unit penalty cost for lost sales, $l^n$, was fixed to 10000 per

5.2 Results

We carried out extensive numerical experiments in order to assess the computational performance of the proposed valid inequalities. This was achieved by solving each considered instance using three alternatives branch-and-cut algorithms:

• CPX: the generic branch-and-cut algorithm embedded in CPLEX 12.8 using the echelon-stock formulation (11)–(22).

• (k, U): a customized branch-and-cut algorithm using the (k, U) inequalities to strengthen the echelon-stock formulation (11)–(22) similarly to what was done in  [12].

• $(\ell ,k,U)$: a customized branch-and-cut algorithm using the newly introduced $(\ell , k,U)$ inequalities to strengthen the echelon-stock formulation (11)–(22). This algorithm is based on the solver CPLEX 12.8. It generates inequalities of type (23)–(25) through a cutting-plane generation algorithm at the root node and at intermediate nodes of the branch-and-bound search tree using the UserConstraints callbacks provided by the solver.

All related linear programs and mixed-integer linear programs were solved using CPLEX 12.8 with the solver default settings. The algorithms were implemented in C++ using the Concert Technology environment. All tests were run on the computing infrastructure of the Laboratoire d’Informatique de Paris VI (LIP6), which consists of a cluster of Intel Xeon Processors X5690. We set the cluster to use two 3.46 GHz cores and 12 GB RAM to solve each instance. We imposed a time limit of 3600 s.

Table 1. Performance of CPLEX and branch-and-cut methods over instance in Set 1.

Table 2. Performance of CPLEX and branch-and-cut methods over instance in Set 2.

The corresponding results are displayed in Table 1 for Set 1 instances and Table 2 for Set 2 instances. Column Method indicates the branch-and-cut algorithm used to solve the instances. Column $\texttt {R.LP}_{gap}$ reports the gap between the value of the linear relaxation strengthened by the corresponding valid inequalities and the best feasible solution found through the branch-and-bound search. For the CPX method, it reports the gap between the value of the initial linear relaxation and the best feasible solution found through the branch-and-bound search. Column $\texttt {R.MIP}_{gap}$ reports the gap between the lower bound at the root node (after the generation of CPLEX generic cutting planes) and the best feasible solution found through the branch-and-bound search. Column $\texttt {MIP}_{gap}$ reports the gap between the best lower and the best feasible solution found through the branch-and-bound search. The average CPU time for the cutting-plane generation of each method is reported in column C.Time, the CPU time spent at the root node in Column R.Time and the average total CPU time in Column T.Time. Note that each line corresponds to the average value of the corresponding 40 instances.

In general, we observe that the customized branch-and-cut algorithms based either on the (k, U) or on the $(\ell , k,U)$ inequalities outperform method CPX, providing solutions of better quality within shorter computation times. Specifically, the total computation time is reduced on average by 20% when using the branch-and-cut algorithm based on the (k, U) and by 26% when using the branch-and-cut algorithm based on the $(\ell , k, U)$ inequalities.

Regarding the relative performance of the (k, U) and $(\ell ,k,U)$ inequalities, we note that the branch-and-cut algorithm based on the $(\ell ,k,U)$ outperforms the algorithm based on (k, U) when the value of the demand-returns ratio is small, i.e. when $r/d \in \{1,2\}$. Thus, over the 160 instances corresponding to a value of r/d equal to 1, the total average computation time is reduced from1732 s when using (k, U) inequalities to1482 s when using $(\ell ,k,U)$ inequalities. Similarly, over the 160 instances corresponding to a value of r/d equal to 2, the average MIP gap is reduced from 2.72% when using (k, U) inequalities to 2.38% when using $(\ell ,k,U)$ inequalities. We note however that the relative performance of the proposed $(\ell ,k,U)$ inequalities deteriorates for the instances corresponding to the largest considered value of the demand-returns ratio. Namely, when r/d is set to 3, the branch-and-cut algorithm based on the (k, U) inequalities provides a smaller MIP gap and/or smaller computation times. This might be explained by the fact that the corresponding instances involve a large amount of returned products so that the quantity processed on a resource at a given period is not (or at least to a lesser extent) limited by the availability of the returned products. This means that the proposed refinements in the expression of the valid inequalities are less relevant in this case.

6 Conclusion and Perspectives

We considered a lot-sizing problem aiming at planning production for a multi-echelon remanufacturing system. This problem can be formulated as a mixed-integer linear program. We focused on strengthening this formulation in order to be able to provide optimal or near-optimal solutions of this problem. Our main contribution is the development of a new set of valid inequalities which take into account, at each production echelon, the limitations on the produced quantities coming from the limited availability of the returned products. The results of our computational experiments show that a branch-and-cut algorithm based on these new valid inequalities performs well as compared to the generic branch-and-cut algorithm of CPLEX solver and to a previously published branch-and-cut algorithm based on less general valid inequalities.

A first possible research direction could be to develop an exact separation algorithm for the $(\ell , k, U)$ inequalities in the presented branch-and-cut algorithm as this may further improve their performance when used in a branch-and-cut algorithm. Moreover, it would also be worth studying whether valid inequalities previously proposed for capacitated lot-sizing problems (see e.g. [3, 7, 9]) might be useful to help solving our problem. Additional computational experiments are also needed to assess the size of the largest instances that may be solved with the proposed exact solution approach.

On a longer perspective, we could seek to extend the proposed valid inequalities to lot-sizing problems with returns involving complicating features such as a limited capacity, backlogging, safety stocks or minimum production levels. Finally, extending the proposed valid inequalities and the cutting-plane generation to solve the stochastic version of the problem studied in [12] is also worth investigating.