模拟退火法应用在含中空基板之排版.PDFVIP

科學與工程技術期刊 第七卷 第三期 民國一○○年 13 Journal of Science and Engineering Technology, Vol. 7, No. 3, pp. 13-21 (2011) 模擬退火法應用在含中空基板之排版 賴元隆 陳薡任 許博榕 大葉大學機械與自動化工程學系 51591 彰化縣大村鄉學府路 168 號 摘 要 一個排版問題主要由兩個過程來完成，一是零件排列次序（permutation ）之決定，另一是 排放零件至基板的排置（placement ）方法；這兩個過程就主宰了一次排版結果的優劣。如果次 序對了，排置方法也滿足需求，這個時候我們就可以找到正解或最佳解；但是往往無法得知正 確的排列次序，因此需要利用搜尋法則來尋找最佳解。但是如果排置的方法不佳，即使排列的 次序對了，排版出來的結果也不盡完善。本研究針對具間隙零件的排版需求，開發創新的排置 演算法（placement algorithm ），結合模擬退火法（simulated annealing ）之特點而來進行排版系 統之最佳決策，找出最好的排版效果。二維排版問題最佳化的目的乃將特定數量的相同或不同 工件（piece ）排列於基材（sheet ）上，期使基材使用率最高或浪費最少為目標，如此基板的使 用率最高以減少物料成本。本研究更進一步將系統以自動化的方式來呈現，發展一模擬排版巨 集指令，將繁瑣的設定工作交由自動系統完成，簡化操作人員技術上的要求。 關鍵詞：排版，排置演算，模擬退火，巨集 Using Simulated Annealing to Solve 2D Nesting Problems on Hollow Sheets YUAN-LUNG LAI, DING-REN CHEN and PO-JUNG HSU Department of Mechanical and Automation Engineering, Da-Yeh University 168 University Rd., Dacun, Changhua 51591, Taiwan, R.O.C. ABSTRACT A nesting problem can be solved using two processes; one is determining the permutation for sequences of pieces, and the other is applying a placement algorithm to place the pieces onto the sheet. These two vital processes dominate the solutions to the nesting probl