本研究中，我們主要探討半導體最終測試排程問題 (Semiconductor Final Testing Scheduling Problem, SFTSP)，此一問題的目的為針對相互關聯的操作組成的工作做排程，從而完成此工作的目標。在文獻中已知 SFTSP 是一種 NP-困難 (NP-hard) 的問題，由於問題的難解性，許多的研究成果以各種泛用啟發式演算法為重點解決此問題，試圖在合理的計算成本中獲得令人滿意的最理想解。然而，在現實中大多的演算法解決 SFTSP 時仍然有改進的空間。因此，我們根據灰狼最佳化演算法提出改善的方法，此一方法的特性為透過採用適應性步長機制，可在開發和探索之間達到適當的平衡。實驗結果顯示我們提出的方法對於半導體最終測試排程問題是有效的。

In this study, we consider the semiconductor final testing scheduling problem (SFTSP). Semiconductor final testing scheduling aims at scheduling a job consisting of interrelated operations and consequently achieving the objectives of the job. The SFTSP is known to be NP-hard in the literature. Due to the intractability of the problem, numerous research efforts have focused on various metaheuristics to acquire satisfactory suboptimal solutions within a reasonable amount of computation cost. However, most realistic algorithms for solving the SFTSP still remain to be improved. On the basis of grey wolf optimization, we therefore propose an improved approach. This approach can be characterized by employing an adaptive step-length mechanism to achieve an appropriate balance between exploitation and exploration. Experimental results demonstrate that the proposed algorithm is efficacious for semiconductor final testing scheduling.

中文摘要 i
ABSTRACT ii
誌謝 iii
目錄 iv
表目錄 vii
圖目錄 x
壹、緒論 1
一、動機與目的 1
二、論文架構 2
貳、問題塑模 3
參、相關研究 9
一、布穀鳥搜尋演算法 9
(一) 布穀鳥行為 9
(二) 布穀鳥行為的數學模型 9
(三) 用以解決半導體最終測試排程問題之布穀鳥搜尋 11
二、入侵雜草最佳化演算法 16
(一) 設計構想 16
(二) 用以解決半導體最終測試排程問題之入侵雜草最佳化演算法 18
三、知識庫多智能演化演算法 23
(一) 設計構想 23
(二) 用以解決半導體最終測試排程問題之知識庫多智能演化演算法 24
四、果蠅最佳化演算法 28
(一) 設計構想 28
(二) 用以解決半導體最終測試排程問題之果蠅最佳化演算法 29
五、分佈估計演算法 32
(一) 用以解決半導體最終測試排程問題之協同的分佈估計演算法 32
(二) 用以解決半導體最終測試排程問題之混合的分佈估計演算法 34
(三) 用以解決半導體最終測試排程問題之緊湊的分佈估計演算法 36
六、灰狼最佳化演算法 38
(一) 灰狼靈感 38
(二) 灰狼狩獵的數學模型 39
(三) 二進制領域的進化和適應性遺傳增強灰狼最佳化演算法 43
肆、設計方法 47
一、方法總覽 47
二、改善式灰狼最佳化演算法 49
(一) 初始化族群 49
(二) 灰狼狩獵階段 50
(三) 適應性步長階段 51
(四) 菁英選擇和競爭式選擇 53
(五) 突變運算 54
三、實例說明 55
伍、實驗效能分析與比較 65
一、實驗設計 65
二、以 IGWO 解半導體最終測試排程問題的實驗比較 66
三、IGWO 內部方法修改的實驗比較 70
陸、結論 75
參考文獻 76

[1]J.-Z. Wu and C.-F. Chien, “Modeling semiconductor testing job scheduling and dynamic testing machine configuration,” Expert Systems with Applications, vo1. 35, no. 1-2, pp. 485-496, July–August 2008.

[2]J.-Z Wu, X.-C. Hao, C.-F Chien, and M. Gen, “A novel bi-vector encoding genetic algorithm for the simultaneous multiple resources scheduling problem,” Journal of Intelligent Manufacturing, vol. 23, no. 6, pp. 2255-2270, December 2012.

[3]X.-C. Hao, J.-Z. Wu, C.-F. Chien, and M. Gen, “The cooperative estimation of distribution algorithm: a novel approach for semiconductor final test scheduling problems,” Journal of Intelligent Manufacturing, vol. 25, no. 5, pp. 867-879, October 2014.

[4]S. Wang and L. Wang, “Compact Estimation of Distribution Algorithm for Semiconductor Final Testing Scheduling Problem,” In Proceedings of 2014 IEEE International Conference on Automation Science and Engineering, pp. 113-118, August 2014.

[5]S. Wang, L. Wang, and, M. Liu, and Y. Xu, “A hybrid estimation of distribution algorithm for the semiconductor final testing scheduling problem,” Journal of Intelligent Manufacturing, vol. 26, no. 5, pp. 861-871, October 2015.

[6]S. Wang and L. Wang, “A knowledge-based multi-agent evolutionary algorithm for semiconductor final testing scheduling problem,” Knowledge-Based Systems, vol. 84, pp. 1-9, August 2015.

[7]X.-l. Zheng, L. Wang, and S.-y. Wang, “A novel fruit fly optimization algorithm for the semiconductor final testing scheduling problem,” Knowledge-Based Systems, vol. 57, pp. 95-103, February 2014.

[8]Z.C. Cao, C.R. Lin, M.C. Zhou, and R. Huang, “Scheduling Semiconductor Testing Facility by Using Cuckoo Search Algorithm With Reinforcement Learning and Surrogate Modeling,” IEEE Transactions on Automation Science and Engineering, vol. 16, no. 3, pp. 825-837, April 2019.

[9]H.Y. Sang, P.Y. Duan, and J.Q. Li, “An effective invasive weed optimization algorithm for scheduling semiconductor final testing problem,” Swarm and Evolutionary Computation, vol. 38, pp. 42-53, February 2018.

[10]S. Mirjalili, S.M. Mirjalili, and, A. Lewis, “Grey Wolf Optimizer,” Advances in Engineering Software, vol. 69, pp.46-61, March 2014.

[11]İ. Gölcük and F.B. Ozsoydan, “Evolutionary and adaptive inheritance enhanced Grey Wolf Optimization algorithm for binary domains,” Knowledge-Based Systems, vol. 194, April 2020.

[12]F.B. Ozsoydan and A. Baykasoglu, “A swarm intelligence-based algorithm for the set-union knapsack problem,” Future Generation Computer Systems, vol. 93, pp. 560-569, April 2019.

[13]A. Baykasoglu, “Design optimization with chaos embedded great deluge algorithm,” Applied Soft Computing, vol. 12, no. 3, pp. 1055-1067, March 2012.

[14]X.-S. Yang and S. Deb, “Cuckoo Search via Lévy flights,” In Proceedings of the 2009 World Congress on Nature & Biologically Inspired Computing, pp. 210-214, December 2009.

[15]I. Pavlyukevich, “Cooling down Lévy flights,” Journal of Physics A: Mathematical and Theoretical, vol. 40, no. 41, pp. 12299-12313, October 2007.

[16]I. Pavlyukevich, “Lévy flights, non-local search and simulated annealing,” Journal of Computational Physics, vol. 226, no. 2, pp. 1830-1844, October 2007.

[17]C.T. Brown, L.S. Liebovitch, and R. Glendon, “Lévy Flights in Dobe Ju/’hoansi Foraging Patterns,” Human Ecology, vol. 35, no. 1, pp. 129-138, February 2007.

[18]Z. Zhang, L. Zheng, F. Hou, and N. Li, “Semiconductor final test scheduling with Sarsa(λ,k) algorithm,” European Journal of Operational Research, vol. 215, no. 2, pp. 446-458, December 2011.

[19]A.R. Mehrabian and C. Lucas, “A novel numerical optimization algorithm inspired from weed colonization,” Ecological Informatics, vol. 1, no. 4, pp. 355-366, December 2006.

[20]M. Yuchi and J.-H. Kim, “Ecology-inspired evolutionary algorithm using feasibility-based grouping for constrained optimization,” In Proceedings of 2005 IEEE Congress on Evolutionary Computation, vol. 2, pp. 1455-1461, September 2005.

[21]W.-T. Pan, “A new Fruit Fly Optimization Algorithm: Taking the financial distress model as an example,” Knowledge-Based Systems, vol. 26, pp.69-74, February 2012.

[22]M. Dorigo and L.M. Gambardella, “Ant colony system: a cooperative learning approach to the traveling salesman problem,” IEEE Transactions on Evolutionary Computation, vol. 1, no. 1, pp. 53-66, April 1997.

[23]X.-S. Yang, “Firefly Algorithms for Multimodal Optimization,” In Proceedings of the Stochastic Algorithms: Foundations and Applications, SAGA 2009, vol. 5792, pp. 169-178, October 2009.

[24]X. Wang, L. Gao, C. Zhang, and X. Shao, “A multi-objective genetic algorithm based on immune and entropy principle for flexible job-shop scheduling problem,” The International Journal of Advanced Manufacturing Technology, vol. 51, no. 5-8, pp. 757-767, November 2010.

[25]K.C. Tan, Y.J. Yang, and C.K. Goh, “A distributed Cooperative coevolutionary algorithm for multiobjective optimization,” IEEE Transactions on Evolutionary Computation, vol. 10, no. 5, pp. 527-549, October 2006.

[26]S. Baluja and R. Caruana, “Removing the Genetics from the Standard Genetic Algorithm,” In Proceedings of the Twelfth International Conference on International Conference on Machine Learning, pp. 38-46, July 1995.

[27]L. Wang, S. Wang, and Y. Xu, “An effective hybrid EDA-based algorithm for solving multidimensionalknapsack problem,” Expert Systems with Applications, vol. 39, no. 5, pp. 5593-5599, April 2012.

[28]L.D. Mech, “Alpha status, dominance, and division of labor in wolf packs,” Canadian Journal of Zoology, vol. 77, no. 8, pp. 1196-1203, November 1999.

[29]C. Muroa, R. Escobedoa, L. Spectorc, and R.P. Coppinger, “Wolf-pack (Canis lupus) hunting strategies emerge from simple rules in computational simulations,” Behavioural Processes, vol. 88, no. 3, pp. 192-197, November 2011.

[30]D. Simon, Evolutionary Optimization Algorithms, John Wiley & Sons Inc, New York, April 2013.

[31]A.E. Eiben, “Multiparent Recombination in Evolutionary Computing,” Advances in Evolutionary Computing, pp. 175-192, Springer, 2003.

[32]A. Baykasoğlu and F.B. Ozsoydan, “Adaptive firefly algorithm with chaos for mechanical design optimization problems,” Applied Soft Computing, vol. 36, pp. 152-164, November 2015.

[33]Y. He, H. Xie, T.-L. Wong, and X. Wang, “A novel binary artificial bee colony algorithm for the set-union knapsack problem,” Future Generation Computer Systems, vol. 78, pp. 77-86, January 2018.