AND/OR Graph approach to solve the two-dimensional cutting stock problem with usable leftovers

• Grant number: 13/06785-0
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: May 01, 2013
• End date: November 30, 2014
• Field of knowledge: Engineering - Production Engineering - Operational Research
• Principal Investigator: Adriana Cristina Cherri
• Grantee: Luiz Carlos Felix Ribeiro
• Host Institution: Faculdade de Ciências (FC). Universidade Estadual Paulista (UNESP). Campus de Bauru. Bauru , SP, Brazil
• Associated research grant: 10/10133-0 - Cutting, packing, lot-sizing and scheduling problems and their integration in industrial and logistics settings, AP.TEM

Abstract

The cutting stock problem consists of cut a set of pieces available in stock in order to produce a set of items, on request or to stock, in specified quantity. In this problem, the quality of the cutting patterns depends directly on the size and quantity of the items to be produced. Therefore, in this project that addresses two-dimensional cutting stock problem, we consider that if a demand of items generates undesirable wastes (not large enough to be used, nor too small to be acceptable waste), then it is better generate retails (not computed as waste) which can be used to produce items for future demands. To solve this problem, some modifications have already been made in the AND/OR Graph approach and in classics heuristic procedures from the literature. However, all developed procedure was implemented using the Delphi programming language. Thus, we pretend to rewrite all the existing code to solve the problem using the C programming language, to change some existing routines in the current programming by routines that should improve the performance of the ANG/OR Graph and define and implement some desirable characteristics for a good solution to the problem (small loss and few leftovers). To verify the performance of the proposed procedures to solve the two-dimensional cutting stock problem, computational tests will be realized with real problems and a set of problems randomly generated.