Translated Titles

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



Key Words

關鍵詞:產品組合、顧客訂單、限制理論、粒子群演算法、變動鄰域搜尋法 ; Keywords: Product mix ; Customer order ; Theory of Constraints ; Particle Swarm Optimization ; Variable neighborhood search.



Volume or Term/Year and Month of Publication


Academic Degree Category




Content Language


Chinese Abstract

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

English Abstract

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.

Topic Category 電機資訊學院 > 工業與系統工程研究所
工程學 > 工程學總論
  1. [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.
  2. [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.
  3. [4] Dekort, J. (1991). Knapsack-Problems, Algorithms and Computer Implementations - Martello,S, Toth,P. European Journal of Operational Research, 51(1), 145-146.
  4. [5] Eberhart, R., & Kennedy, J. (1995, 4-6 Oct 1995). A new optimizer using particle swarm theory. Paper presented at the Micro Machine and Human Science, 1995. MHS '95., Proceedings of the Sixth International Symposium on,39-43.
  5. [7] Hansen, P., Mladenovic, N., & Perez, J. A. M. (2008). Variable neighborhood search. European Journal of Operational Research, 191(3), 593-595.
  6. [10] Lin, B. M. T., & Kononov, A. V. (2007). Customer order scheduling to minimize the number of late jobs. European Journal of Operational Research, 183(2), 944-948.
  7. [12] Onwubolu, G. C., & Mutingi, M. (2003). A genetic algorithm approach for the cutting stock problem. Journal of Intelligent Manufacturing, 14(2), 209-218.
  8. [13] Ratnaweera, A., Halgamuge, S. K., & Watson, H. C. (2004). Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients. IEEE Transactions on Evolutionary Computation, 8(3), 240-255.
  9. [14] Su, L. H., Chen, P. S., & Chen, S. Y. (2013). Scheduling on parallel machines to minimise maximum lateness for the customer order problem. International Journal of Systems Science, 44(5), 926-936.
  10. [15] Tanhaei, F., & Nahavandi, N. (2013). Algorithm for solving product mix problem in two-constraint resources environment. International Journal of Advanced Manufacturing Technology, 64(5-8), 1161-1167.
  11. [16] Wang, G. Q., & Cheng, T. C. E. (2007). Customer order scheduling to minimize total weighted completion time. Omega-International Journal of Management Science, 35(5), 623-626.
  12. [17] Yang, J., & Posner, M. E. (2005). Scheduling parallel machines for the customer order problem. Journal of Scheduling, 8(1), 49-74.
  13. [18] 吳佳娟,變動鄰域尋優法於串並聯系統複置配置問題之研究,元智大學工業工程與管理學系,2004。
  14. [19] 李旺蒼,以粒子群最佳化為基礎之混合式全域搜尋演算法求解含凹形節線成本最小成本轉運問題之研究 ,國立中央大學土木工程學系,2006。
  15. [21] 李維平,自適應慣性權重改良粒子群演算法之研究,中原大學資訊管理所 ,2008a。
  16. [22] 李維平,粒子群最佳化演算法改良之研究,中原大學資訊管理所,2008b。
  17. [24] 洪毫寓,在CTO 環境下考量潛在性訂單之多產品多廠區產能配置模式發展,中原大學工業與系統工程學系,2009。
  18. 參考文獻
  19. [1] Armstrong, K. (1996). Principles of Marketing (Vol. 7). Upper Seddle River: Prentice-Hall.
  20. [6] Goldratt. (1990). What is this thing called the Theory of Constraints? Croton-on-Hudson,NY: North River Press.
  21. [8] Huang, C.-Y.,Product Mix Planning Problem in Customer Order Oriented Environment,Department of Business Administration,2014。
  22. [9] Lee, C. H., Liao, C. J., & Chao, C. W. (2012). Scheduling with multi-attribute setup times. Computers & Industrial Engineering, 63(2), 494-502.
  23. [11] Ning, Z. (2010). Application of particle swarm optimization in generate alternative schemes for urban planning. Journal of Northeast Normal University(Natural Science Edition), 42(2).
  24. [20] 李家豪,KD技術指標之類神經模糊交易決策支援系統,靜宜大學企業管理學系,2001。
  25. [23] 林湘沅,應用作業研究技術於醫療保健管理問題,國立臺灣科技大學管理研究所,2010。
  26. [25] 陳香伶,應用變動鄰域搜尋法於投資組合最佳化問題之研究,桃園創新技術學院財務金融系,2010。
  27. [26] 黃祥熙,多廠區訂單分配最佳化之探討,兩岸工業工程與管理學術研討會,2011。
  28. [27] 劉錫明,多重物料限制下產出導向的產品組合問題,華梵大學工業管理學系,2004。