Algorithms for 2D Nesting Problem Based on the No-Fit Polygon (CROSBI ID 611254)
Prilog sa skupa u zborniku | izvorni znanstveni rad | međunarodna recenzija
Podaci o odgovornosti
Domović, D. ; Rolich, T. ; Grundler, D. ; Bogović, S.
engleski
Algorithms for 2D Nesting Problem Based on the No-Fit Polygon
Strip-packing problem is apparent in textile industry where a set of items, i.e. cutting parts (2D convex or non-convex polygons) need to be placed on a rectangular container (fabric with an m×n area) so that cutting parts do not overlap and do not exceed the boundaries of the container. The goal is to find a placement that utilizes the area of a container. In this paper three methods (random search, greedy algorithm and genetic algorithm) are tested on sets of regular (convex polygons) and irregular (cutting parts) items. The goal is to find the optimal items placement that minimizes the cover area. In this paper a no-fit polygon (NFP) is used to assure two items touch without overlapping. NFP is constructed by rotating polygon B around a static polygon A in a way their edges always touch and never overlap. The result is a polygonal area enclosed by trajectory of rotating polygon's reference point which represents the overlapping area of A and B. Items touch if polygon B is placed on the NFP’s border. Non-convex cutting parts are approximated with their convex hull since a NFP version for convex polygons is used in this paper.
strip-packing problem ; no-fit polygon ; optimization ; convex hull ; genetic algorithm ; greedy algorithm ; random search
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
Podaci o prilogu
1344-1349.
2014.
objavljeno
Podaci o matičnoj publikaciji
Proceedings of the 37th International Convention MIPRO 2014: CIS - Intelligent Systems
Petar Biljanović
Rijeka: Hrvatska udruga za informacijsku i komunikacijsku tehnologiju, elektroniku i mikroelektroniku - MIPRO
978-953-233-078-6
1847-3946
Podaci o skupu
MIPRO 2014
predavanje
25.05.2014-29.05.2014
Opatija, Hrvatska