Hybrid genetic algorithm for cutting and packing problems

混合遺傳演算法於分割與合併問題上之應用

Student thesis: Master's Thesis

View graph of relations

Author(s)

  • Ho Wai YEUNG

Related Research Unit(s)

Detail(s)

Awarding Institution
Supervisors/Advisors
Award date15 Jul 2004

Abstract

Cutting and Packing (C&P) problems are commonly found in our daily life. Typical examples include resource allocation, material cutting, package packing, to name a few. The C&P problem is an optimization problem for allocating small objects into some large ones. Its high complexity and difficulty are well known, not only because it is NP-hard but also due to the multi-dimensional geometrical constraints imposed. In this thesis, a hybrid strategy that combines heuristic approach and genetic algorithm (GA) is established to solve the C&P problems. Heuristic-based approximation method, though it is simple and has been used extensively, is always criticized for having the sub-optimal solution only. On the other hand, GA, as a stochastic algorithm inspired by the mechanism of natural selection, is well recognized with its ability in searching global optimum. Nevertheless, due to the complicated data structures and specialized operators required for the geometrical layout, the speed is rather slow and only problems of small scale can be managed efficiently if applied solely and directly. In the proposed hybrid approach, the complicated geometrical layout and constraints are handled by a heuristic method designed for object packing (or cutting), while optimization of the packing sequence is performed by GA. Thus, the high-dimensional and complicated C&P problem is transformed into a simple permutation problem which is well-understood and can be efficiently solved by GA. The searching space can be greatly reduced and the design effort for chromosome and operations is minimal. Both theoretical analyses and simulations have shown that the time complexity is linearly proportional to the number of small objects in average. The hybrid genetic approach has been successfully applied for practical packing problems with different dimensions, including Job-Shop Schedule problem, Cloth Cutting problem and Container Loading problem. It is demonstrated that optimal results can be duly attained even for medium to large cases in a reasonable time.

    Research areas

  • Packing for shipment, Genetic algorithms, Packaging, Cutting, Cutting stock problem, Data processing