Research And Application Of Rectangular Packing Problem With Process Constraints

Based on packing and cutting process, this thesis presents a hybrid algorithm to improvematerial utilization of rectangular packing problem with process constraints and develops anoptimal layout system according to production practice.Rectangular packing problem belongs to NP-hard problem, having long been asignificant research field of academia and industry. In this thesis, overseas and domesticresearch status about rectangular packing problem and optimal layout system is discussedcarefully. According to various optimization algorithms, this thesis divides them into threecategories: accurate algorithm, heuristic algorithm and meta-heuristic algorithm. Aftercomparing each algorithm’s advantages and drawbacks and analyzing its implementationsteps, this thesis summarizes the algorithm development tendency of rectangular packingproblem.Aiming at rectangular packing problem with process constraints, this thesis builds amathematical model and uses surplus rectangle filling algorithm to meet “guillotine packing”constraint and “multi-part and multi-board” constraint. However, this leads to many holes onsheet. So an improved surplus rectangle filling algorithm is proposed, adding part’s numberjudging, rotating and searching backward operations, which ensures parts can be located inmore appropriate surplus rectangles and makes full use of smaller surplus rectangles to avoidholes. This improved algorithm not only can meet “fiber direction”, but also enhancesmaterial utilization greatly. Finally, this thesis puts forward a hybrid algorithm, combiningimproved surplus rectangle filling algorithm with genetic algorithm together. With GA’sevolution and global search, hybrid algorithm further improves material utilization. Someexamples are presented for comparison of these three algorithms.Last, an optimal layout system is developed based on practical application andtheoretical analysis, including modules of part management, sheet management, layoutmanagement and so on. Applied in a certain cutting workshop, this optimal layout systemsimplifies production process and improves packing efficiency and utilization, bringing greateconomic benefit to enterprise.