臺灣博碩士論文加值系統

不銹鋼作為製造業的重要材料，素有「工業之母」之稱，在該產業中的機台皆因大型產品加工的因素導致機台佔地廣闊，導致在同一產線上會有多種產品交替生產，不同製程也需要經過不同機台進行加工，也因如此，在這樣零工式的生產排程環境下，會額外產生許多的生產限制及製程轉換的整備時間，亦大幅加深生產排程的難度。
本研究運用基因演算法、修正式 NEH（Nawaz-Enscore-Ham）演算法及局部搜索法所組合而成的混合型基因演算法來建構本研究之排程模型。首先，需要釐清各產線間的限制條件、製程轉換的整備時間及生產加工時間，接著使用訂單資料及生產途程作為基礎資料。本研究之研究方法先以最早交期時間優先派工法則（Earliest Due Date，EDD）搭配現況排程方法產生初始解，接著透過基因演算法廣泛性搜索的特性，再加上修正式NEH 演算法及局部搜索法強化搜索的深度，在目標函數上選擇多目標績效，考慮到半成品成本、快速出貨及短交期的訂單需求，以最小總完工時間、最小總延遲時間以及最小總 WIP 等待時間作為排程的績效目標進行優劣比較，來找尋優於現況排程手法的可行解。
研究結果顯示，混合型基因演算法在總完工時間目標上與傳統型基因演算法一致，但在最小總延遲時間及最小總 WIP 等待時間目標上皆明顯優於傳統基因演算法，且在程式執行時間上也較現況排程人員手動排程快速，因此，該方法求解零工式生產排程能有效地輔助決策者進行決策。

Stainless steel is an important material in the manufacturing industry, known as the mother of industry. The machines are usually occupied a lot of space due to the processing of large products, resulting in multiple products being produced on the same line, and different processes have to be processed on different machines. The circumstance could cause a lot of extra production restrictions and set-up time and greatly increase the difficulty of production scheduling.
In this study, a hybrid genetic algorithm combining genetic algorithm, modified Nawaz-Enscore-Ham (NEH) algorithm, and local search method, is used to construct the scheduling model of this study. In order to conduct the experiment, it is necessary to clarify the constraints between production lines, the set-up time,and the product processing time, and then use the order data and production route as the basic data. Firstly, this study uses the earliest due date (EDD) of the dispatching rule with the present scheduling method to generate the initial solution. Second, the extensive search property of the genetic algorithm is used to enhance the depth of the search, together with the modified NEH algorithm and the local search method.Therefore, a multi-objective performance is selected as the objective function. Taking into account the semi-finished products cost, fast delivery and short delivery time, the minimum total completion time, minimum total tardiness time, and minimum total WIP queue time are considered as the performance objectives for scheduling to find a feasible solution that is better than the current scheduling method.
The results show that the hybrid genetic algorithm is identical to the traditional genetic algorithm in the total completion time. However, significantly superior to the traditional genetic algorithm in terms of the minimum total tardiness time and minimum total WIP queue time. The program execution time is faster than the current scheduler’s manual scheduling. Therefore, the proposed method for solving job shop production scheduling can effectively assist decisionmakers in decision-making.

摘要 i
ABSTRACT ii
致謝詞 iii
目錄 iv
表目錄 v
圖目錄 vi
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 2
1.3 研究流程與架構 3
第二章 文獻探討 6
2.1 零工式生產 6
2.2 派工法則 10
2.3 整備時間 11
2.4 多目標績效 14
2.5 基因演算法 18
2.6 小結 22
第三章 研究方法與架構 25
3.1 不銹鋼介紹 25
3.2 不銹鋼廠製程與問題定義 28
3.3 數學符號定義及模式建構 30
3.4 生產工時計算 33
3.5 演算法之架構 35
第四章 實驗結果分析 48
4.1 演算法效能評估 48
4.2 基因演算法參數設定 53
4.3 混合型基因演算法實驗結果 57
4.4 敏感度分析實驗 67
4.5 演算法程式執行時間 76
4.6 小結 77
第五章 結論與未來方向 78
5.1 研究結論 78
5.2 未來研究建議 79
參考文獻 80

[1] 世界鋼鐵協會。取自 https://worldsteel.org/
[2] 林志諭（2009）。基因演算法求解多目標流程型工廠排程之研究（未出版之碩士論文）。國立勤益科技大學，台中市。
[3] 翁家泓（2020）。基因演算法處理多產線之流線型排程問題之運用（未出版之碩士論文）。元智大學，桃園市。
[4] 陳建安（2017）。應用基因演算法改進零工式生產排程研究-以半導體封裝模具廠為例（未出版之碩士論文）。國立成功大學，台南市。
[5] 陳建良（1995）。排程概述。機械工業雜誌，153，122–137。
[6] 謝博仁（2015）。考慮製程時間限制的迴流型零工式生產排程（未出版之碩士論文）。國立高雄第一科技大學，高雄市。
[7] 鍾世軒（2018）。兩階段加工單位不一致流程式生產排程（未出版之碩士論文）。國立雲林科技大學，雲林縣。
[8] Abreu, L. R., Cunha, J. O., Prata, B. A., & Framinan, J. M. (2020). A genetic algorithm for scheduling open shops with sequence-dependent setup times. Computers & Operations Research, 113, 104793.
[9] Allahverdi, A., Gupta, J. N., & Aldowaisan, T. (1999). A review of scheduling research involving setup considerations. Omega, 27(2), 219–239.
[10] Chang, P. C., Hsieh, J. C., & Lin, S. G. (2002). The development of gradual-priority weighting approach for the multi-objective flowshop scheduling problem. International Journal of Production Economics, 79(3), 171–183.
[11] Cheng, R., Gen, M., & Tsujimura, Y. (1996). A tutorial survey of job-shop scheduling problems using genetic algorithms—I. Representation. Computers & Industrial Engineering, 30(4), 983–997.
[12] Cochran, J. K., Horng, S. M., & Fowler, J. W. (2003). A multi-population genetic algorithm to solve multi-objective scheduling problems for parallel machines. Computers & Operations Research, 30(7), 1087–1102.
[13] Ehtesham Rasi, R. (2021). Optimization of the multi-objective flexible job shop scheduling model by applying NSGAII and NRGA algorithms. Journal of Industrial Engineering and Management Studies, 8(1), 45–71.
[14] Fu, M., Zhonghua, H., Zhijun, G., Xiaoting, D., & Xutian, T. (2017, July). Whale optimization algorithm for flexible flow shop scheduling with setup times. In proceeding of the 2017 9th International Conference on Modelling, Identification and Control (ICMIC). Kunming, China.
[15] Gao, J., Gen, M., Sun, L., & Zhao, X. (2007). A hybrid of genetic algorithm and bottleneck shifting for multiobjective flexible job shop scheduling problems. Computers & Industrial Engineering, 53(1), 149–162.
[16] Garey, M. R., Johnson, D. S., & Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research, 1(2), 117 129.
[17] Graham, R. L. (1966). Bounds for certain multiprocessing anomalies. Bell System Technical Journal, 45(9), 1563–1581.
[18] Haupt, R. (1989). A survey of priority rule-based scheduling. Operations ResearchSpektrum, 11(1), 3–16.
[19] Holland, J. H. (1975). Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control, and artificial intelligence. Michigan, USA: U Michigan Press.
[20] Holthaus, O., & Rajendran, C. (1997). Efficient dispatching rules for scheduling in a job shop. International Journal of Production Economics, 48(1), 87–105.
[21] Huang, X., & Yang, L. (2019). A hybrid genetic algorithm for multi-objective flexible job shop scheduling problem considering transportation time. International Journal of Intelligent Computing and Cybernetics, 12(2), 154–174.
[22] Kuczapski, A. M., Micea, M. V., Maniu, L. A., & Cretu, V. I. (2010). Efficient generation of near optimal initial populations to enhance genetic algorithms for job-shop scheduling. Information Technology and Control, 39(1), 32–37.
[23] Lee, K. M., Yamakawa, T., & Lee, K. M. (1998, April). A genetic algorithm for general machine scheduling problems. In proceeding of the 1998 Second International Conference. Knowledge-Based Intelligent Electronic Systems. Proceedings KES'98 (Cat. No.98EX111). Adelaide, Australia.
[24] Li, Y., Zhou, G., & Xiao, Z. (2015, May). Job shop scheduling with flexible routings based on analytical target cascading. In proceeding of the 2015 International Conference on Control, Automation and Robotics. Singapore.
[25] Liang, X., Liu, Y., Gu, X., Huang, M., & Guo, F. (2022). Adaptive Genetic Algorithm Based on Individual Similarity to Solve Multi-Objective Flexible Job Shop Scheduling Problem.IEEE Access, 10, 45748–45758.
[26] Liu, Y., Zhang, L., & Sun, T. (2021, May). An Improved Nondominated Sorting Genetic Algorithm-II for Multi-objective Flexible Job-shop Scheduling Problem Considering Worker Assignments. In proceeding of the 2021 International Conference on Communications, Information System and Computer Engineering (CISCE). Beijing, China.
[27] Mokotoff, E. (2009). Multi-objective simulated annealing for permutation flow shop problems. In Computational intelligence in flow shop and job shop scheduling (pp. 101–150): Springer.
[28] Nawaz, M., Enscore Jr, E. E., & Ham, I. (1983). A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega, 11(1), 91–95.
[29] Ozsoydan, F. B., & Sağir, M. (2021). Iterated greedy algorithms enhanced by hyperheuristic based learning for hybrid flexible flowshop scheduling problem with sequence dependent setup times: a case study at a manufacturing plant. Computers & Operations Research, 125, 105044.
[30] Pezzella, F., Morganti, G., & Ciaschetti, G. (2008). A genetic algorithm for the flexible job-shop scheduling problem. Computers & Operations Research, 35(10), 3202–3212.
[31] Qiao, Y., Wu, N., He, Y., Li, Z., & Chen, T. (2022). Adaptive genetic algorithm for twostage hybrid flow-shop scheduling with sequence-independent setup time and nointerruption requirement. Expert Systems with Applications, 208, 118068.
[32] Ren, H., Xu, H., & Sun, S. (2016, May). Immune genetic algorithm for multi-objective flexible job-shop scheduling problem. In proceeding of the 2016 Chinese Control and Decision Conference (CCDC). Yinchuan, China.
[33] Ribas, I., Companys, R., & Tort-Martorell, X. (2021). An iterated greedy algorithm for the parallel blocking flow shop scheduling problem and sequence-dependent setup times. Expert Systems with Applications, 184, 115535.
[34] Tay, J. C., & Ho, N. B. (2008). Evolving dispatching rules using genetic programming for solving multi-objective flexible job-shop problems. Computers & Industrial Engineering, 54(3), 453–473.
[35] 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.
[36] Vlašić, I., Ðurasević, M., & Jakobović, D. (2019). Improving genetic algorithm performance by population initialisation with dispatching rules. Computers & Industrial Engineering, 137, 106030.
[37] Wang, Y., & Zhu, Q. (2021). A hybrid genetic algorithm for flexible job shop scheduling problem with sequence-dependent setup times and job lag times. IEEE Access, 9, 104864–104873.
[38] Yu, C., Semeraro, Q., & Matta, A. (2018). A genetic algorithm for the hybrid flow shop scheduling with unrelated machines and machine eligibility. Computers & Operations Research, 100, 211–229.
[39] Zhang, G., Hu, Y., Sun, J., & Zhang, W. (2020). An improved genetic algorithm for the flexible job shop scheduling problem with multiple time constraints. Swarm and Evolutionary Computation, 54, 100664.
[40] Zhang, G., Zhang, L., Song, X., Wang, Y., & Zhou, C. (2019). A variable neighborhood search based genetic algorithm for flexible job shop scheduling problem. Cluster Computing, 22(5), 11561–11572.
[41] Zhang, J., Ding, G., Zou, Y., Qin, S., & Fu, J. (2019). Review of job shop scheduling research and its new perspectives under Industry 4.0. Journal of Intelligent Manufacturing, 30(4), 1809–1830.
[42] Zhou, H., Feng, Y., & Han, L. (2001). The hybrid heuristic genetic algorithm for job shop scheduling. Computers & Industrial Engineering, 40(3), 191–200.
[43] Zhu, Z., & Zhou, X. (2020). An efficient evolutionary grey wolf optimizer for multiobjective flexible job shop scheduling problem with hierarchical job precedence constraints. Computers & Industrial Engineering, 140, 106