A cross entropy-Lagrangean hybrid algorithm for the multi-item capacitated lot-sizing problem with setup times

Abstract

The aim of this article is to introduce a hybrid algorithm for the multi-item multi-period capacitated lot-sizing problem with setups. In this problem, demands over a finite planning horizon must be met, where several items compete for space with limited resources in each period, and a portion of these resources is used by setups. The proposed scheme considers a Lagrangean relaxation of the problem and applies a cross entropy-based metaheuristic to the uncapacitated version of the original problem. A thorough experimental plan has been designed and implemented to test the effectiveness and the robustness of the algorithm: first, drawing inspiration from the response surface methodology, we calibrate the algorithm by identifying the optimal parameters value for any given instance size. Next, we carry out experiments on large scale instances, collecting information about solution quality and computational time, and comparing these results with those offered by a global optimizer.

Introduction

The multi-item multi-period capacitated lot-sizing problem with setups (MCLS) is a well known optimization problem that finds a wide variety of applications in real-world problems. It is a well-known fact that MCLS is an $\mathcal{NP}$-hard problem [1], [2], [3]. For this reason, the problem is both challenging from the computational point of view as well as interesting from the real-world applicability perspective. In this paper, we propose a new metaheuristic-based algorithm for MCLS, along with some insight about how to fine-tune the proposed metaheuristic algorithm.

This section is organized as follows: first, the mathematical formulation is presented; next, a thorough literature review is offered, and, finally, an overview of the proposed scheme and of the overall paper is introduced.

A mixed-integer formulation of the problem is

$$(\text{MCLS}):\min \sum _{j=1}^P\sum _{t=1}^T(c_{\mathit{jt}}{y}_{\mathit{jt}}+f_{\mathit{jt}}{x}_{\mathit{jt}}+h_{\mathit{jt}}{s}_{\mathit{jt}})\text{s.t.}\sum _{j=1}^P(a_{\mathit{jt}}{y}_{\mathit{jt}}+m_{\mathit{jt}}{x}_{\mathit{jt}})⩽b_t,t=1,2,\dots ,T\text{,}{y}_{\mathit{jt}}+s_{j,t-1}-s_{\mathit{jt}}=d_{\mathit{jt}},j=1,2,\dots ,P,t=1,2,\dots ,T\text{,}{y}_{\mathit{jt}}⩽{\mathit{Mx}}_{\mathit{jt}},j=1,2,\dots ,P,t=1,2,\dots ,T\text{,}{y}_{\mathit{jt}},s_{\mathit{jt}}⩾0,x_{\mathit{jt}}\in \{0,1\},j=1,2,\dots ,P,t=1,2,\dots ,T\text{.}$$

In this model, P and T stand for the number of items and the number of periods in the planning horizon, respectively. The model presents two groups of continuous variables, which account for the production and the inventory level of each item in each period ($y_{\mathit{jt}}$ and $s_{\mathit{jt}}$, respectively). In addition, a group of binary variables $x_{\mathit{jt}}$ is used to indicate whether any positive quantity of item j is produced during period t. Parameters $c_{\mathit{jt}}$, $f_{\mathit{jt}}$, and $h_{\mathit{jy}}$ stand for unitary production cost, setup cost, and inventory cost for item j during period t, respectively. Production capacity during period t, e.g., available production time, is indicated by $b_t$. Finally, $a_{\mathit{jt}}$ and $m_{\mathit{jt}}$ represent the unitary production time and the setup time for product j during period t, respectively. The first set of constraints accounts for the production capacity limit over the periods and ensures that the overall production does not require more than the available capacity. The second set of constraints, inventory balance constraints, ensures that, for each period and each item, demands are satisfied. Finally, the third set of constraints ensures that appropriate setup costs are paid if some positive production is taken. An illustrative example, along with a graphical representation of the lot sizing problem over a number of time periods is presented in Nemhauser and Wolsey [3].

Due to its vast industrial applicability, researchers have devoted special attention to MCLS (see [4], [5], [6], [7]). The problem is complicated by the existence of setup costs as well as inventory costs. For this reason, a trade off exists between producing an item at every period, and, consequently, paying less inventory but more setup, or producing more sparingly, hence paying less setup but more inventory. Since the multi-item capacitated lot-sizing problem with setups is very difficult to solve to optimality, many researchers have tried to tackle the problem by working on relaxations of the same. A good description of some well studied relaxations of MCLS is provided by Miller et al. [8].

Two main approaches can be identified in the currently available literature. On the one hand, a number of authors have tried to tackle the problem from a general perspective, either defining tighter formulations or via valid inequalities generation. Generally speaking, when the linear programming relaxation of an MIP problem is tight, the optimal objective value of such problem is close to the optimal value of the integer problem. Consequently, a branch and bound-based algorithm could efficiently solve the integer problem. These approaches, typically proposed in the 1980s and early 1990s are inherently flexible, and thus can easily be adapted to solve a wide range of MIP problems, including the MCLS problem. On the other side of the spectrum we find specialized algorithms, mainly based upon Lagrangean relaxation along with an ad hoc heuristic. While these algorithms typically require a good deal of modifications even for small changes in the model, they are more efficient than any general approach and can be used to solve larger instances in a shorter computational time. Recent contributions have been focused on such avenue of research, proposing ad hoc algorithms for MCLS able to efficiently solve instances with tens of thousand of variables.

As an example of what can be seen as a ‘general approach’, Eppen and Martin [5] formulate the capacitated lot-sizing problem as a shortest route problem and solve such network problem using a standard “off-the-shelf” solver. The general idea of the paper is to exploit the structure of the subproblem (uncapacitated lot sizing) to define a tighter formulation. It is worth noting that the linear programming relaxation of the model resulting from variable redefinition produces bounds equal to those of the Lagrangean relaxation. They solve MCLS problems with up to 200 products and 10 periods in a reasonable amount of computational time.

Similarly, Pochet and Wolsey [6] present different variants of the lot-sizing problem. Their approach is based upon the generation of valid inequalities that strengthen the linear programming formulation. In turn, good bounds provided by the LP relaxation foster the effectiveness of a branch and bound-based approach for the general lot-sizing problem. The authors present results on instances with up to five items and 12 periods, which are solved to optimality in a short amount of computational time.

Some other studies, concerning the construction of valid inequalities, have been developed by Miller et al. [8]. This author provides studies on valid inequalities for different relaxations of MCLS, namely the single-item multi-period and the multi-item single-period lot-sizing problems. With respect to the single-item problem, further indications are provided in [6], [9], [10].

In a different study, Miller et al. [11] present a special case of the multi-item single-period capacitated lot sizing problem with setups, where setup times and demands are constant for all items. For this special case, the authors provide a polynomial time algorithm. They prove that the inequalities identified in Miller et al. [12] suffice to solve such problem by linear programming in polynomial time.

Another study on valid inequalities is the one presented in Loparic et al. [13]. They derive facet-defining inequalities for the dynamic knapsack set as well as for the single-item capacitated lot-sizing problem. Computational results offered are quite limited, even though the major point made by the authors is that dynamic knapsack inequalities and their generalizations provide strong valid inequalities for the lot-sizing problem.

Along the same line, Magnanti and Sastry [14] present a study of different scheduling problems. They first derive valid inequalities for the single-item capacitated lot-sizing problem and, subsequently, apply their findings to the multi-item version. They offer an interesting comparison of different strategies, providing a measure of the tightness of the LP model with four families of valid inequalities. Computational results with up to five products and 30 periods are presented. For all these instances, at least one of the proposed formulations with valid inequalities closes the gap between the LP relaxation and the MIP problem.

Considering specialized approaches to MCLS, the seminal work of Trigeiro et al. [2] illustrate how Lagrangean relaxation coupled with subgradient optimization can be used to solve small-medium size instances of MCLS. For each Lagrangean vector, they apply a dynamic programming algorithm to independently solve to optimality a series of uncapacitated lot-sizing problems, one for each item. If the Lagrangean solution is not feasible, a smoothing procedure is applied in order to restore feasibility whenever possible. They present results on random generated instances with up to 24 items and 30 periods. In order to evaluate the goodness of the algorithm, they perform a detailed analysis of the solution gap, computed as distance between the integer solution and the best lower bound. Such gap averaged less than 4%, when computed on instances with a number of items between 6 and 24 and a number of periods between 15 and 30.

Diaby et al. [15] present an ad hoc Lagrangean-based algorithm for large scale MCLS problems that achieves excellent results. They apply Lagrangean relaxation with subgradient optimization to get good lower bounds and then use a branch and bound scheme to obtain the optimal solution to the problem. They solve instances with thousands of items within a 1% of their optimal solution.

Tempelmeier and Derstoff [16] tackle MCLS in a similar way, decomposing the original problem in a set of uncapacitated problems that are solved to optimality. They solve MCLS as the core planning step of the broader Material Requirements Planning system and consider the multi-level version of the problem, where one item is composed of a number of subassembly operations.

In a different study, Katok et al. [17] propose a two-phase algorithm for MCLS. The first phase is aimed at finding a good feasible solution via a Coefficient Modification Heuristic. Next, an LP problem with added constraints is solved to improve the first stage solution. They solve problems with up to 5000 variables and obtain solutions which average 25% better than solutions obtained with a commercial solver in a fixed amount of computational time.

The approach presented by Hindi et al. [18] is interesting for its use of a metaheuristic scheme within a Lagrangean relaxation scheme solved via subgradient optimization. Furthermore, these authors provide an interesting explanation of why the MCLS problem is much more difficult than its counterpart without setup times. The algorithm uses a smoothing heuristic embedded into a Lagrangean relaxation scheme coupled with a variable neighborhood local search scheme. The solution found by the smoothing scheme is further improved by taking it as starting point for a variable neighborhood search algorithm. The proposes heuristic is effectively used to tackle problems with up to 24 items and 30 periods.

In a different study, Sambasivan and Schmidt [19] apply the Lagrangean relaxation technique to the multi-level version of the MCLS problem, which is, the lot-sizing problem with multiple plants. The relaxed problem is solved using an efficient heuristic developed by the authors. Random generated instances are then solved to show the effectiveness of the proposed algorithm.

Finally, we present two metaheuristic-based scheme for the MCLS since a more direct comparison with our algorithm can be performed. Gopalakrishnan et al. [20] present a Tabu Search heuristic for the capacitated lot-sizing problem with the variant of setup carryover, in which carrying items from one period to the next requires the payment of a setup cost. They define a number of dynamic moves and allow the partial exploration of the infeasible space. Finally, they introduce a lower bounding heuristic to improve the quality of the tabu search solution. The algorithm was tested on 751 instance problems from Trigeiro et al. [2], where the setup carryover is set to zero.

The mayor contribution of this paper concerns the development of an hybrid scheme that reduces MCLS to a series of uncapacitated lot-sizing problems (ULS), each one of them effectively solved using the meritorious cross entropy (CE) paradigm. This work is based upon some of the findings of Caserta et al. [21], in which the integer knapsack problem with setup was effectively solved using the a CE-based scheme. The integer knapsack problem with setup is viewed as a particular case of the multi-item capacitated lot-sizing problem with setup times, as presented in Miller et al. [8] and, consequently, the CE scheme presented in this paper draws inspiration from the scheme proposed for the knapsack problem. In this paper, we will show that, after dualizing the capacity constraints, MCLS reduces to a set of $P$ uncapacitated lot-sizing problems that can be separately solved using the CE framework. Hence, MCLS is solved by progressively determining “good” Lagrangean multipliers so that the joint solution of the set of ULS problems is feasible to MCLS. Furthermore, the paper illustrates how statistical techniques, such as the response surface methodology, can be used to perform a good calibration of the metaheuristic algorithm. This analysis will help to identify the relation between instances’ characteristics and problem difficulty.

This paper has the following structure: Section 2 illustrates how the CE paradigm can be adapted to solve uncapacitated lot-sizing problems. Next, Section 3 presents the overall dual scheme used to tackle MCLS, which is, it shows how the CE scheme is embedded into the Lagrangean Optimization phase. In Section 4 we present a greedy scheme used to project a Lagrangean solution, infeasible to MCLS, into the feasible space of the problem. This scheme is used to derive a feasible solution at every Lagrangean iteration. Section 5 is devoted to the presentation of the experimental plan, designed with a two-fold objective in mind: on the one hand, it will be shown how the Cross Entropy-based algorithm is calibrated while, on the other hand, we will prove the effectiveness of the proposed scheme on very large scale instances of MCLS. Finally, Section 6 presents some concluding remarks and possible future works.