Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/68306
Type: Artigo de periódico
Title: Heuristics for two-dimensional knapsack and cutting stock problems with items of irregular shape
Author: Del Valle, AM
de Queiroz, TA
Miyazawa, FK
Xavier, EC
Abstract: In this paper, the two-dimensional cutting/packing problem with items that correspond to simple polygons that may contain holes are studied in which we propose algorithms based on no-fit polygon computation. We present a GRASP based heuristic for the 0/1 version of the knapsack problem, and another heuristic for the unconstrained version of the knapsack problem. This last heuristic is divided in two steps: first it packs items in rectangles and then use the rectangles as items to be packed into the bin. We also solve the cutting stock problem with items of irregular shape, by combining this last heuristic with a column generation algorithm. The algorithms proposed found optimal solutions for several of the tested instances within a reasonable runtime. For some instances, the algorithms obtained solutions with occupancy rates above 90% with relatively fast execution time. (C) 2012 Elsevier Ltd. All rights reserved.
Subject: Two-dimensional irregular shape cutting and packing problems
GRASP
Column generation
Country: Inglaterra
Editor: Pergamon-elsevier Science Ltd
Rights: fechado
Identifier DOI: 10.1016/j.eswa.2012.05.025
Date Issue: 2012
Appears in Collections:Artigos e Materiais de Revistas Científicas - Unicamp

Files in This Item:
File Description SizeFormat 
WOS000307796300031.pdf1.37 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.