[[alternative]]應用於支向機分類器與彈性多工排程問題之最佳化演算法設計

博士[[abstract]]本論文提出兩種單目標混合型最佳化演算法來改善支向機分類器的分類正確率以及兩種多目標最佳化演算法來解決彈性多工排程問題。在支向機分類器的設計上，本論文提出一種可與輸入訓練資料的順序無關的動態濃縮最近鄰居點的演算法，其可以減少因冗餘或雜訊之訓練樣本在分類過程中所造成的影響。然後我們提出分別使用基因演算法與粒子群演算法來將重要代表點的建立、特徵的選取、以及支向機的核心函數之參數設定等三項同時做最佳化處理。本論文提出GA-DCNN-SVM與PSO-DCNN-SVM兩種混合型最佳化演算法，並且和其他先前已公開發表的演算法做比較，經由多種的UCI標準測試資料集的實驗顯示，本論文所提出的混合型演算法可改善支向機的分類正確率，並且表現優於現存的方法。此外，在彈性多工排程問題上，本論文首先提出一個多目標粒子群演算法以尋找問題的多目標最佳解。在此方法中，本論文提出一個有效的編碼法來將粒子的實數值拆成整數部份與小數部份，並且分別表示機器選擇與任務順序，再提出一個循序指派的解碼機制來得到合理可行的排程候選解。因此標準實數型的粒子群演算法整合突變運算的演算法架構即可用來求解彈性多工排程問題。最後，我們提出一個新的多目標蒙地卡羅樹狀搜尋演算法，本論文提出一個循序的機器與任務的指派混合編碼方式來將原來演繹式架構的問題轉換成樹狀搜尋架構的問題，並且採用NSGA-II非支配解排序的計算方式來修改原始的UCT公式，使其適用於求解多目標的問題，然後就可以應用所提出的多目標蒙地卡羅樹狀搜尋演算法來求解彈性多工排程問題。經由與其他演算法的比較，可驗證所提出兩種方法確實可以有效地解決彈性多工排程問題。[[abstract]]In this dissertation, two types of single-objective hybrid model are proposed to improve the classification rate for Support Vector Machine (SVM) classifier and two effective multi-objective optimization algorithms are developed to solve Flexible Job-shop Scheduling Problems (FJSP). In the optimization design for SVM classifier, an order-independent algorithm for the data reduction, called the Dynamic Condensed Nearest Neighbor (DCNN) rule, is proposed to adaptively construct prototypes in training dataset and to reduce the redundant or noisy instances in a classification process for the SVM classifier. Furthermore, two hybrid models based on the Genetic Algorithm (GA) and Particle Swarm Optimization (PSO) algorithm are adopted to simultaneously optimize the prototype construction, feature selection, and the SVM kernel parameters setting. Several UCI benchmark datasets are considered to compare the proposed GA-DCNN-SVM and PSO-DCNN-SVM approaches with the other previously published methods. The experimental results show that the developed hybrid models outperform the existing method and improve the classification accuracy for the support vector machine. In the optimization design for FJSP, an evolutionary Multi-Objective Particle Swarm Optimization (MOPSO) approach is adopted and successfully applied to find the optimal Pareto solutions for FJSP. An effective encoding method is proposed to divide the continuous real value into both integer and decimal numbers, which indicates the machine selection and operation order, respectively. By using the sequential assignment decoding mechanism, a feasible schedule is always obtained and the standard continuous PSO algorithm incorporated with the mutation operator can be adopted. Finally, a Multi-Objective Mote-Carlo Tree Search (MOMCTS) algorithm is proposed to solve the FJSP. The Sequential Operation-Machine Assignment (SOMA) scheme for encoding representation is first introduced to always produce feasible solutions, and then the evolution-based FJSP mapping to a general tree search structure via SOMA is successively completed. The modification of formal UCT (Upper Confidence Bound Apply to Tree) algorithm by using the non-dominated sort strategy makes it suitable for the characters of multi-objective problems, and the Pareto-optimal solutions for FJSP can be obtained. Compared to some developed algorithms, the experimental results illustrate the effectiveness of the both proposed methods for FJSP.[[tableofcontents]]Abstract (in Chinese) i Abstract (in English) ii Contents iii List of Figures vi List of Tables xii Chapter 1 Introduction 1 1.1 Motivation 1 1.2 Review of Research Works 2 1.2.1 Support Vector Machine (SVM) Classifier 2 1.2.2 Flexible Job-shop Scheduling Problem (FJSP) 4 1.3 Summary and Outline of This Dissertation 5 1.3.1 GA-based Single-Objective Hybrid Model for SVM 6 1.3.2 PSO-based Single-Objective Hybrid Model for SVM 6 1.3.3 Multi-Objective PSO Algorithm for FJSP 7 1.3.4 Multi-Objective MCTS Algorithm for FJSP 7 Chapter 2 GA-based Single-Objective Hybrid Model for SVM 8 2.1 Basic SVM Classifier 9 2.2 Condensed Nearest Neighbor (CNN) Algorithm 11 2.3 Genetic Algorithm 12 2.4 Methods 14 2.4.1 Prototype Voting Scheme (PVS) 14 2.4.2 Dynamic CNN (DCNN) Algorithm 16 2.4.3 The Proposed GA-DCNN-SVM Hybrid Model 20 2.5 Experimental Results and Concluding Remarks 26 Chapter 3 PSO-based Single-Objective Hybrid Model for SVM 30 3.1 Basic Single-Objective Particle Swarm Optimization (PSO) 31 3.2 Binary Particle Swarm Optimization (BPSO) 32 3.3 The Proposed Hybrid Model for SVM 33 3.3.1 Particle Representation 34 3.3.2 Fitness Definition 34 3.3.3 Disturbance Strategy for PSO Operation 35 3.3.4 The Proposed PSO-DCNN-SVM Hybrid Model 36 3.4 Experimental Results and Concluding Remarks 39 Chapter 4 Multi-Objective PSO Algorithm for FJSP 44 4.1 Formulation of the FJSP 44 4.2 Multi-Objective Particle Swarm Optimization (MOPSO) 46 4.3 Particle Representation and SDAI Decoding Method 50 4.3.1 Particle Representation 50 4.3.2 Sorting Decimal Assignment Integer (SDAI) Decoding Method 52 4.4 The Proposed MOPSO Algorithm for FJSP 57 4.5 Experimental Results and Concluding Remarks 63 4.5.1 Problem 8x8 63 4.5.2 Problem 10x10 64 4.5.3 Problem 15x10 66 4.5.4 Problem 4x5 with Release Date 66 4.5.5 Problem 10x7 with Release Date 67 4.5.6 Problem 15x10 with Release Date 69 4.5.7 Concluding Remarks 70 Chapter 5 Multi-Objective MCTS Algorithm for FJSP 71 5.1 MCTS and UCT 72 5.1.1 Structure of Monte-Carlo Tree Search (MCTS) 72 5.1.2 The UCT Algorithm 73 5.2 Representation and SOMA Method 75 5.3 Problem Transformation 80 5.4 Modification of UCT with Non-dominated Sorting Strategy 82 5.5 The Path Random Search (PRS) Algorithm 85 5.6 The Proposed MOMCTS Algorithm for FJSP 88 5.7 Experimental Results and Concluding Remarks 91 5.7.1 Problem 8x8 91 5.7.2 Problem 10x10 93 5.7.3 Problem 15x10 94 5.7.4 Problem 4x5 with Release Date 95 5.7.5 Problem 10x7 with Release Date 96 5.7.6 Problem 15x10 with Release Date 97 5.7.7 Concluding Remarks 98 Chapter 6 Conclusions and Future Work 99 Appendix A Some Results of Gantt Charts for Solving FJSP 101 A.1 Problem 8×8 and Some Results of Gantt Charts 103 A.2 Problem 10×10 and Some Results of Gantt Charts 110 A.3 Problem 15×10 and Some Results of Gantt Charts 118 A.4 Problem 4×5 with Release Date and Some Results of Gantt Charts 123 A.5 Problem 10×7 with Release Date and Some Results of Gantt Charts 127 A.6 Problem 15×10 with Release Date and Some Results of Gantt Charts 134 Appendix B Construction of Tree Search Topology 139 References 144 List of Figures Figure 2.1 The flowchart of genetic algorithm. 13 Figure 2.2 Pseudo code of the PVS algorithm. 16 Figure 2.3(a) The result of original dataset. 19 Figure 2.3(b) The result of . 19 Figure 2.3(c) The result of . 19 Figure 2.3(d) The result of . 19 Figure 2.3(e) The result of . 19 Figure 2.3(f) The result of . 19 Figure 2.4 The flowchart of our proposed hybrid GA-DCNN-SVM model. 23 Figure 3.1 The flowchart of our proposed hybrid PSO-DCNN-SVM model. 38 Figure 4.1 Case A in the external repository. 47 Figure 4.2 Case B in the external repository. 47 Figure 4.3 Case C in the external repository. 47 Figure 4.4 Case D in the external repository. 47 Figure 4.5 Structure of proposed particle representation of each dimension. 51 Figure 4.6 One possible encoding representation in Table 4.1. 52 Figure 4.7(a) The SDAI scheme in Step 1. 53 Figure 4.7(b) The Gantt chart in Step 1. 53 Figure 4.8(a) The SDAI scheme in Step 2. 53 Figure 4.8(b) The Gantt chart in Step 2. 53 Figure 4.9(a) The SDAI scheme in Step 3. 54 Figure 4.9(b) The Gantt chart in Step 3. 54 Figure 4.10(a) The SDAI scheme in Step 4. 54 Figure 4.10(b) The Gantt chart in Step 4. 55 Figure 4.11(a) The SDAI scheme in Step 5. 55 Figure 4.11(b) The Gantt chart in Step 5. 55 Figure 4.12(a) The SDAI scheme in Step 6. 56 Figure 4.12(b) The Gantt chart in Step 6. 56 Figure 4.13(a) The SDAI scheme in Step 7. 56 Figure 4.13(b) The Gantt chart in Step 7. 57 Figure 4.14 The system flowchart of the proposed MOPSO algorithm 62 Figure 5.1 The scheme of Monte-Carlo tree search. 73 Figure 5.2 The Gantt chart in Step 7. 79 Figure 5.3 The system flowchart of the proposed PRS algorithm. 87 Figure 5.4 The system architecture of the proposed MOMCTS algorithm. 90 Figure A1 Optimization solution 1*(a) of problem 8×8 (F1=75, F2=12,F3=15). █ Obtained by MOPSO □ Obtained by MOMCTS 104 Figure A2 Optimization solution 1*(b) of problem 8×8 (F1=75, F2=12,F3=15). █ Obtained by MOPSO □ Obtained by MOMCTS 104 Figure A3 Optimization solution 1*(c) of problem 8×8 (F1=75, F2=12,F3=15). □ Obtained by MOPSO █ Obtained by MOMCTS 105 Figure A4 Optimization solution 1*(d) of problem 8×8 (F1=75, F2=12,F3=15). □ Obtained by MOPSO █ Obtained by MOMCTS 105 Figure A5 Optimization solution 2*(a) of problem 8×8 (F1=73, F2=13,F3=16). █ Obtained by MOPSO □ Obtained by MOMCTS 106 Figure A6 Optimization solution 2*(b) of problem 8×8 (F1=73, F2=13,F3=16). █ Obtained by MOPSO █ Obtained by MOMCTS 106 Figure A7 Optimization solution 2*(c) of problem 8×8 (F1=73, F2=13,F3=16). □ Obtained by MOPSO █ Obtained by MOMCTS 107 Figure A8 Optimization solution 2*(d) of problem 8×8 (F1=73, F2=13,F3=16). □ Obtained by MOPSO █ Obtained by MOMCTS 107 Figure A9 Optimization solution 3*(a) of problem 8×8 (F1=77, F2=12,F3=14). █ Obtained by MOPSO █ Obtained by MOMCTS 108 Figure A10 Optimization solution 3*(b) of problem 8×8 (F1=77, F2=12,F3=14). □ Obtained by MOPSO █ Obtained by MOMCTS 108 Figure A11 Optimization solution 4*(a) of problem 8×8 (F1=77, F2=11,F3=16). █ Obtained by MOPSO █ Obtained by MOMCTS 109 Figure A12 Optimization solution 4*(b) of problem 8×8 (F1=77, F2=11,F3=16). □ Obtained by MOPSO █ Obtained by MOMCTS 109 Figure A13 Optimization solution 1*(a) of problem 10×10 (F1=41, F2=7,F3=8). █ Obtained by MOPSO □ Obtained by MOMCTS 111 Figure A14 Optimization solution 1*(b) of problem 10×10 (F1=41, F2=7,F3=8). █ Obtained by MOPSO □ Obtained by MOMCTS 111 Figure A15 Optimization solution 1*(c) of problem 10×10 (F1=41, F2=7,F3=8). □ Obtained by MOPSO █ Obtained by MOMCTS 112 Figure A16 Optimization solution 1*(d) of problem 10×10 (F1=41, F2=7,F3=8). █ Obtained by MOPSO █ Obtained by MOMCTS 112 Figure A17 Optimization solution 2*(a) of problem 10×10 (F1=42, F2=5,F3=8). █ Obtained by MOPSO □ Obtained by MOMCTS 113 Figure A18 Optimization solution 2*(b) of problem 10×10 (F1=42, F2=5,F3=8). █ Obtained by MOPSO █ Obtained by MOMCTS 113 Figure A19 Optimization solution 2*(c) of problem 10×10 (F1=42, F2=5,F3=8). □ Obtained by MOPSO █ Obtained by MOMCTS 114 Figure A20 Optimization solution 3*(a) of problem 10×10 (F1=43, F2=5,F3=7). █ Obtained by MOPSO □ Obtained by MOMCTS 114 Figure A21 Optimization solution 3*(b) of problem 10×10 (F1=43, F2=5,F3=7). □ Obtained by MOPSO █ Obtained by MOMCTS 115 Figure A22 Optimization solution 3*(c) of problem 10×10 (F1=43, F2=5,F3=7). □ Obtained by MOPSO █ Obtained by MOMCTS 115 Figure A23 Optimization solution 4*(a) of problem 10×10 (F1=42, F2=6,F3=7). █ Obtained by MOPSO □ Obtained by MOMCTS 116 Figure A24 Optimization solution 4*(b) of problem 10×10 (F1=42, F2=6,F3=7). █ Obtained by MOPSO □ Obtained by MOMCTS 116 Figure A25 Optimization solution 4*(c) of problem 10×10 (F1=42, F2=6,F3=7). □ Obtained by MOPSO █ Obtained by MOMCTS 117 Figure A26 Optimization solution 4*(d) of problem 10×10 (F1=42, F2=6,F3=7). █ Obtained by MOPSO █ Obtained by MOMCTS 117 Figure A27 Optimization solution 1*(a) of problem 15×10 (F1=91, F2=11,F3=11). █ Obtained by MOPSO □ Obtained by MOMCTS 119 Figure A28 Optimization solution 1*(b) of problem 15×10 (F1=91, F2=11,F3=11). █ Obtained by MOPSO █ Obtained by MOMCTS 119 Figure A29 Optimization solution 1*(c) of problem 15×10 (F1=91, F2=11,F3=11). □ Obtained by MOPSO █ Obtained by MOMCTS 120 Figure A30 Optimization solution 1*(d) of problem 15×10(F1=91, F2=11,F3=11). □ Obtained by MOPSO █ Obtained by MOMCTS 120 Figure A31 Optimization solution 2*(a) of problem 15×10(F1=93, F2=10,F3=11). █ Obtained by MOPSO □ Obtained by MOMCTS 121 Figure A32 Optimization solution 2*(b) of problem 15×10(F1=93, F2=10,F3=11). █ Obtained by MOPSO □ Obtained by MOMCTS 121 Figure A33 Optimization solution 2*(c) of problem 15×10(F1=93, F2=10,F3=11). □ Obtained by MOPSO █ Obtained by MOMCTS 122 Figure A34 Optimization solution 2*(d) of problem 15×10(F1=93, F2=10,F3=11). █ Obtained by MOPSO █ Obtained by MOMCTS 122 Figure A35 Optimization solution 1*(a) of problem 4×5(F1=31, F2=9,F3=16). █ Obtained by MOPSO □ Obtained by MOMCTS 124 Figure A36 Optimization solution 1*(b) of problem 4×5(F1=31, F2=9,F3=16). █ Obtained by MOPSO █ Obtained by MOMCTS 124 Figure A37 Optimization solution 1*(c) of problem 4×5(F1=31, F2=9,F3=16). □ Obtained by MOPSO █ Obtained by MOMCTS 124 Figure A38 Optimization solution 2*(a) of problem 4×5(F1=32, F2=8,F3=16). █ Obtained by MOPSO █ Obtained by MOMCTS 125 Figure A39 Optimization solution 2*(b) of problem 4×5(F1=32, F2=8,F3=16). █ Obtained by MOPSO █ Obtained by MOMCTS 125 Figure A40 Optimization solution 2*(c) of problem 4×5(F1=32, F2=8,F3=16). □ Obtained by MOPSO █ Obtained by MOMCTS 125 Figure A41 Optimization solution 2*(d) of problem 4×5(F1=32, F2=8, F3=16). □ Obtained by MOPSO █ Obtained by MOMCTS 126 Figure A42 Optimization solution 3*(a) of problem 4×5(F1=33, F2=7, F3=16). █ Obtained by MOPSO █ Obtained by MOMCTS 126 Figure A43 Optimization solution 3*(b) of problem 4×5(F1=33, F2=7, F3=16). □ Obtained by MOPSO █ Obtained by MOMCTS 126 Figure A44 Optimization solution 1*(a) of problem 10×7(F1=60, F2=12, F3=16). █ Obtained by MOPSO □ Obtained by MOMCTS 128 Figure A45 Optimization solution 1*(b) of problem 10×7(F1=60, F2=12, F3=16). █ Obtained by MOPSO □ Obtained by MOMCTS 128 Figure A46 Optimization solution 1*(c) of problem 10×7(F1=60, F2=12, F3=16). □ Obtained by MOPSO █ Obtained by MOMCTS 129 Figure A47 Optimization solution 1*(d) of problem 10×7(F1=60, F2=12, F3=16). □ Obtained by MOPSO █ Obtained by MOMCTS 129 Figure A48 Optimization solution 2*(a) of problem 10×7(F1=61, F2=11, F3=15). █ Obtained by MOPSO █ Obtained by MOMCTS 130 Figure A49 Optimization solution 2*(b) of problem 10×7(F1=61, F2=11, F3=15). █ Obtained by MOPSO █ Obtained by MOMCTS 130 Figure A50 Optimization solution 2*(c)of problem 10×7(F1=61, F2=11, F3=15). □ Obtained by MOPSO █ Obtained by MOMCTS 131 Figure A51 Optimization solution 2*(d) of problem 10×7(F1=61, F2=11, F3=15). □ Obtained by MOPSO █ Obtained by MOMCTS 131 Figure A52 Optimization solution 3*(a)of problem 10×7(F1=62, F2=10, F3=15). █ Obtained by MOPSO □ Obtained by MOMCTS 132 Figure A53 Optimization solution 3*(b) of problem 10×7(F1=62, F2=10, F3=15). █ Obtained by MOPSO □ Obtained by MOMCTS 132 Figure A54 Optimization solution 3*(c)of problem 10×7(F1=62, F2=10, F3=15). □ Obtained by MOPSO █ Obtained by MOMCTS 133 Figure A55 Optimization solution 3*(d) of problem 10×7(F1=62, F2=10, F3=15). □ Obtained by MOPSO █ Obtained by MOMCTS 133 Figure A56 Optimization solution 1*(a) of problem 15×10(F1=91, F2=11, F3=23). █ Obtained by MOPSO □ Obtained by MOMCTS 135 Figure A57 Optimization solution 1*(b) of problem 15×10(F1=91, F2=11, F3=23). █ Obtained by MOPSO □ Obtained by MOMCTS 135 Figure A58 Optimization solution 1*(c) of problem 15×10(F1=91, F2=11, F3=23). □ Obtained by MOPSO █ Obtained by MOMCTS 136 Figure A59 Optimization solution 1*(d) of problem 15×10(F1=91, F2=11, F3=23). □ Obtained by MOPSO █ Obtained by MOMCTS 136 Figure A60 Optimization solution 2*(a) of problem 15×10(F1=93, F2=10, F3=23). █ Obtained by MOPSO □ Obtained by MOMCTS 137 Figure A61 Optimization solution 2*(b) of problem 15×10(F1=93, F2=10, F3=23). █ Obtained by MOPSO □ Obtained by MOMCTS 137 Figure A62 Optimization solution 2*(c) of problem 15×10(F1=93, F2=10, F3=23). □ Obtained by MOPSO █ Obtained by MOMCTS 138 Figure A63 Optimization solution 2*(d) of problem 15×10(F1=93, F2=10, F3=23). □ Obtained by MOPSO █ Obtained by MOMCTS 138 Figure B1 Transformation to tree search structure via SOMA in Step 1. 139 Figure B2 Transformation to tree search structure via SOMA in Step 2. 139 Figure B3 Transformation to tree search structure via SOMA in Step 3. 140 Figure B4 Transformation to tree search structure via SOMA in Step 4. 140 Figure B5 Transformation to tree search structure via SOMA in Step 5. 141 Figure B6 Transformation to tree search structure via SOMA in Step 6. 141 Figure B7 Transformation to tree search structure via SOMA in Step 7. 142 Figure B8 Transformation to tree search structure via SOMA in Step 8. 143 List of Tables Table 2.1 The numerical values of the prototype data points with five values of merged rate ( =0.8, 0.85, 0.9, 0.95, and 1.0). 20 Table 2.2 Datasets from the UCI Machine Learning Repository. 26 Table 2.3 Experimental results for Heart disease dataset using GA-DCNN-SVM algorithm and GA-SVM method. 28 Table 2.4 Experimental results summary of GA-DCNN-SVM algorithm and GA-SVM method on six UCI datasets. 28 Table 3.1 The particle i is comprised of four parts: , , and feature mask 34 Table 3.2 Datasets from the UCI Machine Learning Repository. 39 Table 3.3 Parameters used for particle swarm optimization and genetic algorithm. 41 Table 3.4 Experimental results for Heart disease dataset using PSO – DCNN - SVM approach and GA-SVM method proposed by Huang et al. 42 Table 3.5 Experimental results summary of PSO-DCNN-SVM model and PSO-SVM, GA-SVM without DCNN method on six UCI datasets 42 Table 3.6 Experimental results summary of comparison the PSO with GA algorithm under DCNN framework on six UCI datasets. 43 Table 4.1 An example of the FJSP with 3 jobs, 2 machines, and 7 operations 52 Table 4.2 Symbols used in the MOPSO algorithm procedure statement. 58 Table 4.3 Comparison of results on problem 8×8 with 27 operations. The symbol ‘x’ indicates that the authors did not provide the Gantt chart in this article. 64 Table 4.4 Comparison of results on problem 10×10 with 30 operations. The symbol ‘x’ indicates that the authors did not provide the Gantt chart in this article. 65 Table 4.5 Comparison of results on problem 15×10 with 56 operations. The symbol ‘x’ indicates that the authors did not provide the Gantt chart in this article. 66 Table 4.6 Comparison of results on problem 4×5 with 12 operations. The symbol ‘x’ indicates that the authors did not provide the Gantt chart in this article. 67 Table 4.7 Comparison of results on problem 10×7 with 29 operations. The symbol ‘x’ indicates that the authors did not provide the Gantt chart in this article. 68 Table 4.8 Comparison of results on problem 15×10 with 56 operations. The symbol ‘x’ indicates that the authors did not provide the Gantt chart in this article. 69 Table 5.1 Initial candidate set for SOMA. Candidate: "○", Selection: "△". 75 Table 5.2 The selection set and candidate set . 76 Table 5.3 The selection set and candidate set . 76 Table 5.4 The selection set and candidate set . 77 Table 5.5 The selection set and candidate set . 77 Table 5.6 The selection set and candidate set . 78 Table 5.7 The selection set and candidate set . 78 Table 5.8 The selection set . 79 Table 5.9 An example to compute value for the initialization state. 83 Table 5.10 An example to compute value for the simulation state. 84 Table 5.11 Symbols used in the algorithm procedure statement 85 Table 5.12 Comparison of results on problem 8×8 with 27 operations. The symbol ‘x’ indicates that the authors did not provide the Gantt chart in this article. 92 Table 5.13 Comparison of results on problem 10×10 with 30 operations. The symbol ‘x’ indicates that the authors did not provide the Gantt chart in this article. 93 Table 5.14 Comparison of results on problem 15×10 with 56 operations. The symbol ‘x’ indicates that the authors did not provide the Gantt chart in this article. 94 Table 5.15 Comparison of results on problem 4×5 with 12 operations. The symbol ‘x’ indicates that the authors did not provide the Gantt chart in this article. 95 Table 5.16 Comparison of results on problem 10×7 with 29 operations. The symbol ‘x’ indicates that the authors did not provide the Gantt chart in this article. 96 Table 5.17 Comparison of results on problem 15×10 with 56 operations. The symbol ‘x’ indicates that the authors did not provide the Gantt chart in this article. 97 Table A1 Summary of Gantt chart diversity by MOPSO and MOMCTS. 102 Table A2 Problem 8 jobs × 8 machines. 103 Table A3 Problem 10 jobs × 10 machines. 110 Table A4 Problem 15 jobs × 10 machines. 118 Table A5 Problem 4 jobs × 5 machines with release date. 123 Table A6 Problem 10 jobs × 7 machines with release date. 127 Table A7 Problem 15 jobs × 10 machines with release date. 134[[note]]學號: 889350020, 學年度: 9