混合演算法求解客戶訂單導向產品組合之研究

Applying a Hybrid Algorithm to Solve Product Mix of Customer Orders Schedule Problems

陳厚光(Hou-Guang Chen)

指導教授 ： 陳平舜

中原大學/電機資訊學院/工業與系統工程研究所/碩士(2014年)

https://doi.org/10.6840/cycu201400268

摘要

本研究主要針對網路購物其有限制生產環境下面臨多樣化顧客訂單，期望能夠迅速決策出最佳的訂單生產組合，使該期總利潤最大。傳統顧客訂單問題為單一訂單僅含有單一產品，而本研究顧客訂單為單一訂單含有多種產品，並考慮產品組合的多變性以滿足顧客訂單。
本研究提出粒子群結合變動鄰域的混合演算法，並利用限制理論中的瓶頸資源概念來求解。本研究所提出的混合演算法，其中變動鄰域搜尋法使用兩種產生鄰近解的方式：第一種為在可行解中隨機選擇兩筆訂單，隨機與其它未被選擇之訂單進行交換；第二種是在可行解中選擇利潤最低的訂單，再隨機與其他未被選擇之訂單交換。本研究在程式設計上使用十進位轉二進位編碼技巧，來使粒子群速度和位移在大量訂單問題上更加快速收斂。本研究進行數值分析，其結果發現本研究所提混合演算法，在四種情境下其求解品質上皆優於基本粒子群演算法，雖然解算時間相較基本粒子群略久，但在可接受的時間內。

關鍵字

關鍵詞：產品組合、顧客訂單、限制理論、粒子群演算法、變動鄰域搜尋法

並列摘要

The study focused on online shopping companies with diversified customers’ orders under limited production resource environment. The objective of this research was to help companies make quick decisions of determining the optimal product mix of customers’ orders in order to maximize the total profits. Traditional customer orders problem considered that a single customer order had one product. However, this research considered that a single customer order contained multiple products, and considered the variability in product mix to satisfy customers’ orders.
The study proposed a hybrid algorithm that combined particle swarm optimization algorithm (PSO) with variable neighborhood search (VNS), and used the bottleneck resource concept based on theory of constraints (TOC) to solve product mix of customer orders scheduling problems. Two neighborhood searching heurisitics were developed for the proposed VNS: the first one was to randomly select two confirmed orders and two unconfirmed orders in a feasible solution and switch them. The second one was to choose the lowest-profit confirmed order in a feasible solution, and randomly choose one unconfirmed order to switch them. This study used bit conversion (from the 10 numerical system to the 2 numerical system) to write programming codes, so that the particle velocity and location of customer orders scheduling problems would converge much fast. According to numerical examples, the results of this research showed that solution quality of the proposed hybrid algorithm was better than that of the basic PSO in four scenarios. Although the proposed hybrid algorithm required longer computation time, the solving time was within acceptable range.

並列關鍵字

Keywords: Product mix ； Customer order ； Theory of Constraints ； Particle Swarm Optimization ； Variable neighborhood search.

參考文獻

[19] 李旺蒼，以粒子群最佳化為基礎之混合式全域搜尋演算法求解含凹形節線成本最小成本轉運問題之研究 ，國立中央大學土木工程學系，2006。

[22] 李維平，粒子群最佳化演算法改良之研究，中原大學資訊管理所，2008b。

[2] Betrand, J. W. M., & van Ooijen, H. P. G. (2008). Optimal work order release for make-to-order job shops with customer order lead-time costs, tardiness costs and work-in-process costs. International Journal of Production Economics, 116(2), 233-241.

[3] Chang Sup, S., & Sang Hum, Y. (1998). Minimizing total weighted completion time at a pre-assembly stage composed of two feeding machines. International Journal of Production Economics, 54(3), 247-255.

[4] Dekort, J. (1991). Knapsack-Problems, Algorithms and Computer Implementations - Martello,S, Toth,P. European Journal of Operational Research, 51(1), 145-146.