整數型回溯搜索最佳化演算法求解訂單式組裝系統庫存管控問題

An Integer Backtracking Search Optimization Algorithm for Solving Inventory Control Problem of Assemble-To-Order System

何信威(Hsin-Wei Ho)

指導教授 ： 洪士程

朝陽科技大學/資訊學院/資訊工程系/碩士(2015年)

摘要

在本篇論文中，提出一個整數型回溯搜索最佳化演算法(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.

並列關鍵字

base stock level ； inventory control ； assemble-to-order system ； An Integer Backtracking Search Optimization Algorithm ； combinatorial optimization problem with integer variables

參考文獻

[11] 賴詩婷，結合序優化與人工蜂群演算法求解飯店訂房問題，碩士論文，朝陽科技大學資訊工程系，臺中，2013。

[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.

[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.

[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.