Naslov
Solving Strip Packing Problem Using Sequence Pair

Autori
Domović, D. ; Rolich, T.

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

Izvornik
Proceedings of the 38th International Convention MIPRO 2015 / Petar Biljanović - Rijeka : Hrvatska udruga za informacijsku i komunikacijsku tehnologiju, elektroniku i mikroelektroniku - MIPRO, 2015, 1430-1435

ISBN
978-953-233-083-0

Skup
38. International Convention on Information and Communication Technology, Electronics and Microelectronics

Mjesto i datum
Opatija, Hrvatska, 25.05.2015. - 29.05.2015

Vrsta sudjelovanja
Predavanje

Vrsta recenzije
Međunarodna recenzija

Ključne riječi
sequence pair ; longest common subsequence ; simulated annealing ; irregular items ; strip packing problem

Sažetak
Strip-packing problem is a combinatorial optimization problem with a goal of finding optimal positions of cutting patterns that meet the following conditions: each pair of cutting patterns must not overlap and they must be placed within the boundary of rectangular material area. An optimal placement that utilizes material usage needs to be created. Strip-packing problem is a common textile industry problem where it is also known as automated marker making problem. In this paper a sequence pair abstract representation is used to obtain a non-overlapping placement. For that reason cutting patterns are approximated with a rectangular bounding box and placement of rectangles is obtained first. Non-approximated cutting patterns’ positions and material dimensions are then decoded using longest common subsequence method. These methods are combined with simulated annealing algorithm to find an optimal placement of cutting patterns. Experiments were conducted on 4 benchmark datasets: MARQUES and ALBANO (24 cutting parts), DAGLI (30 cutting parts), and MAO (20 cutting parts) with material utilization of 83.54%, 82.02%, 69.86%, and 71.26% respectively.

Izvorni jezik
Engleski

Znanstvena područja
Računarstvo

POVEZANOST RADA