以加入升温机制之模拟退火演算法求解单原片方形物件排列问.PDF

吳泰熙、鄭豐聰、趙楷：以加入升溫機制之模擬退火演算法求解單原片方形物件排列問題 253 技術學刊 第二十二卷 第三期 民國九十六年 253 Journal of Technology, Vol. 22, No. 3, pp. 253-261 (2007) 以加入升溫機制之模擬退火演算法求解單原片方形 物件排列問題 吳泰熙 國立台北大學企業管理系 鄭豐聰 逢甲大學工業工程與系統管理系 趙 楷 大葉大學工業工程與科技管理系 摘 要 工業界莫不亟思要如何精減人力以提昇效率，全面降低生產成本。然而在 如此競爭的環境裡，尚有部分產業仍利用人工方式來處理原物料切割/排列等 相關作業。此類複雜之「物件切割」問題需要有合適之演算法來迅速求得原物 料切割計畫。由於模擬退火演算法 (SA) 利用機率性攀爬搜尋演算法則，來搜 尋能量函數之總體最小值，且使用者亦能輕易地針對不同的問題發展其適合的 演算架構，因此已被大量運用於求解困難的決策問題。雖然 SA 藉著使用波茲 曼函數來接受品質較差之解，以期能跳脫區域解而達到搜尋全域最佳解之目 標。但當退火過程進行、溫度越降越低時，SA 陷入區域解之機率越來越大。 因此實有必要發展進一步之機制，以維持 SA 能跳脫區域解之功能。本研究因 此藉著導入升溫機制之觀念，讓 SA 跳脫區域解之能力不致因溫度高低不同而 受太大之影響，並應用此 SA 演算法於快速時間內求算出最佳或近似最佳之單 原片方形物件排列計畫。 關鍵詞：模擬退火演算法、方形物件排列問題、升溫機制 。 SOLVING A TWO-DIMENSIONAL PACKING PROBLEM USING A SIMULATED ANNEALING ALGORITHM WITH A RISING TEMPERATURE MECHANISM Tai-Hsi Wu Department of Business Administration National Taipei University Taipei, Taiwan 237, R.O.C. Feng-Tsung Cheng Department of Industrial Engineering and Systems Management Feng Chia University Taichung, Taiwan 407, R.O.C. 254 技術學刊