創新排列與基因演算法於電腦輔助自動排版系統之研究

New Placement and Genetic Algorithms for a Computer-Aided Nesting System

一個排版問題主要由兩個過程來完成，一是零件排列次序（permutation）之決定，另一是排放零件至基板的排置（placement）方法；這兩個過程就主宰了一次排版結果的優劣。如果次序對了，排置方法也滿足需求，這個時候我們就可以找到正解或最佳解；但是往往無法得知正確的排列次序，因此需要利用搜尋法則來尋找最佳解。但是如果排置的方法不佳，即使排列的次序對了，排版出來的結果也不盡完善。本研究針對具間隙零件的排版需求，開發創新的排置演算法（placement algorithm），結合基因演算法（genetic algorithm）之特點而來進行排版系統之最佳決策，找出最好的排版效果。二維排版問題最佳化的目的乃將特定數量的相同或不同工件（piece）排列於基材（sheet）上，期使基材使用率最高或浪費最少為目標，如此基板的使用率最高以減少物料成本。排版問題依據不同的限制與目的存在於不同的產業中，如半導體印刷電路板、複合材料、高分子板材、玻璃切割、實木成型、家具裝潢、鞋業生產、服裝裁剪、皮革下料、建築包工、造船鋼板、車輛和發電設備生產中都存在大量的下料或精密排版切割問題。