engleski

Bottom-Left and Sequence Pair for Solving Packing Problems

Nesting problem is a combinatorial optimization problem with a goal of placing a set of polygons within container without overlapping. If polygons in shape of cutting patterns are used, and the container has rectangular shape with a fixed width, the problem is defined as a strip packing problem. In this paper two methodologies are described: Bottom-Left (BL) and Sequence Pair (SP). Bottom-left is order based strategy which can solve strip packing problem. It moves each polygon as far as possible to the bottom of the temporary layout and then as far as possible to the left until a stable position is found. In this paper BLDi version was used with genetic algorithm. Sequence pair is an abstract representation method used for nesting problem that creates a relationship model between rectangular approximations of polygons instead of direct placement. The goal of the research is to obtain maximum packing density for described methodologies. Experiments have been conducted on benchmark datasets: Albano (24 parts), Dagli (30 parts), Mao (20 parts) and Marques (24 parts) in MATLAB environment, with GA-BLDi performing 78.23, 70.15, 70.70 and 77.63 percent respectively (in average), and SP-BLi performing 76.28, 63.10, 68.52 and 75.60 percent respectively (in average).

genetic algorithm ; simulated annealing ; longest common subsequence ; sequence pair ; strip-packing problem ; nesting

nije evidentirano