The two-dimensional cutting problem with usable leftovers and uncertainty in demand

Author(s)

Douglas Nogueira do Nascimento

• Document type: Doctoral Thesis
• Press: Bauru. 2022-09-06.
• Institution: Universidade Estadual Paulista (Unesp). Faculdade de Engenharia. Bauru
• Defense date: 2022-09-01
• Advisor: Adriana Cristina Cherri; José Fernando Oliveira

Abstract

The cutting stock problem is a classic problem in the operational research area that has been the subject of hundreds of studies published in the scientific literature. In the first part of this thesis, a variation of this problem, known as the two-dimensional cutting stock problem with usable leftovers, is addressed, which consists of cutting rectangular plates available in stock to produce smaller rectangular items with specific dimensions and quantities while minimizing the material loss. The planning of this production is carried out considering the possibility of generating unordered leftovers that, if meeting predefined criteria, return to stock to be used in future cutting processes. Usable leftovers is a strategy of great practical importance for many companies, with strong economic and environmental impact, due to the reduction in raw material waste. To solve this problem, a mathematical model that simultaneously creates cutting patterns and determines their frequencies was proposed. The cutting patterns are created by a strategy that divides the cut plate into horizontal strips, in which the items are allocated. New items are also considered from the combination of the original types of items. This model was solved by an exact solver. However, due to its high number of variables and constraints, its resolution for medium and large-sized instances may become impracticable in an acceptable computational time. In this context, a heuristic procedure was developed using two adaptations of the model to solve separately the tasks of creating cutting patterns and defining their frequencies. Computational tests were performed with instances from the literature and randomly generated instances to compare the performance of the model and the heuristic with other models proposed in the literature. In the second part of the thesis, aiming to bring this research closer to real practical applications, the two-dimensional cutting stock problem with usable leftovers was studied considering uncertain items' demand. The production of usable leftovers and items to meet a variable and random demand is a recurring problem in companies due to the unpredictability occurrence of customer orders. Solving this problem involves complex planning, which motivates the search for solution methods that help in the decision-making process. For the formulation of this problem, the uncertain demands can be approximated by a finite set of possible scenarios. This thesis contributes to the scientific literature by proposing a matheuristic that solves the problem in three consecutive and dependent steps. In the first step, a set of cutting patterns, with and without usable leftovers, is created for all types of plates in stock and all possible item combinations. These cutting patterns are used in the second step by a framework based on genetic algorithms that generate a set of demand scenarios. In the third step, both patterns and scenarios are used by a stochastic model that determines the frequency of each cutting pattern in each demand scenario. This stochastic model was solved by two approaches, an exact solver and a heuristic based on the L-shaped method, tested in computational experiments with randomly generated instances. From the obtained results and an analysis of the effects of uncertainty on the quality of solutions, it was possible to verify that the matheuristic satisfactorily solves the addressed problem, demonstrating that it can be an efficient tool if applied to real situations. (AU)

• FAPESP's process: 18/16600-0 - The two-dimensional cutting stock problem with usable leftovers and demand uncertainty
• Grantee: Douglas Nogueira Do Nascimento
• Support Opportunities: Scholarships in Brazil - Doctorate (Direct)