- 期刊
創新排列與基因演算法於電腦輔助自動排版系統之研究
New Placement and Genetic Algorithms for a Computer-Aided Nesting System
摘要
一個排版問題主要由兩個過程來完成，一是零件排列次序(permutation)之決定，另一是排放零件至基板的排置(placement)方法；這兩個過程就主宰了一次排版結果的優劣。如果次序對了，排置方法也滿足需求，這個時候我們就可以找到正解或最佳解；但是往往無法得知正確的排列次序，因此需要利用搜尋法則來尋找最佳解。但是如果排置的方法不佳，即使排列的次序對了，排版出來的結果也不盡完善。本研究針對具間隙零件的排版需求，開發創新的排置演算法(placement algorithm)，結合基因演算法(genetic algorithm)之特點而來進行排版系統之最佳決策，找出最好的排版效果。二維排版問題最佳化的目的乃將特定數量的相同或不同工件(piece)排列於基材(sheet)上，期使基材使用率最高或浪費最少爲目標，如此基板的使用率最高以減少物料成本。排版問題依據不同的限制與目的存在於不同的產業中，如半導體印刷電路板、複合材料、高分子板材、玻璃切割、實木成型、家具裝潢、鞋業生產、服裝裁剪、皮革下料、建築包工、造船鋼板、車輛和發電設備生產中都存在大量的下料或精密排版切割問題。
並列摘要
A nesting problem can be solved by two processes, one being determining the permutation for sequences of pieces; the other, applying a placement algorithm for positioning all pieces on the sheet. These two important processes dominate the solutions for the nesting problem. If the sequence of permutation is available and the placement rule also meets the packing demand, then the exact or optimum solutions can be found. However, whether the sequence of permutation is adequate remains unknown. Even if the sequence is appropriate for the permutation, without a suitable placement algorithm the final results are also unacceptable. In this research, we developed a new placement algorithm for pieces with gaps in automatic nesting operations, by which a genetic algorithm approach to optimal determination of hollow nesting systems was adopted. The objective of the two-dimensional optimal nesting problem is to determine an effective usage of a stock sheet under different configurations of the pieces. Such determination ensures that the material utilization rate is the highest, thereby reducing the cost of materials. Nesting problems are encountered in many different industries, incorporating different constraints and objectives. E.g., the PCB, wood, polymer-plate, glass, paper, metal, textile and leather industries are substantially concerned with the cutting of arbitrary-shaped figures.