Naslov
Algorithms for 2D Nesting Problem Based on the No-Fit Polygon

Autori
Domović, D. ; Rolich, T. ; Grundler, D. ; Bogović, S.

Vrsta, podvrsta i kategorija rada
Radovi u zbornicima skupova, cjeloviti rad (in extenso), znanstveni

Izvornik
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, 2014, 1344-1349

ISBN
978-953-233-078-6

Skup
37. International Convention on Information and Communication Technology, Electronics and Microelectronics - MIPRO 2014

Mjesto i datum
Opatija, Hrvatska, 26.05.2014. - 30.05.2014

Vrsta sudjelovanja
Predavanje

Vrsta recenzije
Međunarodna recenzija

Ključne riječi
strip-packing problem ; no-fit polygon ; optimization ; convex hull ; genetic algorithm ; greedy algorithm ; random search

Sažetak
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.

Izvorni jezik
Engleski

Znanstvena područja
Računarstvo

POVEZANOST RADA