Logic-Based Benders Decomposition for Integrated Process Configuration and Production Planning Problems

Karim Pérez Martínez (), Yossiri Adulyasak () and Raf Jans ()
Additional contact information
Karim Pérez Martínez: GERAD and Department of Logistics and Operations Management, HEC Montréal ( École des hautes études commerciales de Montréal ), Montréal, Québec H3T 2A7, Canada
Yossiri Adulyasak: GERAD and Department of Logistics and Operations Management, HEC Montréal ( École des hautes études commerciales de Montréal ), Montréal, Québec H3T 2A7, Canada
Raf Jans: GERAD and Department of Logistics and Operations Management, HEC Montréal ( École des hautes études commerciales de Montréal ), Montréal, Québec H3T 2A7, Canada

INFORMS Journal on Computing, 2022, vol. 34, issue 4, 2177-2191

Abstract: We propose a general logic-based Benders decomposition (LBBD) for production planning problems with process configuration decisions. This family of problems appears in contexts where the machines are set up according to specific patterns, templates, or, in general, process configurations that allow for simultaneously producing products of different types. The problem requires determining feasible configurations for the machines and their corresponding production levels to fulfill the demand at the minimum total cost. The structure of this problem contains nonlinear constraints that link the number of units produced of each product with the used configurations and their production levels. We decompose the original problem into a master problem, where the configurations are determined, and a subproblem, where the production amounts are determined. This allows us to apply the LBBD technique to solve the problem using a standard LBBD implementation and a branch-and-check algorithm. LBBD enhancements through logic-based inequalities generated for subsets of products with common characteristics are proposed. Such inequalities represent a form of the subproblem relaxation added to the master problem during its resolution. In our computational experiments, we apply the proposed LBBD approaches to two different applications from the literature: cutting stock problems in the steel industry and a printing problem. Results show that the LBBD methods find optimal solutions much faster than the solution approaches in the literature and have a superior performance with respect to the number of instances solved to optimality and the solution quality. Summary of Contribution: In this work, we introduce a unified exact solution algorithm based on logic-based Benders decomposition to solve a class of integrated production planning problems that include process configuration decisions. We propose a general mathematical representation of the original integrated planning problem and logic-based Benders reformulations that can be applied to solve several problems within the studied class. Our implementation frameworks provide guidelines to practitioners in the field. The solution approaches in this paper together with the proposed methodological enhancements can be adapted to solve other integrated planning problems in a similar context, including the case when the original problem has a complex combinatorial and nonlinear structure.

Keywords: logic-based Benders decomposition; branch-and-check; integrated production planning; cutting stock (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2021.1079 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:34:y:2022:i:4:p:2177-2191

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().