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

General integrated lot-sizing and cutting stock problems: Solution methods

Silvio Alexandre de Araujo Universidade Estadual Paulista "Júlio de Mesquita Filho" (UNESP), Brésil

The lot-sizing problem and the cutting stock problem have been the object of extensive research for more than 50 years. Much progress has been made with respect to formulations and solution methods for these two problems. The literature mostly deals with the lot-sizing problem and cutting stock problem separately through models that capture just the main trade-off in each problem. The basic idea of the integrated lot-sizing and cutting stock problem is to consider, simultaneously, the decisions related to both problems so as to capture the interdependency between these decisions in order to obtain a better global solution. The interest in this integrated problem often originates from direct practical applications of the integrated environments in various industries (paper industry, fiber glass industry, aluminum industry and furniture industry). When various authors refer to an integrated lot-sizing and cutting stock problem, they often consider different assumptions with respect to the level of integration considered, and hence present quite different models. In a previous paper we propose a general formulation that considers multiple dimensions of integration and comprises several aspects found in practice, and as such enables us to classify the current literature in this field. In this work we, firstly, present a literature review of the solution methods to the integrated lot-sizing and cutting stock problem. Secondly, we develop solution methods for the general formulation proposed. We are interested in mathematical programming based heuristic approaches that overcome the difficulties faced in the cutting stock problem and take advantage of the multi-level structure to deal with the binary values of the setup variables in the lot-sizing problem. The solution methods proposed to the general problem are based on two known strategies from the literature which are column generation procedure, which is largely used in the literature of cutting stock problems and the relax-and-fix heuristics, which are used successfully in lot-sizing problems. These strategies are combined into an optimization package in a computational study with randomly generated data.

Joint work with Gislaine Mara Melega and Raf Jans.


Entrée gratuite.
Bienvenue à tous!