臺灣博碩士論文加值系統

在多目標問題當中，由於各個目標之間往往是相互衝突的，若只是一昧求其中單一目標的最佳排程，經常會造成其他目標的損失。因此如何在多個具有衝突的目標之間，找到一個平衡點，來達到整體的最佳目標，使整體的目標能夠符合決策者的要求，確實是一個相當困難的問題。在本研究的基因演算法和混合式基因演算法中，為了要達到搜尋所有可能的柏柆圖最佳解，本研究提出一個以演化世代數作為權重指定的基礎，可以根據決策者所訂定的目標優先順序以漸進式的權重指定方式，來搜尋在此優先順序下的柏拉圖最佳解(Pareto Optimal Solutions)。而此方法有別於一般在同一世代內隨機指定染色體變動權重的方式。經實驗證明，本研究所提出之漸進式優先順序法在求解時間與求解品質上均具有不錯的效果。

The objectives are competitive in solving the multi-objective scheduling problem. Supposing that we just concentrate on searching the optimal schedule with respect to one of the objectives, it leads to the loss of the other objectives. And the optimal schedule of the specified objective is always a local optimum to the multi-objective scheduling problem. As for how to achieve the global optimization is a really hard problem. Conventionally, for lowering the complexity, multi-objective problems are transformed into single objective problem through linear combination. Supposing that the searching direction is fixed and many other superior solutions cannot be visited. In this research, to recover the key drawback of the conventional approach, we propose the gradual-priority weight assignment (GPWA) approach to search the Pareto optimal solutions. GPWA searches feasible region from the first objective in the beginning and toward the other objectives gradually. For verifying the effectiveness and efficiency, GPWA compares with the variable weights approach proposed by Murata et al. As the results of comparisons, GPWA performs quite effectively and efficiently.

第一章 緒論…………………………………………………………………1
1.1 研究背景與動機………………………………………………………1
1.2 研究目的………………………………………………………………2
1.3 研究範圍與限制………………………………………………………3
1.4 研究方法………………………………………………………………3
1.5 研究架構………………………………………………………………4
第二章 文獻探討……………………………………………………………6
2.1 基因演算法應用於單目標、雙目標與多目標排程問題……………6
2.1.1 單目標方面………………………………………………………6
2.1.2 雙目標或多目標方面……………………………………………7
2.2 其他與求解雙目標或多目標排程問題之演算法……………………9
2.3 基因演算法之介紹………………………………………………… 12
2.3.1 基因演算法概述……………………………………………… 12
2.3.2 名詞解釋與限制條件………………………………………… 12
2.3.3 基因演算法與傳統演算法之差異…………………………… 14
2.3.4 基因演算法的演算流程……………………………………… 15
2.4 結語………………………………………………………………… 25
第三章 問題定義與模式建構…………………………………………… 27
3.1 問題定義…………………………………………………………… 27
3.2 模式之建構………………………………………………………… 30
3.2.1 模式之限制與假設…………………………………………… 30
3.2.2 符號說明……………………………………………………… 30
3.2.3 績效衡量準則………………………………………………… 31
第四章 研究方法………………………………………………………… 33
4.1 多目標排程問題相關名詞之說明與定義………………………… 33
4.1.1 多目標排程問題之決策方向………………………………… 33
4.1.2 柏拉圖最佳解之定義………………………………………… 35
4.1.3 變動權重……………………………………………………… 36
4.1.4 具有優先順序的漸進式權重指定法………………………… 40
4.2 基因演算法與基因局部搜尋法之演算流程……………………… 45
4.2.1 符號說明……………………………………………………… 45
4.2.2 基因演算法之演算流程……………………………………… 45
4.2.3 基因局部搜尋法法之演算流程……………………………… 50
第五章 實驗設計………………………………………………………… 56
5.1 基因演算法之參數設計…………………………………………… 56
5.1.1 雙目標問題之參數設計……………………………………… 56
5.1.2 三目標問題之參數設計……………………………………… 61
5.2 基因局部搜尋法之參數設計……………………………………… 62
5.2.1 雙目標問題之參數設計……………………………………… 62
5.2.2 三目標問題之參數設程……………………………………… 67
第六章 實驗結果與分析………………………………………………… 68
6.1 權重指定方式的差異……………………………………………… 68
6.1.1 雙目標問題…………………………………………………… 68
6.1.2 三目標問題…………………………………………………… 71
6.2 實驗結果與分析…………………………………………………… 73
6.2.1 應用基因演算法於雙目標問題之結果分析與比較………… 74
6.2.2 應用基因演算法於三目標問題之結果分析與比較………… 76
6.2.3 應用基因局部搜尋法於雙目標問題之結果分析與比較…… 77
6.2.4 應用基因局部搜尋法於雙目標問題之結果分析與比較…… 79
6.3 綜合分析…………………………………………………………… 80
第七章 結論與未來研究方向…………………………………………… 81
7.1 結論………………………………………………………………… 81
7.2 未來研究方向……………………………………………………… 82
參考文獻 …………………………………………………………………… 83
表目錄
表2.1 流程型工廠之雙目標與多目標排程文獻統整表………………… 11
表2.2 輪盤法圖例之一…………………………………………………… 20
表2.3 輪盤法圖例之二…………………………………………………… 20
表2.4 輪盤法圖例之三…………………………………………………… 20
表2.5 期望值模式圖例之一……………………………………………… 21
表2.6 期望值模式圖例之二……………………………………………… 22
表2.7 期望值模式圖例之三……………………………………………… 22
表5.1 相互凌越後所剩下的累積個數與平均個數……………………… 59
表5.2 相互凌越後所剩下的累積個數與平均個數……………………… 59
表5.3 相互凌越後所剩下的累積個數與平均個數……………………… 60
表5.4 相互凌越後所剩下的累積個數與平均個數……………………… 61
表5.5 基因演算法於雙目標之各個 組合的最佳參數組合…………… 61
表5.6 基因演算法於三目標之各個 組合的最佳參數組合…………… 62
表5.7 相互凌越後所剩下的累積個數與平均個數……………………… 63
表5.8 相互凌越後所剩下的累積個數與平均個數……………………… 65
表5.9 相互凌越後所剩下的累積個數與平均個數……………………… 66
表5.10 相互凌越後所剩下的累積個數與平均個數……………………… 66
表5.11 基因局部搜尋法於雙目標之各個組合的最佳參數組合………… 67
表5.12 基因局部搜尋法於三目標之各個 組合的最佳參數組合……… 67
表6.1 基因演算法於雙目標問題之績效比較…………………………… 75
表6.2 基因演算法於雙目標問題之平均模擬時間比較………………… 75
表6.3 基因演算法於三目標問題之績效比較…………………………… 76
表6.4 基因演算法於三目標問題之平均模擬時間比較………………… 77
表6.5 基因局部搜尋法於雙目標問題之績效比較……………………… 78
表6.6 基因局部搜尋法於雙目標問題之平均模擬時間比較…………… 78
表6.7 基因局部搜尋法於三目標問題之績效比較……………………… 79
表6.8 基因局部搜尋法於三目標問題之平均模擬時間比較…………… 80
圖目錄
圖1.1 研究方法與架構圖………………………………………………… 5
圖2.1 母體與染色體關係圖……………………………………………… 13
圖2.2 一般基因演算法之演算流程圖…………………………………… 15
圖2.3 輪盤法示意圖……………………………………………………… 21
圖2.4 二元編碼之單點交配……………………………………………… 22
圖2.5 二元編碼之雙點交配……………………………………………… 23
圖2.6 符號編碼之雙點交配……………………………………………… 23
圖2.7 二元編碼之突變方式……………………………………………… 24
圖2.8 符號編碼之移動突變方式………………………………………… 24
圖3.1 流程型工廠之工作流程…………………………………………… 28
圖3.2 零工型工廠之代表性機器之工作流程…………………………… 28
圖3.3 流程型工廠之排程類型…………………………………………… 29
圖4.1 目標函數之可行域與柏拉圖最佳解……………………………… 36
圖4.2 固定權重之搜尋方向……………………………………………… 38
圖4.3 搜尋方向與所搜尋的解之關係圖………………………………… 38
圖4.4 變動權重之搜尋方向……………………………………………… 38
圖4.5 利用目標空間角度關係之權重指定方式………………………… 39
圖4.6 固定權重之演算示意圖…………………………………………… 40
圖4.7 變動權重之演算示意圖…………………………………………… 40
圖4.8 具有優先順序的漸進式權重指定法之演算示意圖……………… 41
圖4.9 演化世代與柏拉圖最佳解之關係圖……………………………… 42
圖4.10 三維目標之具有優先順序的漸進式權重指定方式示意圖……… 44
圖4.11 基因演算法之演算流程圖………………………………………… 46
圖4.12 基因局部搜尋法結構圖…………………………………………… 50
圖4.13 基因局部搜尋法演算流程圖……………………………………… 51
圖5.1 基因演算法求解雙目標問題之柏拉圖曲線變化圖……………… 58
圖5.2 基因局部搜尋法求解雙目標問題之柏拉圖曲線變化圖………… 64
圖6.1 目標空間之各世代收斂變化圖（雙目標問題）………………… 69
圖6.2 各別所搜尋到的柏拉圖最佳解（雙目標問題）………………… 70
圖6.3 相互凌越後所剩下的柏拉圖最佳解（雙目標問題）…………… 70
圖6.4 不同權重指定方式之收斂差異示意圖…………………………… 71
圖6.5 相互凌越後所剩下的柏拉圖最佳解之散佈圖（三目標問題）… 72

[1] Baker, K. R., Introduction to Sequencing and Scheduling, John Wiley, New York, 1974.
[2] Chen, C. L., V. S. Vempati and N. Aljaber, “An Application of Genetic Algorithms for Flow Shop Problems,” European Journal of Operational Research, 80, pp.389-396.1995.
[3] Davis, L., Handbook of Genetic Algorithms, Morgan Kaufmann, San Mateo, CA, 1987.
[4] French, S., Sequencing and Scheduling: An Introduction to the Mathematics of the Job-Shop, John Wiley, New York, 1982.
[5] Gangadharan, R. and C. Rajendran, “A Simulated Annealing Heuristic for Scheduling in a Flowshop with Bicriteria,” Computers & Industrial Engineering, 27, pp.473-476, 1994.
[6] Gen, M. and R. Cheng, Genetic Algorithms and Engineering Design, John Wiley, New York, 1997.
[7] Glass, C. A. and C. N. Potts, “A Comparison of Local Search Methods for Flow Shop Scheduling,” Annals of Operations Research, 63, pp.489-509, 1996.
[8] Goldberg, D. E., Genetic Algorithms in Search, Optimization and Machine Learning, Addison Wesley, Reading, MA, 1989.
[9] Ho, J. C. and Y. L. Chang, “ A New Heuristic for The n-Job, M-Machine Flow-shop Problem,” European Journal of Operational Research, 52, pp.194-202, 1991.
[10] Ishibuchi, H. and H. Murata, “Local Search Procedures in a Multi-Objective Genetic Local Search Algorithm for Scheduling Problems,” Proceedings of IEEE International Conference on SMC, pp.119-124, 1996.
[11] Ishibuchi, H. and H. Murata, “Multi-Objective Genetic Local Search Algorithm,” Proceedings of IEEE International Conference on Evolutionary Computation, pp.119-124, 1996.
[12] Ishibuchi, H. and H. Murata, “Multi-Objective Genetic Local Search Algorithm and Its Applications to Flowshop Scheduling,” IEEE Transactions on SMC, 28, pp.392-403, 1998.
[13] King, J. R., and A. S. Spachis, “Heuristic for Flow-shop Scheduling,” International Journal of Production Research, 18, pp.345-357, 1980.
[14] Michalewicz, Z., Genetic Algorithm + Data Structures = Evolution Programs, 2nd ed., Springer-Verlag, New York, 1994.
[15] Murata, T. and H. Ishibuchi, “Performance Evolution of Genetic Algorithms for Flowshop Scheduling Problems,” Proceedings of 1st IEEE International Conference on Evolutionary Computation,” pp.812-817, 1994.
[16] Murata, T. and H. Ishibuchi, “MOGA: Multi-Objective Genetic Algorithms,” Proceedings of 2nd IEEE International Conference on Evolutionary Computation, pp.284-294, 1995.
[17] Murata, T. and H. Ishibuchi, “Positive and Negative Combination Effects of Crossover and Mutation Operators in Sequencing Problems,” Proceedings of IEEE International Conference on Evolutionary Computation, pp.170-175, 1996.
[18] Murata, T., H. Ishibuchi and H. Tanaka, ”Genetic Algorithm for Flowshop Scheduling Problem,” International Journal of Computers and Industrial Engineering, 30, pp.1061-1071, 1996.
[19] Murata, T., H. Ishibuchi, and H. Tanaka, “Multi-Objective Genetic Algorithm and Its Applications to Flowshop Scheduling,” International Journal of Computers and Industrial Engineering, 30, pp.957-968, 1996.
[20] Murata, T., H. Ishibuchi, and M. Gen, “Neighborhood Structures for Genetic Local Search Algorithms,” Proceedings of 2nd IEEE International Conference on Knowledge-based Intelligent Electronic Systems, 21-23, pp.259-263, 1998.
[21] Nagar, A., J. Haddock and S. Heragu, “Multiple and Bicriteria Scheduling: A Literature Survey,” European Journal of Operational Research, 81, pp.88-104, 1995.
[22] Nagar, A., S. S. Heragu, and J. Haddock, “A Branch and Bound Approach for a Two-Machine Flowshop Scheduling Problem,” Journal of the Operational Research Society, 46, pp.721-734, 1995.
[23] Nagar, A., S. S. Heragu, and J. Haddock, “A Combined Branch-and-Bound and Genetic Algorithm Based Approach for a Flowshop Scheduling Problem,” Annals of Operations Research, 63, pp.397-414, 1996.
[24] Nawaz, M., E. E. Enscore and I. Ham, “A Heuristic Algorithm for the m-Machine, n-Job Flow-shop Sequencing Problem,” OMEGA, 11, pp.91-95, 1983.
[25] Neppali, V. R., C. L. Chen and J. N.D. Gupta, “Genetic Algorithms for the Two-stage Bicriteria Flowshop Problem,” European Journal of Operational Research, 95, pp.356-373, 1996.
[26] Rajendran, C. and D. Chaudhuri, “An Efficient Heuristic Approach to The Scheduling of Jobs in a Flowshop,” European Journal of Operational Research, 61, pp.318-325, 1992.
[27] Rajendran, C., “Two-stage Flowshop Scheduling Problem with Bicriteria,” Journal of the Operational Research Society, 43, pp.871-884, 1992.
[28] Rajendran, C., “Heuristics for Scheduling in Flowshop with Multiple Objectives,” European Journal of Operational Research, 82, pp.540-555, 1995.
[29] Reeves, C. R., “A Genetic Algorithm for Flowshop Sequencing,” Computer & Operations Research, 22, pp.5-13, 1995.
[30] Sridhar, J. and C. Rajendran, “Scheduling in Flowshop and Cellular Manufacturing Systems with Multiple Objectives―A Genetic Algorithmic Approach,” Production Planning & Control, 7, pp.374-382,1996.
[31] Tamaki, H., H. Kita, and S. Kobayashi, “Multi-Objective Optimization by Genetic Algorithms: A Review,” Proceedings of IEEE International Conference on Evolutionary Computation,” pp.517-522, 1996.
[32] Widmer, M. and A. Hertz, “A New Heuristic Method for the Flow Shop Sequencing Problem,” European Journal of Operational Research, 41, pp.186-193, 1989.
[33] 汪玉柏，「運用基因演算法求解流程型工廠之多目標排程」，國立台灣科技大學，碩士論文，民國八十八年。
[34] 周富得，「流程型工廠在雙評估準則下之排程研究」，國立交通大學，博士論文，民國八十六年。
[35] 許民聖，「運用模擬退火法求解流程型工廠之多目標排程」，國立台灣科技大學，碩士論文，民國八十九年。
[36] 許志義，多目標決策，一版，五南圖書出版有限公司，台北，民國八十三年。