A New Comprehensive Algorithm for the Cutting and Packing Problem with Position Constraints

A New Comprehensive Algorithm for the Cutting and Packing Problem with Position Constraints

The cutting and packing (CP) is a widespread problem in the production processes of garment, shoes, board, and in other manufacturing industries. It is closely related to the production and management costs. This problem refers to the placement of pieces, without overlapping, in a limited space by maximizing the space utilization. In this work, a CP variant with position constraints, namely the horizontal striped fabric layout problem (HSFL), is investigated. We propose a solution approach for it, where a top-left fill (TLF) algorithm based on key points positioning strategy is used to deal with position constraints in the stripe alignment problem. This algorithm establishes a key points sequence for every piece, when determining the placement of pieces, compare the key points sequence of pieces. This algorithm also eliminates the error often occurred in the rectangle bounding box algorithm at the time of simplifying the layout process. The TLF algorithm based on key points positioning strategy and genetic algorithm (GA) are combined for obtaining the optimum layout. The datasets used in the computational experiment are collected from an apparel industry as well as from other publications. The comparison of our experimental results with the best known results shows that the proposed approach could improve the average computing speed and achieve higher utilization in 10 out of 16 instances. It can be concluded that the proposed approach is potential in balancing the computing speed and utilization rate. The algorithm has been successfully applied in an apparel company in China.