Keywords

1 Introduction

Capacitated lot-sizing arises in industrial production planning whenever change-over operations such as preheating, tool changing or cleaning are required between production runs of different products on a machine. The amount of the related changeover costs usually does not depend on the number of products processed after the changeover. Thus, to minimize changeover costs, production should be run using large lot sizes. However, this generates inventory holding costs as the production cannot be synchronized with the actual demand pattern: products must be held in inventory between the time they are produced and the time they are used to satisfy customer demand. The objective of lot-sizing is thus to reach the best possible trade-off between changeover and inventory holding costs while taking into account both the customer demand satisfaction and the technical limitations of the production system.

An early attempt at modelling this trade-off can be found in [12] for the problem of planning production for a single product on a single resource with an unlimited production capacity. Since this seminal work, a large part of the research on lot-sizing problems has focused on modelling operational aspects in more detail to answer the growing industry need to solve more realistic and complex production planning problems. An overview of recent developments in the field of modelling industrial extensions of lot-sizing problems is provided in [7].

In the present paper, we focus on one of the variants of lot-sizing problems mentioned in [7], namely the multi-product single-resource discrete lot-sizing and scheduling problem or DLSP. As defined in [4], several key assumptions are used in the DLSP to model the production planning problem:

  • A set of products is to be produced on a single capacitated production resource.

  • A finite time horizon subdivided into discrete periods is used to plan production.

  • Demand for products is time-varying (i.e. dynamic) and deterministically known.

  • At most one product can be produced per period and the facility processes either one product at full capacity or is completely idle (discrete production policy).

  • Costs to be minimized are the inventory holding costs and the changeover costs.

In the DLSP, it is assumed that a changeover between two production runs for different products results in a changeover cost. Changeover costs can depend either on the next product only (sequence-independent case) or on the sequence of products (sequence-dependent case). We consider in the present paper the DLSP with sequence-dependent changeover costs (denoted DLSPSD in what follows). Sequence-dependent changeover costs are mentioned in [7] as one of the relevant operational aspects to be incorporated into lot-sizing models. Moreover, a significant number of real-life lot-sizing problems involving sequence-dependent changeover costs have been recently reported in the academic literature: see among others [9] for a textile fibre industry or [3] for soft drink production.

A wide variety of solution techniques from the Operations Research field have been proposed to solve lot-sizing problems: the reader is referred to [2, 6] for recent reviews on the corresponding literature. The present paper belongs to the line of research dealing with exact solution approaches aiming at providing guaranteed optimal solutions for the problem. A large amount of existing exact solution techniques consists in formulating the problem as a mixed-integer linear program (MILP) and in relying on a Branch & Bound type procedure to solve the obtained MILP. However the computational efficiency of such a procedure strongly depends on the quality of the lower bounds used to evaluate the nodes of the search tree. In the present paper, we seek to improve the quality of these lower bounds so as to decrease the total computation time needed to obtain guaranteed optimal solutions for medium-size instances of the problem.

Within the last thirty years, much research has been devoted to the polyhedral study of lot-sizing problems in order to obtain tight linear relaxations and improve the corresponding lower bounds: see e.g. [8] for a general overview of the related literature and [1, 5, 10] for contributions focusing specifically on the DLSP. However, these procedures mainly focus on the underlying single-product subproblems and thus fail at capturing the conflicts between multiple products sharing the same resource capacity. This leads in some cases to significant integrality gaps for multi-product instances of the DLSPSD. In what follows, we propose a new family of multi-product valid inequalities to partially remedy this difficulty and discuss both an exact and a heuristic algorithm to solve the corresponding separation problem. To the best of our knowledge, this is one of the first attempts focusing on improving the polyhedral description of multi-product lot-sizing problems.

The main contributions of the present paper are thus twofold. First we introduce a new family of valid inequalities representing conflicts on multi-period time intervals between several products simultaneously requiring production on the resource. Second we formulate the corresponding separation problem as a quadratic binary program and propose to solve it either exactly by relying on a quadratic programming solver or approximately through a Kernighan-Lin type heuristic algorithm. The results of the preliminary computational results carried out on medium-size instances show that the proposed valid inequalities are efficient at strengthening the linear relaxation of the problem and at decreasing the overall computation time needed to obtain guaranteed optimal solutions of the DLSPSD.

The remainder of the paper is organized as follows. In Sect. 2, we recall the initial MILP formulation of the multi-product DSLPSD and the previously published single-product valid inequalities. We then present in Sect. 3 the proposed new multi-product multi-period valid inequalities and discuss in Sect. 4 both an exact and a heuristic algorithm to solve the corresponding separation problem. Preliminary computational results are discussed in Sect. 5.

2 MILP Formulation

We first recall the initial MILP formulation of the DLSPSD. We use the network flow representation of changeovers between products, which was proposed among others by [1], as this leads to a tighter linear relaxation of the problem. We then discuss the valid inequalities first proposed by [10] to strengthen the underlying single-product subproblems.

2.1 Initial MILP Formulation

We wish to plan production for a set of products denoted \(p=1\ldots P\) to be processed on a single production machine over a planning horizon involving \(t=1\ldots T\) periods. Product \(p=0\) represents the idle state of the machine and period \(t=0\) is used to describe the initial state of the production system.

Production capacity is assumed to be constant throughout the planning horizon. We can thus w.l.o.g. normalize the production capacity to one unit per period and express the demands as binary numbers of production capacity units: see e.g. [4]. We denote \(d_{pt}\) the demand for product \(p\) in period \(t\), \(h_{p}\) the inventory holding cost per unit per period for product \(p\) and \(S_{pq}\) the sequence-dependent changeover cost to be incurred whenever the resource setup state is changed from product \(p\) to product \(q\).

Using this notation, the DLSPSD can be seen as the problem of assigning at most one product to each period of the planning horizon while ensuring demand satisfaction and minimizing both inventory and changeover costs. We thus introduce the following binary decision variables:

  • \(y_{pt}\) where \(y_{pt}=1\) if product \(p\) is assigned to period \(t\), \(0\) otherwise.

  • \(w_{pqt}\) where \(w_{pqt}=1\) if there is a changeover from \(p\) to \(q\) at the beginning of \(t\), \(0\) otherwise.

This leads to the following MILP formulation denoted DLSPSD0 for the problem.

$$\begin{aligned} Z_{LS0} =&min \sum _{p=1}^P\sum _{t=1}^T h_{p} \sum _{\tau =1}^t (y_{p\tau }-d_{p\tau }) + \sum _{p,q=0}^P S_{p,q} \sum _{t=1}^{T-1} w_{p,q,t}&\end{aligned}$$
(1)
$$\begin{aligned}&\sum _{\tau =1}^ty_{p\tau } \ge \sum _{\tau =1}^t d_{p\tau }&\forall p, \forall t \end{aligned}$$
(2)
$$\begin{aligned}&\sum _{p=0}^P y_{pt} =1,&\forall t \end{aligned}$$
(3)
$$\begin{aligned}&y_{p,t}=\sum _{q=0}^P w_{q,p,t}&\forall p, \forall t \end{aligned}$$
(4)
$$\begin{aligned}&y_{p,t}=\sum _{q=0}^P w_{p,q,t+1}&\forall p, \forall t \end{aligned}$$
(5)
$$\begin{aligned}&y_{pt} \in \{0,1\}&\forall p, \forall t \end{aligned}$$
(6)
$$\begin{aligned}&w_{p,q,t} \in \{0,1\}&\forall p,\forall q, \forall t \end{aligned}$$
(7)

The objective function (1) corresponds to the minimization of the inventory holding and changeover costs over the planning horizon. \(\sum _{\tau =1}^t (y_{p\tau }-d_{p\tau })\) is the inventory level of product \(p\) at the end of period \(t\). Constraints (2) impose that the cumulated demand over interval \([1,t]\) is satisfied by the cumulated production over the same time interval. Constraints (3) ensure that, in each period, the resource is either producing a single product or idle. Constraints (4)–(5) link setup variables \(y_{pt}\) with changeover variables \(w_{pqt}\) through equalities which can be seen as flow conservation constraints in a network. They ensure that in case product \(p\) is setup in period \(t\), there is a changeover from another product \(q\) (possible \(q=p\)) to product \(p\) to at the beginning of period \(t\) and a changeover from product \(p\) to another product \(q\) (possible \(q=p\)) at the end of period \(t\).

2.2 Single-Product Valid Inequalities

We now recall the expression of the valid inequalities proposed by [10] for the single product DLSP. We denote \({d}_{p,t,\tau }\) the cumulated demand for product \(p\) in the interval \(\{t,\ldots ,\tau \}\) and \(\Delta _{p,v}\) the \(vth\) positive demand period for product \(p\). \(\Delta _{p,d_{p,1,t}+v}\) is thus the period with the \(vth\) positive unit demand for product \(p\) after period \(t\) occurs.

$$\begin{aligned} \sum _{\tau =1}^t (y_{p\tau }-d_{p\tau }) + \sum _{v=1}^{w} \Bigl [ y_{p,t+v}&+ \sum _{\tau =t+v+1}^{\Delta _{p,d_{p,1,t}+v}} \sum _{q \ne p} w_{q,p,\tau }\Bigr ] \ge w \nonumber \\&\qquad \qquad \qquad \forall p, \forall t, \forall w \in [1, d_{p, t+1, T}] \end{aligned}$$
(8)

The idea underlying valid inequalities (8) is to compute a lower bound on the inventory level of a product \(p\) at the end of a period \(t\), \(\sum _{\tau =1}^t (y_{p\tau }-d_{p\tau })\), by considering both the demands and the resource setup states for this product in the forthcoming periods \(\tau =t+1...\Delta _{p,d_{p,1,t}+v}\). The reader is refered to [10] for a full proof of validity for these inequalities. In the computation experiments to be presented in Sect. 5, we use a standard cutting-plane generation algorithm to strengthen the formulation DLSPSD0 by adding violated valid inequalities of family (8). The resulting improved formulation is denoted DLSPSD1.

Constraints (8) can be understood as a way to strengthen the demand satisfaction constraints (2) by expressing in a more detailed way the need for each individual product to access the resource in order to satisfy its own demand on a given subinterval of the planning horizon. However, in the resulting DLSPSD1 formulation, the conflicts between different products simultaneously requiring production on the resource will only be handled by the single-period capacity constraints (3). In what follows, we propose to improve this representation of the conflicts between different products by considering multi-period multi-product valid inequalities.

3 New Multi-product Valid Inequalities

We now present the multi-period multi-product valid inequalities we propose to strengthen the linear relaxation of the multi-product DLSPSD.

Proposition 1

Let \(SP \subset \{0...P\}\) be a subset of products.

Let \(t \in [1,T]\) be a period within the planning horizon. Let \((\theta _1,..., \theta _p,...,\theta _{P}) \in [0,T]^P\) be a set of periods such that \(\theta _p < t\) if \(p \in SP\). For each period \(\tau \in [1,T]\), we denote \(SD_{\tau } = \{p=1...P | \theta _p > \tau \}\).

The following inequalities are valid for the multi-product DLSPSD.

$$\begin{aligned} \Bigl [ \sum _{q=1}^P d_{q,1,\theta _q}\Bigr ] \Bigl [ \sum _{p \in SP} y_{pt} \Bigr ] \le \sum _{\tau =1}^T \tilde{C}_{\tau } \end{aligned}$$
(9)

where \(\tilde{C}_{\tau }\) is defined by:

$$\begin{aligned} \tilde{C}_{\tau }&= min \Bigl (\sum _{q \in SD_{\tau }} y_{q,\tau }, \sum _{p \in SP} y_{p,t}\Bigr )\text { if } \tau \notin [t-1 ; t+1] \nonumber \\ \tilde{C}_{t-1}&= \sum _{q \in SD_{t-1}, p \in SP} w_{qpt} \nonumber \\ \tilde{C}_{t}&= 0 \nonumber \\ \tilde{C}_{t+1}&= \sum _{p \in SP, q \in SD_{t+1}} w_{pq,t+1} \nonumber \end{aligned}$$

Before providing the proof for Proposition 1, we briefly explain the idea underlying valid inequalities (9). We choose a subset \(SP\) of products. If none of these products is assigned for production in period \(t\) (i.e. \(\sum _{p \in SP} y_{pt}=0\)), all corresponding valid inequalities are trivially respected. But if one of these products is produced in period \(t\) (i.e. \(\sum _{p \in SP} y_{pt}=1\)), then we have to make sure that we are able to satisfy the total cumulated demand \(\sum _{q=1}^P d_{q,1,\theta _q}\) on the remaining periods \(1...t-1, t+1...T\). In this case, the right hand side of inequalities (9) computes a tight upper bound (\(\sum _{\tau =1}^T \tilde{C}_{\tau }\)) of the total production capacity remaining to satisfy this cumulated demand.

Proof

Let \((y, w)\) be a feasible solution of the DLSPSD. We arbitrarily choose a subset of products \(SP\), a period \(t\) and a vector of periods \((\theta _1,..., \theta _p,...,\theta _{P})\) such that \(\theta _p < t\) if \(p \in SP\) and show that all proposed inequalities (9) are valid for the considered feasible solution.

We distinguish two main cases:

  • Case 1: \(\sum _{p \in SP} y_{pt}=0\) In this case, the left hand side of the inequalities is equal to 0 whereas the right hand side is nonnegative. All inequalities (9) are thus trivially true.

  • Case 2: \(\sum _{p \in SP} y_{pt}=1\) In this case, the left hand side of inequalities (9) is equal to the total cumulated demand over intervals \([1,\theta _q]\) for products \(q=1..P\), i.e. to \(\sum _{q=1}^P d_{q,1,\theta _q}\).

\(\sum _{p \in SP} y_{pt}=1\) means that period \(t\) is devoted to the production of one of the products in \(SP\). As we have \(\theta _p < t\) for each product \(p\in SP\), period \(t\) cannot be used to satisfy the cumulated demand \(d_{p,1,\theta _p}\) of any product in \(SP\). Hence \((y, w)\) can be a feasible solution of the DLSPSD if and only if the remaining total cumulated production capacity over the periods \(1...t-1, t+1...T\) is sufficient to satisfy the cumulated demand \(\sum _{q=1}^P d_{q,1,\theta _q}\).

We now seek to compute a tight upper bound for the production capacity \(C_{\tau }\) available in each period \(\tau \in [1,t-1] \cap [t+1,T]\) to satisfy the cumulated demand \(\sum _{q=1}^P d_{q,1,\theta _q}\):

  • By capacity constraints (3), we have \(C_{\tau } \le 1\), i.e. \(C_{\tau } \le \sum _{p \in SP} y_{pt}\).

  • Moreover, the cumulated demand \(d_{q,1,\theta _{q}}\) for a product \(q\) can only be satisfied by a production for \(q\) in period \(\tau \) if \(\tau \le \theta _{q}\) as demand backlogging is not allowed here. Hence period \(\tau \) can be used to satisfy part of demand \(\sum _{q=1}^P d_{q,1,\theta _{q}}\) only if the resource is setup for one of products \(q=1..P\) such that \(\tau \le \theta _{q}\). This gives \(C_{\tau } \le \sum _{q \in SD_{\tau }} y_{q,\tau }\).

We thus obtain \(C_{\tau } \le min(\sum _{q \in SD_{\tau }} y_{q,\tau }, \sum _{p \in SP} y_{pt})\) \(\forall \tau \in [1,t-1] \cap [t+1,\theta ]\).

Now, we can exploit our knowledge of the setup state of the resource in period \(t\) to further strengthen these inequalities. Namely, we know that a product \(p\) belonging to \(SP\) is produced in period \(t\). A changeover to (resp. from) this product \(p\) thus has to take place at the beginning (resp. at the end) of period \(t\). This means that:

  • If period \(t-1\) is to be used to satisfy the demand of one of the products belonging to \(SD_{t-1}\), there must be a changeover from this product \(q \in SD_{t-1}\) to the product \(p \in SP\) at the beginning of period \(t\). The production capacity available in period \(\tau =t-1\) for the products in \(SD_{t-1}\) is thus limited by \(C_{t-1} \le \sum _{ p\in SP,q\in SD_{t-1}} w_{q,p,t}\).

  • Similarly, if period \(t+1\) is to be used to satisfy the demand of one of the products belonging to \(SD_{t+1}\), there must be a changeover from the product \(p \in SP\) to this product at the end of period \(t\). The production capacity available in period \(\tau =t+1\) for the products in \(SD_{t+1}\) is thus limited by \(C_{t+1} \le \sum _{p\in SP, q\in SD_{t+1}} w_{p,q,t+1}\).

We can thus strengthen the upper bound of \(C_{t-1}\) (resp \(C_{t+1}\)) by replacing the term \(min(\sum _{q \in SD_{\tau }} y_{q,\tau }, \sum _{p \in SP} y_{pt})\) by \(\sum _{p\in SP, q\in SD_{t-1}} w_{q,p,t}\) (resp. \(\sum _{p\in SP, q\in SD_{t+1}}\) \(w_{p,q,t+1}\))

and obtain the inequalities (9) discussed in Proposition 1.

4 Separation Problem

The number of valid inequalities (9) grows very fast with the problem size. It therefore not possible to include them a priori in the MILP formulation of the problem. This is why we use a cutting-plane generation strategy to add to the MILP formulation only the most violated valid inequalities of the family. This requires solving the corresponding separation algorithm which, given a fractional solution \((\overline{y}, \overline{w})\) of the DLSPSD, will either identify a violated valid inequality or prove that no such inequality exists.

4.1 Exact Separation Algorithm

We first discuss an exact separation algorithm, i.e. an algorithm which is guaranteed to find an inequality violated by a fractional solution \((\overline{y}, \overline{w})\) of the DLSPSD if one exists. We consider each period \(t\) and seek to identify the subset \(SP\) and the vector \((\theta _1,..., \theta _p,...,\theta _{P})\) which provide the largest violation of inequalities (9). To achieve this, we formulate the separation problem for a given \(t\) as follows.

We introduce the following decision variables:

  • \(\alpha _p = 1\) if product \(p \in SP\), 0 otherwise.

  • \(\beta _{q,\theta } = 1\) if \(\theta _q=\theta \), 0 otherwise.

  • \(\gamma _{\tau }=1\) if capacity \(C_{\tau }\) is limited by \(\sum _{p=0}^P \overline{y_{pt}} \alpha _p\), 0 if \(C_{\tau }\) is limited by \(\sum _{q=0}^P \sum _{\theta =\tau }^T \overline{y_{q,\tau }} \beta _{q,\theta }\).

With this notation, the separation problem \(QBP_t\) for a given \(t\) and a solution \((\overline{y}, \overline{w})\) is formulated as:

$$\begin{aligned} max&\sum _{p=0}^P \sum _{q=1}^P \sum _{\theta =1}^T d_{q, 1, \theta } \overline{y_{pt}} \alpha _p \beta _{q,\theta }- \sum _{p=0}^P \sum _{q=1}^P \sum _{\theta =t-1}^T \overline{w_{q,p,t}} \alpha _p \beta _{q,\theta }&\nonumber \\&- \sum _{p=0}^P \sum _{q=1}^P \sum _{\theta =t+1}^T \overline{w_{p,q,t+1}} \alpha _p \beta _{q,\theta }&\nonumber \\&- \sum _{\begin{array}{c} \tau =1...t-2 t+2... \theta \end{array}} \Bigl [ \sum _{p=0}^P \overline{y_{pt}} \alpha _{p} \gamma _{\tau } + \sum _{q=1}^P \sum _{\theta =\tau }^T \overline{y_{q,\tau }} \beta _{q,\theta } (1-\gamma _{\tau }) \Bigr ]&\end{aligned}$$
(10)
$$\begin{aligned}&\alpha _p + \sum _{\theta =t}^T \beta _{p,\theta } \le 1&\forall p \end{aligned}$$
(11)
$$\begin{aligned}&\sum _{\theta =0}^T \beta _{p,\theta } = 1&\forall p \end{aligned}$$
(12)
$$\begin{aligned}&\alpha _p \in \{0,1\}&\forall p&\end{aligned}$$
(13)
$$\begin{aligned}&\beta _{p,\theta } \in \{0,1\}&\forall p,\forall \theta&\end{aligned}$$
(14)
$$\begin{aligned}&\gamma _{\tau } \in \{0,1\}&\forall \tau&\end{aligned}$$
(15)

The objective function (10) corresponds to the maximimization of the violation of the inequalities, i.e. we seek to identify \(SP\) and\((\theta _1,..., \theta _p,...,\theta _{P})\) so as to maximize the difference between the left and the right hand side of the inequality. If this value is strictly positive, we obtain a violated valid inequality. In case this value is less than or equal to 0, it means that all valid inequalities for period \(t\) are satisfied by the fractional solution \((\overline{y}, \overline{w})\). Constraints (11) state that for a given product \(p\), we cannot simultaneously include it in \(SP\) and choose a period \(\theta _p\) such that \(\theta _p \ge t\). Constraints (12) guarantee that for each product \(p\), exactly one value of \(\theta _{p}\) is chosen .

Problem \(QBP_{t}\) is a binary program with a quadratic objective function and a series of linear constraints. It can be solved to optimality by a quadratic binary programming solver such as the one embedded in CPLEX 12.5.

4.2 Heuristic Separation Algorithm

As can be seen from the computational experiments to be presented in Sect. 5, solving to optimality a sequence of quadratic binary programs \(QBP_{t}\) leads to prohibitively long computation times for the cutting-plane generation algorithm, even for small-size instances. We are thus currently investigating the development of a heuristic separation algorithm capable of identifying violated valid inequalities more quickly.

We discuss here a first version of this separation algorithm which focuses on a special case of the proposed multi-product valid inequalities. This special case consists in choosing a period \(\theta \) such that \(\theta \ge t\), in restricting the possible values for periods \(\theta _1\),..., \(\theta _p\),...,\(\theta _{P}\) to the set \(\{0,\theta \}\) and in imposing \(\theta _p=0\) if \(p \in SP\).

In this case, for a given pair of periods \((t,\theta )\), the separation problem amounts to finding a tripartition of the set of products \(\{0...P\}\) into 3 subsets: \(SP\), \(SDem_{\theta }=\{q=1..P|\theta _q= \theta \}\) and \(SDem_{0} = \{q=1..P|\theta _q=0\}\) such that the quadratic expression (10) is maximized. This problem shares some common features with graph partitioning problems. We therefore propose to solve it using the following Kernighan-Lin type heuristic as this type of algorithm is known to be rather efficient at solving graph partitioning problems.

figure a

The neighbourhood of a tripartition \(\varPi \) of \(\{0...P\}\) is defined as the set of tripartitions obtained by moving a single product from its current subset in \(\varPi \) to one of the two other subsets. Moreover, in the computational experiments to be presented in Sect. 5, five different types of partitions are used to initialize the heuristic.

4.3 Cutting-Plane Generation Algorithm

We now briefly describe the cutting-plane generation used to strengthen formulation DLSPSD1 by adding to it some multi-product valid inequalities (9).

figure b

5 Computational Results

We now discuss the results of some preliminary computational experiments carried out to evaluate the effectiveness of the proposed multi-product valid inequalities at strengthening the formulation of the multi-product DLSPSD and to assess their impact on the total computation time.

We randomly generated instances of the problem using a procedure similar to the one described in [11] for the DLSP with sequence-dependent change-over costs and times. More precisely, the various instances tested have the following characteristics:

  • Problem dimension. The problem dimension is represented by the number of products P and the number of periods T: we solved medium-size instances involving 4–10 products and 15–75 periods.

  • Inventory holding costs. For each product, inventory holding costs have been randomly generated from a discrete uniform \(DU(5,10)\) distribution.

  • Changeover costs. We used two different types of structure for the changeover cost matrix \(S\). Instances of sets A1–A7 have a general cost structure: the cost of a changeover from product \(p\) to product \(q\), \(S_{pq}\), was randomly generated from a discrete uniform \(DU(100,200)\) distribution. Instances of sets B1–B7 correspond to the frequently encountered case where products can be grouped into product families: there is a high changeover cost between products of different families and a smaller changeover cost between products belonging to the same family. In this case, for products \(p\) and \(q\) belonging to different product families, \(S_{pq}\) was randomly generated from a discrete uniform \(DU(100,200)\) distribution; for products \(p\) and \(q\) belonging to the same product family, \(S_{pq}\) was randomly generated from a discrete uniform \(DU(0,100)\) distribution.

  • Production capacity utilization. Production capacity utilization \(\rho \) is defined as the ratio between the total cumulated demand (\(\sum _{p=1}^P \sum _{t=1}^T d_{pt}\)) and the total cumulated available capacity (\(T\)). We set \(\rho =0.95\) for all instances.

  • Demand pattern. Binary demands \(d_{pt} \in \{0,1\}\) for each product have been randomly generated according to the a procedure similare to the used by [11].

For each considered problem dimension, we generated 10 instances, leading to a total of 140 instances.

All tests were run on an Intel Core i5 (2.7 GHz) with 4 GB of RAM, running under Windows 7. We used a standard MILP software (CPLEX 12.5) with the solver default settings to solve the problems with one of the following formulations:

  • DLPSD1: initial MILP formulation DLSPSD0, i.e. formulation (1)–(7), strengthened by single-product valid inequalities (8). We used a standard cutting-plane generation strategy based on a complete enumeration of all possible valid inequalities to add them into the formulation.

  • DLSPSD2e: formulation DLSPSD1 strengthened by multi-product valid inequalities (9). We used the cutting-plane generation algorithm presented in Sect. 4.3 to add only the most violated valid inequalities and relied on the exact separation algorithm discussed in Sect. 4.1.

  • DLSPSD2h: formulation DLSPSD1 strengthened by multi-product valid inequalities (9). We used the cutting-plane generation algorithm presented in Sect. 4.3 to add only the most violated valid inequalities and relied on the heuristic separation algorithm discussed in Sect. 4.2.

Tables 1 and 2 display the computational results. We provide for each set of 10 instances:

  • \(P\) and \(T\): the number of products and planning periods involved in the production planning problem.

  • \(V\) and \(Cst\): the number of variables and constraints in the initial formulation DLSPSD0.

  • \(SP\): the number of single-product violated valid inequalities (8) added in the three formulations.

  • \(MPe\) and \(MPh\): the number of multi-product violated valid inequalities added in formulation DLSPSD2e by the exact separation algorithm and in formulation DLSPSD2h by the heuristic separation algorithm.

  • \(Gap_{LP1}\) (resp. \(Gap_{LP2e}\), \(Gap_{LP2h}\)): the average percentage gap between the linear relaxation of formulation DLSPSD1 (resp. DLSPSD2e, DLSPSD2h) and the value of an optimal integer solution.

  • \(N_{IP1}\) (resp. \(N_{IP2e}\), \(N_{IP2h}\)): the average number of nodes explored by the Branch & Bound procedure before a guaranteed optimal integer solution is found or the computation time limit of 2700 s is reached.

  • \(T_{IP1}\) (resp. \(T_{IP2e}\), \(T_{IP2h}\)): the total computation time (cutting-plane generation and Branch & Bound search) needed to find a guaranteed optimal integer solution (we used the value of 2700s in case a guaranteed optimal integer solution could not be found within the computation time limit).

Table 1. Preliminary computational results: exact separation algorithm.
Full size table
Table 2. Preliminary computational results: heuristic separation algorithm.
Full size table

Results from Table 1 show that the proposed valid inequalities (9) are efficient at strengthening formulation DLSPSD1. Namely, the integrality gap is reduced from an average of 5.3 % with formulation DLSPSD1 (see \(Gap_{LP1}\)) to an average of 0.3 % with formulation DLSPSD2e (see \(Gap_{LP2e}\)). We note that this reduction is particularly significant for instances B1–B3 featuring a product family changeover cost structure. Moreover this formulation strengthening is obtained thanks to a relatively small number of multi-product inequalities as can be seen from the average value of \(MPe\) (12). However, even if the number of nodes needed by the Branch & Bound procedure to find a guaranteed optimal solution is slightly reduced when using formulation DLSPSD2e, it does not lead to an overall reduction of the computation time. This is mainly explained by the fact that the cutting-plane generation algorithm based on an exact separation algorithm requires prohibitively long computation times to identify the violated multi-product valid inequalities to be added to the formulation. It is thus necessary to resort to a heuristic separation algorithm such as the one proposed in Sect. 4.2.

Comparison of the results obtained with the exact and the heuristic separation algorithm for the instances A1–A3 and B1–B3 (Tables 1 and 2) shows that the proposed heuristic is efficient at finding violated valid inequalities for small size instances. Namely, the average integrality gap for these 60 instances when using the heuristic algorithm is the \(Gap_{LP2h} = 0.5\,\%\) which is close to the one obtained when using the exact algorithm (\(Gap_{LP2e} = 0.3\,\%\)). Moreover, the number of violated valid inequalities found by the heuristic algorithm is nearly the same as the number of violated valid inequalities found by the exact algorithm.

Results from Table 2 also confirm that the proposed heuristic is rather efficient at finding violated valid inequalities for larger instances. This can be seen by looking at the results for instances A4–A7 and B4–B7. We first note that, for these instances, the integrality gap is reduced from an average of 7.9 % while using formulation DLSPSD1 to an average of 4.7 % while using formulation DLSPSD2h. Moreover a significant decrease in the overall computation time is obtained for instances B4–B7 when using formulation DLSPSD2h.

6 Conclusions

We considered the multi-product discrete lot-sizing and scheduling problem with sequence-dependent changeover costs and proposed a new family of multi-product valid inequalities for this problem. This enabled us to better take into account in the MILP formulation the conflicts between different products simultaneously requiring production on the resource. We then presented both an exact and a heuristic separation algorithm in order to identify the most violated valid inequalities to be added in the initial MILP formulation within a cutting-plane generation algorithm. Our preliminary results show that the proposed valid inequalities are efficient at strengthening the MILP formulation and that their use leads to a significant reduction of the overall computation time for instances featuring a product family changeover cost structure. Research work is currently ongoing in order to extend the proposed heuristic separation algorithm so as to identify violated valid inequalities from the whole family.