臺灣博碩士論文加值系統

在運籌學領域，作業車間調度問題被認為是常見問題之一，具有很多實際應用。由於 NP-hard（非確定性多項式時間）問題的性質，通常採用近似方法來解決此類問題。在論文框架中，結合兩種具有不同搜索策略的局部搜索技術（模擬退火和可變鄰域搜索），提出了一種新的受生物學啟發的元啟發式方法，稱為珊瑚礁優化。基於解決不同規模的作業車間調度問題來評估兩種混合算法的性能。結果與原始算法進行了比較，顯示了局部搜索技術對兩種混合算法的搜索效率的積極影響。此外，與其他兩種元啟發式算法的比較結果表明，兩種提出的混合算法的搜索能力與其他元啟發式方法相比具有相當的競爭力。

In the field of operational research, the job shop scheduling problem is considered as one of the common problems and has many practical applications. Due to the nature of the NP-hard (nondeterministic polynomial time) problem, approximation approaches are often applied to solve this type of problem. In the thesis framework, a novel biologically inspired metaheuristic method called coral reef optimization is proposed in combination with two local search techniques (simulated annealing and variable neighborhood search) with different search strategies. The performance of the two hybrid algorithms is evaluated based on solving different sizes of the job shop scheduling problem. The results are compared with the original algorithm, showing the positive impact of local search techniques on the search efficiency of the two hybrid algorithms. Furthermore, the results of the comparison with two other metaheuristic algorithms indicates that the search ability of the two proposed hybrid algorithms is quite competitive with other metaheuristic methods.

TABLE OF CONTENTS
CHAPTER 1. INTRODUCTION 1
1.1 Job shop scheduling problem in the study 1
1.1.1 Overview of job shop scheduling problem 1
1.1.2 Model of job shop scheduling problem 1
1.1.2.1 Complexity of job shop scheduling problem 3
1.1.2.2 Optimization criteria 3
1.1.2.3 Representation of solutions 4
1.1.2.4 Calculate makepsan value 5
1.2 Role of job shop scheduling problem in production scheduling 8
1.2.1 Production scheduling in manufacturing industry 8
1.2.2 Job-shop scheduling problems and applications 9
CHAPTER 2. LITERATURE REVIEW 12
2.1 Solution approaches for job shop scheduling problem 12
2.1.1 Exact algorithms 12
2.1.2 Approximate algorithms 13
2.1.2.1 Heuristic Algorithms 13
2.1.2.2 Meta-Heuristic Algorithms 14
2.2 Related metaheuristic optimization algorithms 15
2.2.1 Genetic algorithm approach (GA) 15
2.2.1.1 Overview 15
2.2.1.2 Genetic algorithm 16
2.2.2 Local search technique 17
2.2.2.1 Simulated Annealing 18
2.2.2.2 Variable Neighborhood Search 21
2.2.3 Coral reef optimization approach 23
2.2.3.1 Overview 23
2.2.3.2 Coral reef optimization algorithm 24
CHAPTER 3. PROPOSAL APPROACH 27
3.1 Representation of job shop scheduling problem 27
3.1.1 Representation of the problem 27
3.1.2 Objective function 28
3.2 Hybrid Coral Reef Optimization Algorithm 29
3.2.1 Local search strategy 29
3.2.1.1 The hybrid algorithm CROLS1 30
3.2.1.2 The hybrid algorithm CROLS2 32
3.2.2 Implementation of the hybrid algorithm 33
CHAPTER 4. EXPERIMENT RESULTS 40
4.1 Initial setting 40
4.1.1 Dataset of job shop scheduling problem 40
4.1.2 Parameters use in the algorithm 41
4.1.3 Recommended parameters for settings 41
4.2 Experimental results on job shop scheduling instances 42
4.2.1 Comparison between two hybrid algorithms and original algorithm 42
4.2.1.1 Finding optimal solution 42
4.2.1.2 Performance improvement 46
4.2.1.3 Convergence to optimal solution 49
4.2.2 Comparison between two hybrid algorithms with another metaheuristic algorithm 52
4.2.3 Summary results 54
CHAPTER 5. CONCLUSION 56
5.1 Contributions 56
5.2 Future work 57
REFERENCES 58

REFERENCES
[1]S. M. Johnson, “Optimal two‐and three‐stage production schedules with setup times included,” Naval research logistics quarterly, vol. 1, no. 1, pp. 61–68, 1954.
[2]M. R. Garey, D. S. Johnson, and R. Sethi, “The complexity of flow shop and job shop scheduling,” Mathematics of operations research, vol. 1, no. 2, pp. 117–129, 1976.
[3]J. Zhang, G. Ding, Y. Zou, S. Qin, and J. Fu, “Review of job shop scheduling research and its new perspectives under Industry 4.0,” Journal of Intelligent Manufacturing, vol. 30, no. 4, pp. 1809–1830, 2019.
[4]“Job-shop scheduling,” Wikipedia. May 04, 2022. Accessed: May 07, 2022. [Online]. Available: https://en.wikipedia.org/w/index.php?title=Job-shop_scheduling&oldid=1086161280
[5]H. Xiong, S. Shi, D. Ren, and J. Hu, “A survey of job shop scheduling problem: the types and models,” Computers & Operations Research, p. 105731, 2022.
[6]A. Türkyılmaz, Ö. Şenvar, İ. Ünal, and S. Bulkan, “A research survey: heuristic approaches for solving multi objective flexible job shop problems,” Journal of Intelligent Manufacturing, vol. 31, no. 8, pp. 1949–1983, 2020.
[7]F. Xhafa and A. Abraham, Metaheuristics for scheduling in industrial and manufacturing applications, vol. 128. Springer, 2008.
[8]M. Pinedo, Planning and scheduling in manufacturing and services. Springer, 2005.
[9]S. Muthuraman and V. P. Venkatesan, “A comprehensive study on hybrid meta-heuristic approaches used for solving combinatorial optimization problems,” in 2017 world congress on computing and communication technologies (WCCCT), 2017, pp. 185–190.
[10]B. Çaliş and S. Bulkan, “A research survey: review of AI solution strategies of job shop scheduling problem,” Journal of Intelligent Manufacturing, vol. 26, no. 5, pp. 961–973, 2015.
[11]M. Gendreau and J.-Y. Potvin, “Metaheuristics in combinatorial optimization,” Annals of Operations Research, vol. 140, no. 1, pp. 189–213, 2005.
[12]X.-S. Yang, Nature-inspired optimization algorithms. Academic Press, 2020.
[13]L. Davis, “Job shop scheduling with genetic algorithms,” in Proceedings of an international conference on genetic algorithms and their applications, 1985, vol. 140.
[14]J. Kennedy and R. Eberhart, “Particle swarm optimization,” in Proceedings of ICNN’95-international conference on neural networks, 1995, vol. 4, pp. 1942–1948.
[15]S. Kirkpatrick, C. D. Gelatt Jr, and M. P. Vecchi, “Optimization by simulated annealing,” science, vol. 220, no. 4598, pp. 671–680, 1983.
[16]J. H. Holland, Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. MIT press, 1992.
[17]R. Nakano and T. Yamada, “Conventional genetic algorithm for job shop problems.,” in ICGA, 1991, vol. 91, pp. 474–479.
[18]E. Aarts, E. H. Aarts, and J. K. Lenstra, Local search in combinatorial optimization. Princeton University Press, 2003.
[19]“Local optimum,” Wikipedia. Apr. 29, 2020. Accessed: May 07, 2022. [Online]. Available: https://en.wikipedia.org/w/index.php?title=Local_optimum&oldid=953841396
[20]“Simulated annealing,” Wikipedia. Mar. 27, 2022. Accessed: May 07, 2022. [Online]. Available: https://en.wikipedia.org/w/index.php?title=Simulated_annealing&oldid=1079578440
[21]N. Mladenović and P. Hansen, “Variable neighborhood search,” Computers & operations research, vol. 24, no. 11, pp. 1097–1100, 1997.
[22]P. Hansen, N. Mladenović, and D. Urošević, “Variable neighborhood search for the maximum clique,” Discrete Applied Mathematics, vol. 145, no. 1, pp. 117–125, 2004.
[23]“Variable neighborhood search,” Wikipedia. Jun. 27, 2021. Accessed: May 07, 2022. [Online]. Available: https://en.wikipedia.org/w/index.php?title=Variable_neighborhood_search&oldid=1030774399
[24]S. Salcedo-Sanz, J. Del Ser, I. Landa-Torres, S. Gil-López, and J. A. Portilla-Figueras, “The coral reefs optimization algorithm: a novel metaheuristic for efficiently solving optimization problems,” The Scientific World Journal, vol. 2014, 2014.
[25]L. García-Hernández, L. Salas-Morera, C. Carmona-Muñoz, A. Abraham, and S. Salcedo-Sanz, “A hybrid coral reefs optimization—Variable neighborhood search approach for the unequal area facility layout problem,” IEEE Access, vol. 8, pp. 134042–134050, 2020.
[26]C.-W. Tsai, H.-C. Chang, K.-C. Hu, and M.-C. Chiang, “Parallel coral reef algorithm for solving jsp on spark,” in 2016 IEEE International Conference on Systems, Man, and Cybernetics (SMC), 2016, pp. 001872–001877.
[27]R. Cheng, M. Gen, and Y. Tsujimura, “A tutorial survey of job-shop scheduling problems using genetic algorithms—I. Representation,” Computers & industrial engineering, vol. 30, no. 4, pp. 983–997, 1996.
[28]R. Cheng, M. Gen, and Y. Tsujimura, “A tutorial survey of job-shop scheduling problems using genetic algorithms, part II: hybrid genetic search strategies,” Computers & Industrial Engineering, vol. 36, no. 2, pp. 343–364, 1999.
[29]Y. Wang, “A new hybrid genetic algorithm for job shop scheduling problem,” Computers & Operations Research, vol. 39, no. 10, pp. 2291–2299, 2012.
[30]L. Gao, G. Zhang, L. Zhang, and X. Li, “An efficient memetic algorithm for solving the job shop scheduling problem,” Computers & Industrial Engineering, vol. 60, no. 4, pp. 699–705, 2011.
[31]Cuong Nguyen-Dinh, Tuan Nguyen-Thanh, Chin-Shiuh Shieh, Mong-Fong Horng, “Hybrid coral reef optimization with local search for job shop scheduling problem,” Digital Life Technology Symposium, Taiwan, 2022.