Research On Scroll Packing Problem With Guillotine Constraint

Scroll Packing Problem (SPP) mainly research on how to place rectangular products on sheet material with variable length in order to get high material utilization. SPPs are widespread in the manufacturing industry, such as cutting of paper and steel plate. SPP is one kind of classic NP-Complete Problem. Affected by some manufacturing process, the packing and cut solution of them are asked satisfy the guillotine constraint. At the same time, some work pieces are required to be paired. Such particular requirements bring new challenges to SPP. Good layout solutions can increase the material utilization greatly and reduce the enterprise’s cost.This thesis mainly researches on Two-Dimensional Scroll Packing Problem with Rotatable Rectangle and Guillotine Constraints (2DSPP-RG). We proposed a Group-Based Heuristic Search Approach, GBHSA. GBHSA is a constructive approach which combines the layout process with search process and recursively performs a ’placing&splitting’steps. The backtracking rule of GBHSA is the surplus waste area. Heuristic on splitting and searching steps have been widely used to reduce search space speed up the search process. GBHSA show good global optimization ability. We had compared GBHSA with other layout algorithms by use of a series of international standard benchmarks. GBHSA has certain advantages on solution quality.Also, we developed an interactive packing component to adjust the layout solution manually. It supports to add, delete, rotate and move the rectangle material items. After such operations are finished, a cutline generation algorithm, which takes the total path of cut lines as optimize object, is called to generate guillotine cutline.At last, we have developed a two-dimensional layout software based on the above research achievements.