製造業及服務業中有許多大型排程問題具有不同排程目標，但其計算時間常隨著問題的大小呈指數增長，尋求最小完工時間之無等待流線式工廠排程問題已被證明是一個NP-Hard問題。過去研究發現採用融合田口直交表實驗方法的基因演算法可以為無等待流線式工廠排程問題找到很好的最小完工時間之排程，Tseng & Lin (以下簡稱 TL 演算法) 再加以改良提出新的區域搜尋方法，更新了公開基準案例中71.66%的已知最佳解。我們以TL 演算法作為本研究基礎，改良基因演算法架構與提出新的區域搜尋方法：插入搜尋結合兩點切開修復(Insertion-Search with Two Point Cut-and-Repair)，可擴大搜尋範圍，實驗結果改善了TL 演算法83.33%基準案例的實驗結果。我們並測試不同維度的田口直交表對於基因演算法中搜尋最佳可行解的影響，由實驗結果，建議大型案例使用較大直交表。

Large-scale scheduling problems in the manufacturing and service industries have many different scheduling goals. The computing time of these problems increases exponentially with number of jobs. The no-wait flow shop scheduling problem with the makespan criterion was proved NP-hard. From past studies, the genetic algorithm using the Taguchi orthogonal array method has produced very good scheduling for no-wait flow shop scheduling problems with minimum makespan criterion. Tseng & Lin further proposed a new local search method (called TL algorithm below) and improved 71.66% of the best known in the public benchmark cases. Based on the TL algorithm, we improve its framework and propose a new local search method, called Insertion-Search with Two Point Cut-and-Repair. Our algorithm could expand the local search range, and for the benchmark cases, our best solutions improve 83.33% of the results obtained by the TL algorithm. We use the same benchmark cases to test and analyze the impact of different Taguchi orthogonal array tables on searching for the best feasible solution. From our experimental results, we suggest use large Taguchi orthogonal array tables for large cases.

目錄
第壹章、緒論 1
1.1 研究背景 1
1.2 研究動機 2
1.3 問題描述 3
1.4 研究目的 5
1.5 研究架構 6
第貳章、文獻探討 7
2.1 工廠排程問題類型 7
2.2 解決排程問題方法 8
2.2.1 派工法則 9
2.2.2 績效指標 9
2.2.3 解決排程問題之啟發式演算法 10
2.2.4 解決排程問題之人工智慧演算法 11
2.3 田口基因演算法 18
2.4 區域搜尋法 20
第參章、研究方法 22
3.1 NWFSSP問題說明 22
3.2 基因演算法 26
3.3 TL演算法 28
3.3.1 編碼與適應函數的定義 29
3.3.2 交配方法 29
3.3.2.1 田口直交表 30
3.3.2.2 應用田口直交表之交配 30
3.3.3 區域搜尋 32
3.3.3.1 插入搜尋 33
3.3.3.2 切開修復 35
3.3.3.3 插入搜尋結合切開修復演算流程 36
3.3.4 突變方法 36
3.3.5 TL演算法與基因演算法之比較 37
3.4 本研究之基因演算法 38
3.4.1 本研究之插入搜尋 39
3.4.2 兩點切開修復 41
3.4.3 插入搜尋結合兩點切開修復演算流程 42
3.4.4 本研究與基因演算法之比較 43
第肆章、實驗結果 44
4.1 實驗環境與基準案例介紹 44
4.2 混合式基因演算法實作結果 45
4.2.1 直交表L4(23)比較 45
4.2.2 直交表L8(27)比較 47
4.2.3 TL演算法與本研究演算法之比較 48
4.3 小工作數實驗比較本研究演算法結果與最佳解 49
4.4 田口基因演算法可行解的影響分析 51
第伍章、結論與未來展望 54
5.1 結論 54
5.2 研究貢獻 55
5.3未來工作與展望 55
參考文獻 56

表目錄
======================================================
表 1、為具代表性人工智慧方法彙整表 16
表 2、避免掉入局部最佳解之具代表性區域搜尋彙整表 21
表 3、工作處理時間範例 24
表 4、TL演算法與基因演算法之特性比較表 37
表 5、本研究與基因演算法之特性比較表 43
表 6、直交表L4(23)實驗之參數設定 45
表 7、比較L4(23)與L8(27)抽測24個案例實作結果 46
表 8、比較L8(27)抽測24個案例實作結果 47
表 9、TL演算法與本研究演算法之特性比較表 49
表 10、小工作數最佳解之比較實驗結果與平均完工時間 50
表 11、小工作數實驗比較最佳解與本研究結果 51
表 12、田口基因演算法可行解分析表 52

圖目錄
======================================================
圖 1、FSSP展示範例 3
圖 2、NWFSSP展示範例 4
圖 3、研究架構 6
圖 4、等待時間演算流程 25
圖 5、No-Wait排程範例 25
圖 6、基因演算法演算流程 27
圖 7、L4(23) orthogonal array實作範例 32
圖 8、突變產生子代圖示 37
圖 9、本研究插入搜尋演算範例 40
圖 10、本研究之兩點切開修復演算範例說明 42
圖 11、案例ta001迭代比較圖 49
圖 12、田口基因演算法可行解曲線圖 52

參考文獻
[1] Allahverdi, A. (2016). "A survey of scheduling problems with no-wait in process, " European Journal of Operational Research, 255(3), 665-686.
[2] Allahverdi, A., Aydilek, H., & Aydilek, A. (2018). "No-wait flowshop scheduling problem with two criteria; total tardiness and makespan, "European Journal of Operational Research, 269(2), 590-601.
[3] Carlier, J. (1978). "Ordonnancements a contraintes disjonctives, "RAIRO-Operations Research, 12(4), 333-350.
[4] Gao, F., Liu, M., Wang, J. J., & Lu, Y. Y. (2018). "No-wait two-machine permutation flow shop scheduling problem with learning effect, common due date and controllable job processing times, " International Journal of Production Research, 56(6), 2361-2369.
[5] Grabowski, J., & Pempera, J. (2005). "Some local search algorithms for no-wait flow-shop problem with makespan criterion, " Computers & Operations Research, 32(8), 2197-2212.
[6] Grabowski, J., & Wodecki, M. (2004). "A very fast tabu search algorithm for the permutation flow shop problem with makespan criterion, " Computers & Operations Research, 31(11), 1891-1909.
[7] Heller, J. (1960). "Some numerical experiments for an M× J flow shop and its decision-theoretical aspects,"Operations Research, 8(2), 178-184.
[8] Ho, Shinn-Ying., &Chen, Jian-Hung. (2000)." A GA-based systematic reasoning approach for solving traveling salesman problems using an orthogonal array crossover, " IEEE Proceedings Fourth International Conference/Exhibition on High Performance Computing in the Asia-Pacific Region, 659-663.
[9] Hall, N. G., & Sriskandarajah, C. (1996). "A survey of machine scheduling problems with blocking and no-wait in process, " Operations research, 44(3), 510-525.
[10] Liu, B., Wang, L., & Jin, Y. H. (2007). " An effective hybrid particle swarm optimization for no-wait flow shop scheduling, "The International Journal of Advanced Manufacturing Technology, 31(9-10), 1001-1011.
[11] Liu, L. L., Hu, R. S., Hu, X. P., Zhao, G. P., & Wang, S. (2015). "A hybrid PSO-GA algorithm for job shop scheduling in machine tool production, "International Journal of Production Research, 53(19), 5755-5781.
[12] Lu, Z., Cui, W., & Han, X. (2015). " Integrated production and preventive maintenance scheduling for a single machine with failure uncertainty, " Computers & Industrial Engineering, 80, 236-244.
[13] Leung, Y. W., & Wang, Y. (2001). " An orthogonal genetic algorithm with quantization for global numerical optimization, " IEEE Transactions on Evolutionary computation, 5(1), 41-53.
[14] Mir, M. S. S., & Rezaeian, J. (2016). " A robust hybrid approach based on particle swarm optimization and genetic algorithm to minimize the total machine load on unrelated parallel machines," Applied Soft Computing, 41, 488-504.
[15] 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.
[16] Pan, Q. K., Wang, L., & Zhao, B. H. (2008). "An improved iterated greedy algorithm for the no-wait flow shop scheduling problem with makespan criterion, "The International Journal of Advanced Manufacturing Technology, 38(7-8), 778-786.
[17] Pang, K. W. (2013). "A genetic algorithm based heuristic for two machine no-wait flowshop scheduling problems with class setup times that minimizes maximum lateness, "International Journal of Production Economics, 141(1), 127-136.
[18] 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.
[19] Rahman, H. F., Sarker, R., & Essam, D. (2015). " A real-time order acceptance and scheduling approach for permutation flow shop problems, "European Journal of Operational Research, 247(2), 488-503.
[20] Ruiz, R., Maroto, C., & Alcaraz, J. (2006). " Two new robust genetic algorithms for the flowshop scheduling problem, " Omega, 34(5), 461-476.
[21] Reeves, C. R. (1994). "Genetic algorithms and neighbourhood search, " In AISB Workshop on Evolutionary Computing, 115-130.
[22] Reeves, C. R. (1995). "A genetic algorithm for flowshop sequencing, " Computers & operations research, 22(1), 5-13.
[23] Röck, H. (1984). "The three-machine no-wait flow shop is NP-complete, " Journal of the ACM , 31(2), 336-345.
[24] Taillard, E. (1993). " Benchmarks for basic scheduling problems, " European Journal of Operational Research, 64(2), 278-285.
[25] Tseng, L. Y., & Lin, Y. T. (2010). "A hybrid genetic algorithm for no-wait flowshop scheduling problem, " International Journal of Production Economics, 128(1), 144-152.
[26] Tseng, L. Y., & Lin, Y. T.(2009). "A Hybrid Genetic Algorithm for Minimizing Total Flowtime in Flowshop Scheduling Problems, " 25th Workshop on Combinatorial Mathematics and Computation Theory,331-338
[27] Tsai, Jinn-Tsong ., Liu, Tung-Kuan & CHOU, Jyh-Horng. (2004). "Hybrid Taguchi-genetic algorithm for global numerical optimization, " IEEE Transactions on evolutionary computation, 8.4: 365-377.
[28] Tseng, C. C., & Liu, B. S. (2011). "Hybrid Taguchi-genetic algorithm for selecting and scheduling a balanced project portfolio, " Journal of Science and Engineering Technology, 7(1), 11-18.
[29] Umar, U. A., Ariffin, M. K. A., Ismail, N., & Tang, S. H. (2015). "Hybrid multiobjective genetic algorithms for integrated dynamic scheduling and routing of jobs and automated-guided vehicle (AGV) in flexible manufacturing systems (FMS) environment, " The International Journal of Advanced Manufacturing Technology, 81(9-12), 2123-2141.
[30] Vallada, E., Ruiz, R., & Framinan, J. M. (2015). " New hard benchmark for flowshop scheduling problems minimising makespan," European Journal of Operational Research, 240(3), 666-677.
[31] Wang, S., & Liu, M. (2013). "A genetic algorithm for two-stage no-wait hybrid flow shop scheduling problem, " Computers & Operations Research, 40(4), 1064-1075.
[32] 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.
[33] Ying, K. C., & Lin, S. W. (2018). "Minimizing makespan for no-wait flowshop scheduling problems with setup times, " Computers & Industrial Engineering, 121, 73-81.
[34] 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.
[35] 王柏翔(2008)."應用混合型田口遺傳演算法於引伸模具補強肋之尺寸最佳化, "國立高雄第一科技大學機械與自動化工程學系碩士論文.
[36] 王裕仁，賴俊宇，林采璇，蔡博安，邱松山(2011)，"應用田口基因演算法於工程查核指派問題之研究, "行政院國家科學委員會專題研究計畫.
[37] 李東森(2006). "跳躍式 no-wait 生產線工件排程方法之研究, "國立交通大學工業工程與管理學系碩士論文.
[38] 李宛柔(2007). "以基因演算法求解不可延遲批次排程問題之研究, "國立臺灣科技大學工業管理系碩士論文.
[39] 吳秉威(2005). "以遺傳演算法求解 PCB 廠生產排程問題, "南台科技大學工業管理學系碩士論文.
[40] 林則孟(2012).生產計劃與管理,台北:華泰書局.
[41] 林亞泰(2009). "以基因區域搜尋演算法解決流程型工廠排程問題, "國立中興大學資訊科學與工程學系博士論文.
[42] 林采璇(2011). "應用田口方法於基因演算法輸入參數設計-以工程品質查核標案選擇與委員指派組合為例, "國立高雄應用科技大學土木工程與防災科技學系碩士論文.
[43] 楊景勛(2005). "應用田口法與基因演算法於衝壓模具之簡化樑模型結構最佳化設計, "國立高雄應用科技大學模具工程系碩士論文.
[44] 陳宜欣，陳稼興，許芳誠(2001). "遺傳演算法於 Job Shop 排程問題上的研究, "技術學刊，第十六卷，第一期.
[45] 蔡宗翰(2007). "共用機台之跳躍式不允許等待流程式生產排程, "國立交通大學工業工程與管理學系碩士論文.
[46] 謝政勳，廖珗洲，李聯旺(2018).人工智慧:智慧型導論,新北市:全華圖書.