臺灣博碩士論文加值系統

在本篇論文中，提出一個整數型回溯搜索最佳化演算法(Integer Backtracking Search Optimization Algorithm，IBSA)，求解組裝式生產系統的基本存貨水準最佳化問題。組裝式生產系統是指在生產的最後階段，用庫存的通用零部件裝配滿足客戶訂單需求的產品。這些通用的零部件是在客戶訂貨之前就計劃、生產並儲存入庫的。收到客戶訂單後，就把它們裝配成最終產品。回溯搜索最佳化演算法優於其他方法的地方在於結構簡單，只有單一控制參數，能有效並迅速的求出最佳解。組裝式生產系統的基本存貨水準問題，可轉換成一個具有巨大解空間的整數型變數組合最佳化問題。雖然文獻中已經有許多的全域最佳解搜尋方法來解決此類問題，但是需要大量的世代搜尋，會耗費許多的計算成本及時間。因此，本篇論文的目的是將提出的演算法套用至組裝式生產系統，在有限的計算時間內求取足夠好的零件基本存貨水準，使得組裝式生產系統可以得到最大利潤。最後將所提出的演算法獲得的結果與三種方法:粒子群演算法、演化策略、模擬退火法做比較，模擬結果顯示所提出的整數型回溯搜索最佳化演算法表現超越三種方法。

關鍵字：整數型回溯搜索最佳化演算法、組裝式生產系統、庫存管控、基本存貨水準、整數型變數組合的最佳化問題

This thesis proposes an integer backtracking search optimization algorithm (IBSA) to solve a problem for a good enough base stock level of the assemble-to-order (ATO) system. ATO systems refer to a production environment in which the customer must first order specified products before the item is manufactured. The items of the products are already produced in ATO system, where every item is produced after receiving an order. Businesses often stock the inventory required to make the product. As soon as an order is placed, they often have every item they need to give the customer what has been demanded. Unlike many search algorithms, backtracking search optimization algorithm (BSA) has a single control parameter. The BSA has a simple structure that is effective, fast and capable of solving numerical optimization problems. The ATO system operating with a base stock policy can be formulated as a combinatorial optimization problem with integer variables that possesses a huge solution space. The huge solution space makes the considered problem very hard for conventional heuristic methods to find near-optimal base stock level in a reasonable time. The goal of this thesis is to determine a good enough base stock level of the ATO system in a reasonable computation time such that the total profit per period is maximized. The solution quality is demonstrated by comparing with those obtained by three competing methods: particle swarm optimization, evolution strategy and simulated annealing. The base stock level obtained by the IBSA is promising in the aspects of solution quality and computational efficiency.

Keywords: integer backtracking search optimization algorithm, assemble-to-order system, inventory control, base stock level, combinatorial optimization problem with integer variables.

索引目錄
中文摘要 I
Abstract II
索引目錄 III
表目錄 IV
圖目錄 V
第一章 緒論 1
1.1研究背景 1
1.2研究方法與論文架構 5
第二章 進化式演算法和群體智能演算法 7
2.1演化式策略(Evolution Strategy，ES) 7
2.2粒子群演算法(Particle Swarm Optimization，PSO) 9
2.3模擬退火演算(Simulated Annealing, SA) 11
2.4基因演算法(Genetic Algorithm, GA) 13
第三章 方法理論與應用 16
3.1回溯搜索最佳化演算法(BSOA) 16
3.2整數型回溯最佳化演算法 16
第四章 組裝式生產系統庫存管控問題 27
4.1組裝式生產系統簡介 27
4.2組裝式生產系統的管理需求分析 28
4.3組裝式生產系統的生產方法 30
4.4組裝式生產系統的形式 31
4.5組裝式生產系統的作用 32
4.6組裝式生產系統的使用範圍 32
4.7組裝式生產系統的生產管理過程 33
4.8組裝式生產系統的數學模式 34
4.9組裝式生產系統的問題難度 38
第五章 實驗結果與比較 39
5.1實驗結果 39
5.2.1演化式策略(ES) 44
5.2.2粒子群最佳化(Particle Swarm Optimization, PSO) 44
5.2.3模擬退火演算法(SA) 46
5.3比較結果 47
第六章 結論 48
參考文獻 49





表目錄
表1. 參數設定 22
表2. 10項零件的各項參數 40
表3. 6項產品的各項參數 41
表4. 實驗結果 41
表5. 方法比較 47

















圖目錄
圖1. 論文架構 6
圖2. 演化式策略(ES)計算流程 8
圖3. 粒子群演算法(PSO)計算流程 10
圖4. 基因演算法(GA)計算流程 12
圖5. 基因演算法(GA)計算流程 13
圖6. 基因演算法的交配圖例 14
圖7. 基因演算法的突變例子 15
圖8. 回溯最佳化演算法基本架構 16
圖9. 回溯最佳化演算法流程圖 18
圖10. 整數型回溯最佳化演算法流程圖 20
圖11. 企業實現按客戶訂單定製的分類點 27
圖12. 八項零件與五項產品組裝式生產系統 34
圖13. 輸入輸出關係流程圖 35
圖14. 組裝式生產系統的生產管理過程虛擬碼 37
圖15. 十項零件與六項產品 40

參考文獻
[1]D. Bertsimas and R. Weismantel and Optimization over Integers. Belmont and Massachusetts: Dynamic Ideas and 2004.
[2]K. Deb and Optimization for Engineering Design – Algorithms and Examples. Prentice-Hall of India. Privated Limited and New Delhi and 2004.
[3]S.J. Abspoel and L.F.P. Etman and J. Vervoort and R.A. van Rooij and A.J.G. Schoofs and J.E. Rooda and “Simulation based optimization of stochastic systems with integer design variables by sequential multipoint linear approximation” and Structural and Multidisciplinary Optimization and vol. 22 and no. 2 and Pp. 125-138 and 2001.
[4]Y. Xiao and J. Chen and C.Y. Lee and “Optimal decisions for assemble-to-order systems with uncertain assembly capacity and” International Journal of Production Economics and vol. 123 and no. 1 and Pp. 155-165 and 2010.
[5]S.S. Ko and J.Y. Choi and D.W. Seo and “Approximations of lead-time distributions in an assemble-to-order system under a base-stock policy and” Computers & Operations Research and vol. 38 and no. 2 and Pp. 582-590 and 2011.
[6]G. L. Nemhauser and A.W. Laurence and Integer and Combinatorial Optimization. John Wiley & Sons and New York and1999.
[7]L. Ntaimo and S. Sen and “The million-variable march for stochastic combinatorial optimization and” Journal of Global Optimization and vol. 32 and no. 3 and Pp. 385-400 and 2005.
[8]Asheim and D. Huybrechs and “Asymptotic analysis of numerical steepest descent with path approximations and” Foundations of Computational Mathematics and vol. 10 and no. 6 and Pp. 647-671 and 2010.
[9]M. Avriel and Nonlinear Programming: Analysis and Methods. Dover Publishing and 2003.
[10]B.W. Wah and Y.X. Chen and T. Wang and “Simulated annealing with asymptotic convergence for nonlinear constrained optimization and” Journal of Global Optimization and Vol. 39 and no. 1 and Pp. 1-37 and 2007.
[11]賴詩婷，結合序優化與人工蜂群演算法求解飯店訂房問題，碩士論文，朝陽科技大學資訊工程系，臺中，2013。
[12]Lars Junghans and Nicholas Darde and “Hybrid single objective genetic algorithm coupled with the simulated annealing optimization method for building optimization” and Energy and Buildings and Vol 86 and 2015 and Pp. 651-662.
[13]Nicoletta Kessaris and Lorenza Magno and Anna Noren Rubin and Marcio Guiomar Oliveira “Genetic programs controlling cortical interneuron fate” and Current Opinion in Neurobiology and Vol 26 and 2014 and Pp. 79-87.
[14]N. Moreira and T. Miranda and M. Pinheiro and P. Fernandes and D. Dias and L. Costa and J. Sena-Cruz “Back analysis of geomechanical parameters in underground works using an EVolution Strategy algorithm” and Tunnelling and Underground Space Technology and Vol 33 and 2013 and Pp. 143-158.
[15]Saúl Domínguez-Isidro and Efrén Mezura-Montes and Luis-Guillermo Osorio-Hernández and “EVolutionary programming for the length minimization of addition chains” and Engineering Applications of Artificial Intelligence and Vol 37 and 2015 and Pp. 125-134.
[16]D.Karaboga and B. Basturk and “A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm” and Journal of Global Optimization and November 2007 and Vol 39 and Issue 3 and Pp. 459-471.
[17]J.Kennedy and R.C. Eberhart and “Particle Swarm Optimization” and IEEE International Conference on Neural Networks and Vol 4 and 1995 and Pp. 1942-1948.
[18]Xu Zhou and Yanheng Liu and Jindong Zhang and Tuming Liu and Di Zhang “An ant colony based algorithm for overlapping community detection in complex networks” and Physica A: Statistical Mechanics and its Applications and Vol 427 and 2015 and Pp. 289-301.
[19]Hanning Chen and Ben Niu and Lianbo Ma and Weixing Su and Yunlong Zhu “Bacterial colony foraging optimization” and Neurocomputing and Vol 137 and 2014 and Pp. 268-284.
[20]Md. Abul Kalam Azad and Ana Maria A.C. Rocha and Edite M.G.P. Fernandes and “Improved binary artificial fish swarm algorithm for the 0–1 multidimensional knapsack problems” and Swam and EVolutionary Computation and Vol 14 and 2014 and Pp. 66-75.
[21]Erik Cuevas and Miguel Cienfuegos and Daniel Zaldívar and Marco Pérez-Cisneros “A swarm optimization algorithm inspired in the behavior of the social-spider” and Expert Systems with Applications and Vol 40 and Issue 16 and 2013 and Pp. 6374-6384.
[22]Wen-Tsao Pan and “A new Fruit Fly Optimization Algorithm: Taking the financial distress model as an example” and Knowledge-Based Systems and Vol 26 and 2012 and Pp. 69-74.
[23]Ayad Mashaan Turky and Salwani Abdullah and Nasser R. Sabar and “A Hybrid Harmony Search Algorithm for Solving Dynamic Optimisation Problems” and Procedia Computer Science and Vol 29 and 2014 and Pp. 1926-1936.
[24]Pinar Civicioglu and “Backtracking Search Optimization Algorithm for numerical optimization problems” and Applied Mathematics and Computation and Vol 219 and Issue 15 and 1 April 2013 and Pp. 8121–8144.
[25]L.J. Hong and B.L. Nelson and “Discrete optimization via simulation using COMPASS and” Operations Research and Vol. 54 and no. 1 and Pp. 115-129 and 2006.
[26]R. C. Eberhart and Y. Shi.“comparison between genetic algorithms and particle swarm optimization” and Annual Conference on EVolutionary Programming and San Diego and 1998.
[27]Y. Zheng and L. Ma and L. Zhang and and J. Qian and “Empirical study of particle sw optimizer with an increasing inertia weight”. Proceedings of IEEE Congress on EVolutionary Computation 2003 (CEC 2003) and Canbella and Australia and 2003. pp 221-226.