流程生產環境在眾多產業中廣泛存在，如何找到最佳的生產順序以減少時間的浪費一直是研究的重點。目前，基因演算法是解決排程問題常用的方法之一，能夠在可行的時間內找到可行解或最佳解，適用於大量的排列問題。然而，傳統的基因演算法容易產生不可行解，增加了計算時間。因此，在本研究中我們採用了有偏隨機密鑰基因演算法來解決不可行解的問題。為了提升演算法的局部搜索能力，我們結合了禁忌搜尋與模擬退火演算法，以實現對局部區域的快速有效搜索，平衡全局和局部搜索能力。我們使用Taillard的120個問題實例來測試演算法的性能，並通過實驗設計找出最佳的參數設置。在實驗結果中，相對於HGSA和GA-TS，HGATS-SA在統計上具有顯著優勢，且演算法的變異數也小於CHFPSO。因此，我們提出的演算法能夠有效解決流程生產問題。

The optimization of production sequencing has been a prominent research area in various industries characterized by production environments. Genetic Algorithm (GA) has emerged as a popular approach for solving sequencing problems, as it can provide feasible or optimal solutions within a reasonable timeframe, particularly for a large number of permutation problems. However, the conventional GA may encounter challenges in generating feasible solutions, leading to increased computational efforts. To address this issue, the Biased Random Key Genetic Algorithm (BRKGA) is employed in this study to tackle infeasible solution problems. Additionally, a combination of Tabu Search and Simulated Annealing algorithms is implemented to enhance the algorithm's local search capability, facilitating efficient and rapid searches within local regions while maintaining a balance between global and local search capabilities. The proposed algorithm's performance is evaluated using Taillard's 120 problem instances, and an experimental design is applied to identify the optimal parameter settings. The experimental results demonstrate that HGATS-SA exhibits significant improvements compared to HGSA and GA-TS algorithms. Furthermore, the algorithm demonstrates lower variance compared to CHFPSO. As a result, the algorithm proposed in this study effectively addresses production sequencing problems.

Ahmad, M. F., Isa, N. A. M., Lim, W. H., & Ang, K. M. (2022). Differential evolution: A recent review based on state-of-the-art works. Alexandria EngineeringJournal,61(5),3831-3872https://doi.org/10.1016/j.aej.2021.09.013
ARIK, O. A. (2022). Genetic algorithm application for permutation flow shop scheduling problems. Gazi University Journal of Science, 35(1), 92-111.
Abreu, L. R., Tavares-Neto, R. F., & Nagano, M. S. (2021). A new efficient biased random key genetic algorithm for open shop scheduling with routing by capacitated single vehicle and makespan minimization. Engineering Applications of Artificial Intelligence, 104, 104373
Bank, M., Fatemi Ghomi, S. M. T., Jolai, F., & Behnamian, J. (2012). Application of particle swarm optimization and simulated annealing algorithms in flow shop scheduling problem under linear deterioration. Advances in Engineering Software, 47(1), 1-6. https://doi.org/10.1016/j.advengsoft.2011.12.001
Bean, J. C. (1994). Genetic Algorithms and Random Keys for Sequencing and Optimization. ORSA Journal on Computing, 6(2), 154-160. https://doi.org/10.1287/ijoc.6.2.154
Ben-Daya, M., & Al-Fawzan, M. (1998). A tabu search approach for the flow shop scheduling problem. European Journal of Operational Research, 109(1), 88-95.
Blum, C., Puchinger, J., Raidl, G. R., & Roli, A. (2011). Hybrid metaheuristics in combinatorial optimization: A survey. Applied Soft Computing, 11(6), 4135-4151. https://doi.org/10.1016/j.asoc.2011.02.032
Brammer, J., Lutz, B., & Neumann, D. (2022). Permutation flow shop scheduling with multiple lines and demand plans using reinforcement learning. European Journal of Operational Research, 299(1), 75-86. https://doi.org/10.1016/j.ejor.2021.08.007
Baker, K. R., & Trietsch, D. (2013). Principles of sequencing and scheduling. John Wiley & Sons.
Chen, C.-F., Wu, M.-C., & Lin, K.-H. (2013). Effect of solution representations on Tabu search in scheduling applications. Computers & Operations Research, 40(12), 2817-2825. https://doi.org/10.1016/j.cor.2013.06.003
Dai, M., Tang, D., Giret, A., Salido, M. A., & Li, W. D. (2013). Energy-efficient scheduling for a flexible flow shop using an improved genetic-simulated annealing algorithm. Robotics and Computer-Integrated Manufacturing, 29(5), 418-429. https://doi.org/10.1016/j.rcim.2013.04.001
Damm, R. B., Resende, M. G. C., & Ronconi, D. P. (2016). A biased random key genetic algorithm for the field technician scheduling problem. Computers&OperationsResearch,75,49-63. https://doi.org/10.1016/j.cor.2016.05.003
Gümüşçü, A., Kaya, S., Tenekeci, M. E., Karaçizmeli, İ. H., & Aydilek, İ. B. (2022). The impact of local search strategies on chaotic hybrid firefly particle swarm optimization algorithm in flow-shop scheduling. Journal of King Saud University – Computer and Information Sciences, 34(8), 6432-6440. https://doi.org/10.1016/j.jksuci.2021.07.017
Geurtsen, M., Didden, J. B. H. C., Adan, J., Atan, Z., & Adan, I. (2023). Production, maintenance and resource scheduling: A review. European Journal of Operational Research, 305(2), 501-529. https://doi.org/10.1016/j.ejor.2022.03.045
Glover, F. (1986). Future paths for integer programming and links to artificial intelligence. Computers & Operations Research, 13(5), 533-549.
Glover, F., & Laguna, M. (1998). Tabu search. Springer.
Gonçalves, J. F., & Resende, M. G. (2014). An extended Akers graphical method with a biased random‐key genetic algorithm for job‐shop scheduling. International Transactions in Operational Research, 21(2), 215-246
Gonçalves, J. F. (2015). A hybrid biased random key genetic algorithm for a production and cutting problem. IFAC-PapersOnLine, 48(3), 496-500.
Gonçalves, J. F., & Resende, M. G. C. (2010). Biased random-key genetic algorithms for combinatorial optimization. Journal of Heuristics, 17(5), 487-525. https://doi.org/10.1007/s10732-010-9143-1
Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. R. (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. In Annals of discrete mathematics (Vol. 5, pp. 287-326). Elsevier.
Guzman, E., Andres, B., & Poler, R. (2022). Models and algorithms for production planning, scheduling and sequencing problems: A holistic framework and a systematic review. Journal of Industrial Information Integration, 27. https://doi.org/10.1016/j.jii.2021.100287
Harbaoui, H., & Khalfallah, S. (2020). Tabu-search optimization approach for no-wait hybrid flow-shop scheduling with dedicated machines. Procedia Computer Science, 176, 706-712.
Li, X., & Gao, L. (2016). An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem. International Journal of Production Economics, 174, 93-110. https://doi.org/10.1016/j.ijpe.2016.01.016
Li, Y., Li, X., Gao, L., Fu, L., & Wang, C. (2022). An efficient critical path based method for permutation flow shop scheduling problem. Journal of Manufacturing Systems, 63, 344-353. https://doi.org/10.1016/j.jmsy.2022.04.005
Liaw, C.-F. (2003). An efficient tabu search approach for the two-machine preemptive open shop scheduling problem. Computers & Operations Research, 30(14), 2081-2095. https://doi.org/10.1016/s0305-0548(02)00124-7
Liu, L. (2019). Outsourcing and rescheduling for a two-machine flow shop with the disruption of new arriving jobs: A hybrid variable neighborhood search algorithm. Computers & Industrial Engineering, 130, 198-221. https://doi.org/10.1016/j.cie.2019.02.015
McClintock, B. (1951). Chromosome organization and genic expression. Cold Spring Harbor symposia on quantitative biology.
Osman, I. H., & Potts, C. (1989). Simulated annealing for permutation flow-shop scheduling. Omega, 17(6), 551-557.
Pan, Q.-K., & Ruiz, R. (2013). A comprehensive review and evaluation of permutation flowshop heuristics to minimize flowtime. Computers & Operations Research, 40(1), 117-128. https://doi.org/10.1016/j.cor.2012.05.018
Ripon, K. S. N., Tsang, C.-H., & Kwong, S. (2006). Multi-objective evolutionary job-shop scheduling using jumping genes genetic algorithm. The 2006 IEEE International Joint Conference on Neural Network Proceedings
Rahman, H. F., Sarker, R., & Essam, D. (2015). A genetic algorithm for permutation flow shop scheduling under make to stock production system. Computers & Industrial Engineering, 90, 12-24. https://doi.org/10.1016/j.cie.2015.08.006
Ramesh, C., Kamalakannan, R., Karthik, R., Pavin, C., & Dhivaharan, S. (2021). A lot streaming based flow shop scheduling problem using simulated annealing algorithm. Materials Today: Proceedings, 37, 241-244. https://doi.org/10.1016/j.matpr.2020.05.108
Seyed-Alagheband, S., Davoudpour, H., Doulabi, S., & Khatibi, M. (2009). Using a modified simulated annealing algorithm to minimize makespan in a permutation flow-shop scheduling problem with job deterioration. Proceedings of the world congress on engineering and computer science,
Sukkerd, W., & Wuttipornpun, T. (2016). Hybrid genetic algorithm and tabu search for finite capacity material requirement planning system in flexible flow shop with assembly operations. Computers & Industrial Engineering, 97, 157-169. https://doi.org/10.1016/j.cie.2016.05.006
Shao, W., Pi, D., & Shao, Z. (2016). A hybrid discrete optimization algorithm based on teaching–probabilistic learning mechanism for no-wait flow shop scheduling. Knowledge-Based Systems, 107, 219-234. https://doi.org/10.1016/j.knosys.2016.06.011
Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2), 278-285.
Thamilselvan, R., & Balasubramanie, P. (2012). Integrating genetic algorithm, tabu search and simulated annealing for job shop scheduling problem. International Journal of Computer Applications, 48(5), 42-54.
Tayeb, F. B.-S., Bessedik, M., Benbouzid, M., Cheurfi, H., & Blizak, A. (2017). Research on permutation flow-shop scheduling problem based on improved genetic immune algorithm with vaccinated offspring. Procedia Computer Science, 112, 427-436.
Umam, M. S., Mustafid, M., & Suryono, S. (2022). A hybrid genetic algorithm and tabu search for minimizing makespan in flow shop scheduling problem. Journal of King Saud University - Computer and Information Sciences, 34(9), 7459-7467. https://doi.org/10.1016/j.jksuci.2021.08.025
Garey, M. R., Johnson, D. S., & Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. Mathematics of operations research, 1(2), 117-129.
Gonçalves, J. F., & Resende, M. G. (2011). Biased random-key genetic algorithms for combinatorial optimization. Journal of Heuristics, 17(5), 487-525.
Lalla-Ruiz, E., González-Velarde, J. L., Melián-Batista, B., & Moreno-Vega, J. M. (2014). Biased random key genetic algorithm for the tactical berth allocation problem. Applied Soft Computing, 22, 60-76.
Wei, H., Li, S., Jiang, H., Hu, J., & Hu, J. (2018). Hybrid genetic simulated annealing algorithm for improved flow shop scheduling with makespan criterion. Applied Sciences, 8(12), 2621
Zhang, H., Liu, F., Zhou, Y., & Zhang, Z. (2020). A hybrid method integrating an elite genetic algorithm with tabu search for the quadratic assignment problem. Information Sciences, 539, 347-374.