Research And Application Of Rectangular Nesting Based On Harmony Search Algorithm

With the improvement of abilities and skills of manufacture,how to utilize and exploit raw materials efficiently and environment-friendly has gradually become an issue of vital importance for a country rich in resource.Rectangular nesting problems with practical process constraints in wood industry are intensively considered.Main research efforts are listed as below.Firstly,detailed related works of overseas and domestic researchers are analyzed and summarized.Followed by the foundation of main framework of this thesis,classification,methodology along with weakness and tendency concerning rectangular nesting problem are systematicly introduced.Theories about rectangular nesting problem are considered.With regard to the very problem within the scope of NP-hard,a generalized math model is constructed.Base on the state-of-art algorithms designed to tackle with nesting problem,a composite method of Harmony Search algorithm and strategy of Degree of match-up is proposed.Embed with cross and mutation operators of GA,the new proposed algorithm is used to optimize the sequence of rectangular items to pack.The strategy of Degree of match-up is modified to choose the most proper remain rectangular space of sheet for the current item.The experimental results of bin and strip packing problems show that the presented algorithm outperforms some of the algorithms compared.Secondly,packing problems with process constraints in wood industry are well discussed.Practical process constraints are generalized which are common in wood industry,such as Consideration of orientation of fiber,Guillotine cutting,Maximum of Blade length and Packing each item of the same type stickily as much as possible.A complicated mathematical model concerning this problem is established.A combinatorial fulfillment strategy is proposed to tackle with these process constraints,which group and reshape several items considered into a rectangle as large as possible,which can be packed into the residual rectangular space of sheet.Degree of match-up of the item is computed referring to the similarity between the residual rectangle and the formed large rectangle it can hold.The location is determined by choosing the biggest value of Degree of match-up of the item.Furthermore,in order to solving rectangular nesting problem of large scale,a modified method was presented with coding type of the items rather than the number of that.Also,the experimental results validate this new proposed algorithm.And finally,followed by design of data structure and interfaces,a rectangular packing system for Nangong wood and mechanical factory is designed and developed on the basis of these presented algorithms and strategies,which lay the ground for the informatization construction of company concerned.Experiments upon two realistic cases are conducted to verify the practicablity of the very packing system.