A flexible labour division approach to the polygon packing problem based on space allocation

Abstract

This paper deals with the two-dimensional satellite module polygon packing problem. Based on the duality of material and space, it regards the polygon packing problem as a space allocation problem, which involves allocating the container space to the given polygons reasonably and efficiently. Ant colony’s labour division is essentially a kind of task allocation. Using this task allocation to achieve the space allocation in polygon packing problems, a flexible labour division approach (FLD) is proposed based on the response threshold model. According to the characteristics of space allocation in polygon packing problems, FLD designs three actions for polygons to occupy the container space. With the interaction between environmental stimulus and response threshold, each polygon takes an appropriate action to complete the space allocation and a layout that meets the requirements of satellite module layout is obtained. The results of standard test instances demonstrate the effectiveness of FLD when compared with self-organisation emergence algorithm. Moreover, experiments on the general polygon packing problem also show that FLD is competitive with other existing algorithms.

Keywords:

• nesting
• packing problems
• cutting stock problems
• space allocation
• ant colony’s labour division