本文選題：矩形板材排樣　切入點：遺傳算法　出處：《電子科技大學》2015年碩士論文

【摘要】：板材排樣優(yōu)化在現(xiàn)代工業(yè)生產(chǎn)中有著廣泛的應用,而矩形板材排樣優(yōu)化又是其中最為常見的一類問題。給定一定數(shù)量的矩形板材以及目標零件的尺寸與數(shù)量,矩形板材排樣優(yōu)化需要找出生產(chǎn)成本最低的切割方案。而生產(chǎn)成本的高低主要由原料使用多少、切割加工難度決定。根據(jù)加工工藝的不同,矩形板材排樣問題又可以分為有“一刀切”約束和無“一刀切”約束這兩類,本文研究的是有“一刀切”約束的矩形板材排樣優(yōu)化問題,其典型的應用場景包括玻璃、石材、木材等板材的生產(chǎn)加工。本文首先介紹了目前排樣優(yōu)化問題的國內外研究現(xiàn)狀,指出了針對石材行業(yè)多類型、多尺寸原料輸入情況下設計排樣優(yōu)化算法的背景與意義,然后分析了在現(xiàn)有加工工藝下矩形板材排樣的約束條件,將“易于切割”進行量化并加入到了待優(yōu)化的目標函數(shù),從而彌補了以往僅僅靠出材率評價排樣方案的不足,最終建立了相應的數(shù)學模型。接著介紹了矩形板材排樣問題已有的經(jīng)典算法,著重介紹了剩余矩形算法。接下來研究了遺傳算法在排樣優(yōu)化問題中的應用,提出了將原料加入染色體編碼的方案,從而解決了排樣優(yōu)化中的多規(guī)格原料輸入問題;使用數(shù)學模型中的目標函數(shù)合成非線性的適應度評價函數(shù);設計符合排樣優(yōu)化的染色體交叉算子。然后分析了前面設計的遺傳算法在同一規(guī)格的原料、零件數(shù)量較多時存在的不足,提出了同類復用策略,并嘗試將其融入到遺傳算法中,最終使用貪心算法實現(xiàn)同類復用策略,并通過分階融合的方式將其與遺傳算法結合使用,從而解決了遺傳算法排樣結果與實際生產(chǎn)習慣不夠契合的問題。在此基礎上,提出了進一步改進排樣算法的整體擺放策略,并將其應用到貪心算法當中。對于未充分利用的原料,提出了二分搜索策略來提高余料的可用性。接下來使用前面提出的排樣算法設計并編碼實現(xiàn)了針對石材行業(yè)的自動排樣系統(tǒng),將其分為UI模塊和算法模塊兩部分,使其具有較高的可維護性,同時加入了一些石材行業(yè)的常用功能,提高了排樣系統(tǒng)的實用性。最終,我們通過一個符合實際生產(chǎn)需要的具有多類型、多規(guī)格原料與零件的測試用例對自動排樣系統(tǒng)進行測試,成功計算出所有220個目標零件的排樣方案,整體出材率為94%,同時排樣結果也具有同類復用、整體擺放的特征,達到了排樣算法的設計目標。
[Abstract]:Plate layout optimization is widely used in modern industrial production, and rectangular plate layout optimization is one of the most common problems.Given the size and quantity of a certain number of rectangular plates and target parts, the cutting scheme with the lowest production cost is needed to optimize the layout of rectangular plates.The cost of production is mainly determined by the amount of raw materials used and the difficulty of cutting and processing.According to the different processing technology, the rectangular plate layout problem can be divided into two types: "one size fits all" constraint and no "one size cut" constraint. In this paper, the rectangular plate layout optimization problem with "one size fits all" constraint is studied.Typical application scenarios include the production and processing of glass, stone, wood, etc.This paper first introduces the current research status of layout optimization problem at home and abroad, and points out the background and significance of designing layout optimization algorithm under the condition of multi-type and multi-size raw material input in stone industry.Then, the constraint conditions of rectangular plate layout under the existing processing technology are analyzed, and the "easy to cut" is quantified and added to the objective function to be optimized.Finally, the corresponding mathematical model is established.Then the classical algorithms of rectangular plate layout are introduced, and the residual rectangle algorithm is emphasized.Then, the application of genetic algorithm in layout optimization is studied, and the scheme of adding raw material to chromosome coding is put forward to solve the problem of multi-specification raw material input in layout optimization.The objective function in the mathematical model is used to synthesize the nonlinear fitness evaluation function, and the chromosome crossover operator is designed according to the layout optimization.Then it analyzes the shortcomings of the genetic algorithm in the same specification and the large number of parts, and puts forward the similar reuse strategy, and attempts to integrate it into the genetic algorithm, and finally uses greedy algorithm to realize the same reuse strategy.The genetic algorithm is combined with genetic algorithm in order to solve the problem that the layout result of genetic algorithm is not consistent with the actual production habit.On this basis, the overall placement strategy of the improved layout algorithm is proposed and applied to the greedy algorithm.A binary search strategy is proposed to improve the availability of raw materials.Then, the automatic layout system for stone industry is designed and coded with the proposed layout algorithm, which is divided into two parts: UI module and algorithm module, so that it has high maintainability.At the same time, some common functions of stone industry are added to improve the practicability of the layout system.Finally, we test the automatic layout system with a test case of multi-type, multi-specification raw materials and parts that meet the actual production needs, and successfully calculate the layout scheme of all 220 target parts.The overall output rate is 94 and the layout result has the characteristics of similar reuse and overall placement, which achieves the design goal of the layout algorithm.
【學位授予單位】：電子科技大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：TB30;TP18

【參考文獻】

相關期刊論文 前2條

1 王潔;;關于NP結構的研究[J];計算機科學;1984年04期

2 朱冠華;;矩形件排樣中基于最低水平線的改進算法[J];茂名學院學報;2006年01期

，

本文編號：1703098