The one-dimensional cutting stock problem with usable leftovers and k-best solutions for knapsack problem

• Grant number: 12/18788-0
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: November 01, 2012
• End date: October 31, 2013
• Field of knowledge: Engineering - Production Engineering - Operational Research
• Principal Investigator: Adriana Cristina Cherri
• Grantee: Renata Tiepo Fonseca
• 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

In the one-dimensional cutting stock problem with usable leftovers (1DCSPUL), a set of items must be produced from a set of available objects in stock with the objective to minimize the waste. However, since the quality of the cutting patterns depends directly on the size and quantity of the items to be produced, we can consider that if the 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. The study that involves the 1DCSPUL is recent in the literature and few papers present a mathematical model to obtain the solution to these problems. Therefore, in this project, we use a mathematical model recently published in the literature to solve the 1DCSPUL and we propose some modifications to obtain the solution. Computational implementations will be developed and, to verify the performance of the proposed procedures, computational tests will be realized with instances from the literature and, if possible, with real problems. We also pretend use a random generator of instances, based in the work of the literature. In this generator, successive problems are solved in a time horizon. For each period, new demands arise and a new problem is solved considering information about the stock and the retails generated of the previous period. (AU)