Research On Comparison And Integration Of Rectangular Optimal Layout Algorithms Under Constraint Of Guillotine

The problem of rectangular layout is very complicated in computing theory,but it has gotthe extensive application in the actual manufacture.It prevalent in many areas of industrialproduction,and occupies an important position. A good packing scheme can improve theutilization of raw materials effectively, reduce the production cost and bring economic benefitsfor enterprises.Because of the different of cutting craft and plate situation,the problem ofrectangular layout need to be divided into a few problems to solve. One class is cutting stockmust meet the constraint of guillotine,it prevalent in machining of glass, newspaper typesettingand furniture manufacturing.The research in this paper is for this kind of problem.In order to finda better rectangular layout program,consultend a large number of domestic and foreign literature,in-depth study on the rectangular optimal layout algorithm.First,this paper expatiates the background and significance of the subject,summarizes andanalyzes the research status of the problem of rectangular layout in domestic and foreign,sumsup the related theory of the problem of rectangular layout and established the mathematicalmodel.Introduces several common heuristic layout algorithm,and analyzes of the advantages anddisadvantages of each algorithm.Proposed an improved minimum contour search algorithmbased on the result,and make it as the decoding method of Genetic Algorithm.And thenintroduces the basic theory of Genetic Algorithm and Ant Colony Algorithm.Design andimprovement the two basic algorithms based on the features of the problem,gives the concretesteps for solve the problem of rectangular layout by Genetic Algorithm and Ant ColonyAlgorithm.Then tests and compares the two algorithms through an example.Next,analysis of thefeasibility and introduces the fundamental of integration of the two algorithm,and then emphasisresearch the best integration opportunity between the two algorithms.Analysis of the deficienciesof the existing mixed strategy and proposed an improved mixed strategy,gives the concrete stepsfor solve the problem of rectangular layout by mixed algorithm,and solves an example throughexisting mixed algorithm and improved mixed algorithm.Compares the performance of Genetic Algorithm, Ant Colony Algorithm, existing mixed algorithm and improved mixed algorithm.Theresult shows that the improved mixed algorithm is more effective in solving the problem ofrectangular layout under constraint of guillotine.Finally the paper sums up this paper and lookingforward.