Groupe d’études et de recherche en analyse des décisions

G-2021-49

Formulations and exact solution approaches for a coupled bin-packing and lot-sizing problem with sequence-dependent setups

, , et

We study bin-packing and lot-sizing decisions in an integrated way. Such a problem appears in several manufacturing settings where items first need to be cut and next assembled into final products. One of the main novelties of this research is the modeling of the complex setup operations for the cutting process. More specifically, we consider the operation regarding the insertion or removal of the knives in the cutting process. Since this operation depends on the number of items cut in the current cutting process and in the previous one, the number of insertions and removals is sequence-dependent. The setups in the lot-sizing problem related to the production of the final products are also sequence-dependent. To deal with such a problem, two compact formulations are proposed, which are based on the assignment variables to model the bin-packing decisions. The sequence-dependent setups in the bin-packing problem are modeled in two different ways. The first one is based on known constraints from the literature and the second one is based on the idea of micro-periods and a phantom cutting process. Due to the dependency of the setup decisions in the bin-packing problem with sequence-dependent setups, the resulting formulations are mixed-integer nonlinear mathematical models. Exact mixed-integer linear programming formulations are presented by applying linearization techniques. An exact branch-and-cut algorithm, which applies violated subtour elimination cuts to deal with the sequence-dependent production and cutting setups, is developed to solve the non-polynomial formulations. In addition, a Benders-based branch-and-cut algorithm using Benders cuts and violated cuts is also presented to solve the integrated problem. A computational study is conducted in order to analyze the impact of the proposed approaches to model sequence-dependent setups and the exact solution methods used to solve the coupled bin-packing and lot-sizing problem.

, 37 pages