Applying Shuffled Frog Leaping Algorithm in Cutting and Packing Problem

Abstract

The cutting and packing problem is commonly found in various industries. The major aim is to find a method of using the production material as efficiently as possible that results in reducing the total production cost. In many situations, time required to find a good solution and diversity of objects’ shape and size need to be considered as additional constraints. This research presents the method for finding the optimal solutions of the cutting and packing problem by applying the shuffled frog leaping algorithm (SFLA) with the bottom left fill (BLF) algorithm. The BLF algorithm imposes a specific method for arranging a sequence of objects by trying the fill up from the bottom left first in order to obtain a unique arranging pattern. SFLA, a population based, meta-heuristic optimization method, is applied in searching for optimal solutions. SFLA and BLF is able to find solutions for arranging simple rectangular objects into a limited size space. In many cases, the objects are in complex polygon shapes. SFLA is applied with the No Fit Polygon (NFP) method for arranging irregular shapes. Simulation results show that this approach is able to arrange irregular shapes effectively. The study shows how the algorithm parameters affect the solution finding performance.