A Research On Circular Layout Algorithm Based On Quasi-physical And Layered Searching Algorithm

Packing problem is to find out an optimal layout for some reagular or irreagular shapes with the border and process constraints. The objective of packing problem is to achieve an best material utilization ratio and produce the least waste. Packing problem exists in manufacturing industry widely, such as sheet metal fabrication and garment cutting. An optimal layout in manufacturing can help improve the material utilization ratio, increase productivity and decrease cost for the enterprise.Great importance has been attached to the two-dimensional packing problems all around the world, but little attention has been paied to the circular shape packing problem. In practice, a manual lay-out method is always employed when the circular packing problem is encountered, which is neither good in productivity nor in utilization ratio. Thereby, we can solve this problem with the assistance of computer intelligent algorithm. We classify the existing packing algorithms into three types: accurate algothims, heuristic algorithms and meta-heuristic algorithms. With the comparsions and analysis of these algorithms, it may helpful for us to find a new method to solve the circular packing problem. For the two-dimensional circular packing problem, a layered searching algorithm(LSA) based on quasi-physical algorithm is proposed in this paper, which can effectively improve the utilization ratio of materials. Moreover, a circular layout softare system is developed according to the practical production requirements.The circular packing problem studied in this paper belongs to constrained two-dimensional problems. This problem can be described as follows: with the constraint of part numbers, finding an optimal layout to place all these parts in fewest plates with specific size or shortest coil with specific width. To solve this problem, a layered searching algorithm based on quasi-physical algorithm is proposed in this paper. The experiment indicates that the proposed algorithm can obtain a result which can catch up with the result of Hifi's algorithm. Moreover, LSA can save remarkable time compared with the existing algorithms. Random experiment shows that the solving time of LSA can meet the requirements of practical production with good utilization ratio of materials.Applying the LSA, a circular packing software system is developed for practical use, where several modules are realized, such as the part management, plate management and packing management. The software can be applied to practical manufacture, aiming at increasing the utilization ratio of materials and improving production management.