(3.235.139.152) 您好!臺灣時間:2021/05/11 13:11
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

: 
twitterline
研究生:徐麟
研究生(外文):Lin Hsu
論文名稱:以柴比雪夫分群法建構子群體權重向量求解多目標問題
論文名稱(外文):Sub-population Genetic Algorithm II for Multi-objective Parallel Machine Scheduling Problems
指導教授:張百棧張百棧引用關係
學位類別:碩士
校院名稱:元智大學
系所名稱:資訊管理學系
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:2011
畢業學年度:99
語文別:中文
論文頁數:65
中文關鍵詞:多目標排程問題、柴比雪夫分割方法、流程型排程問題、柏拉圖最佳解
外文關鍵詞:Multi-objective Problems, Tchebycheff Decomposition, Parallel Flow-shop Scheduling, Pareto front.
相關次數:
  • 被引用被引用:0
  • 點閱點閱:157
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:1
  • 收藏至我的研究室書目清單書目收藏:0
近年來,排程的單一目標最佳化已無法滿足管理者的需求,管理者於決策時往往會考慮多個衡量指標,因此以往簡單的最佳化排程法則已漸漸淘汰而不被使用。而排程問題隸屬於NP-hard問題,因此以傳統最佳化方法求解相當費時,故本研究提出一個子群體基因演算法(SPGA-II)的啟發式演算方法,其主要方法是利用柴比雪夫分割方法將搜尋空間分割成數個子群體空間並給予權重向量,在不同的權重向量空間中搜尋最佳解;並以流程型排程問題來驗證SGPA-II的適用性,多目標求解法就是在各目標之間進行取捨(tradeoff),本研究二個目標式分別為最小化總完工時間與最小化最大延遲時間,求解相同機台數、不同工件數組合題型之柏拉圖最佳解,研究結果顯示SPGA-II兼顧收斂性與擴散性。本研究所提出的方法SPGA-II將與SPGA、MOGA、NSGA-II、SPEA-II等四種演算式演算法進行比較,並與衡量指標D1R來比較各演算法的優劣,從所有的測試題型結果可以發現,SPGA-II在求解排程問題的結果都相當不錯。

In recent years, industrial manufacturing usually faces the tradeoff of multi-objective decision problems. Many researchers have become more aware of the efficiency of heuristics for solving multi-objective problems. In this paper, we improve the previous SPGA approach and present a Sub-population Genetic Algorithm II (SPGA-II). SPGA-II takes advantage of the Tchebycheff Decomposition and effective Pareto Fronts and Reference Points generated during the evolutionary process to enhance the performance of the proposed approach. Our experimental results show that SPGA-II is able to improve the performance of SPGA in solving Parallel Machine Scheduling Problems.

書名頁 i
論文口試委員審定書 ii
授權書 iii
中文摘要 iv
英文摘要 v
誌謝 vi
目錄 vii
表目錄 ix
圖目錄 x
第一章 緒論1
1.1研究背景與動機1
1.2研究目的2
1.3研究範圍與限制3
1.4研究架構與流程4
第二章 文獻探討6
2.1 排程類型與績效指標6
2.1.1 排程類型6
2.1.2 排程之績效指標8
2.2多目標排程問題與相關研究11
2.2.1多目標最佳化問題11
2.2.2多目標排程之相關研究12
2.3演化式多目標最佳化19
2.3.1演化式演算法(Evolutionary Algorithms, EAs)概念簡介19
2.3.2柏拉圖最佳解(Pareto Optimum Solution)概念簡介 21
2.3.3演算式演算法之方法介紹概念簡介(Evolutionary Algorithms, EAs22
2.3.4第一代:不以柏拉圖解為基礎之求解方法23
2.3.5第一代:以柏拉圖解為基礎之求解方法24
2.3.6第二代:演化式演算法26
2.4SPGA主要概念29
2.4.1SPGA演算法之特色29
2.5小結30
第三章 研究方法31
3.1SPGA-II之特色31
3.2SPGA-II理論模型 32
3.3SPGA-II架構33
3.4SPGA-II演算流程 37
3.5衡量方法43
3.5.1 D1R值衡量方式43
第四章 實驗結果與分析45
4.1參數設計45
4.1.1 共同參數45
4.1.2 SPGA-II個別參數46
4.1.3 SPGA-II世代數與菁英政策47
4.2 流程型排程問題測試結果50
4.2.1 20工件20機台50
4.2.2 40工件20機台51
4.2.3 60工件20機台52
4.2.4 80工件20機台53
4.3 分析與討論54
第五章 結論59
5.1結論59
5.2未來研究方向60
參考文獻61



1.Zhang, Q., Li, H., “MOEA/D: A Multiobjective Evolutionary Algorithm Base on Decomposition,” IEEE Transactions on Evolutionary Computation, 11 (6), pp. 712-731, 2007.
2.Ishibuchi, H., Sakane, Y., Tsukamoto, N., Nojima, Y., “Adaptation of Scalarizing Functions in MOEA/D:An Adaptive Scalarizing Function-Based Multiobjective Evolutionary Algorithm,” Computer Science, pp. 438-452, 2009.
3.Ishibuchi, H., Sakane, Y., Tsukamoto, N., Nojima, Y., “Simultaneous Use of Different Scalarizing Functions in MOEA/D,” GECCO, pp. 519-526, 2010.
4.Jaszkiewicz, A., “On the Performance of Multiple-Objective Genetic Local Search on the 0/1 Knapsack Problem-A Comparative Experiment,” IEEE Transactions on Evolutionary Computation, 6 (4), pp. 402-412, 2002.
5.Ishibuchi, H., Sakane, Y., Tsukamoto, N., Nojima, Y., “Effects of Using Two Neighborhood Structures on the Performance of Cellular Evolutionary Algorithms for Many-Objective Optimization,” IEEE Congress on Evolutionary Computation (CEC 2009), pp. 2508-2515, 2009.
6.Li, H., Zhang, Q., “Multiobjective Optimization Problems With Complicated Pareto Sets, MOEA/D and NSGA-II,” IEEE Transactions on Evolutionary Computation, 13 (2), pp. 284-302, 2009.
7.Zhang, Q., Liu, W., Li, H., “The Performance of a New Version of MOEA/D on CEC09 Unconstrained MOP Test Instances,” CEC''09 Proceedings of the Eleventh conference on Congress on Evolutionary Computation, pp. 203-208, 2009.
8.Zhang, Q., Liu, W., Tsang, E., Virginas, B., “Expensive Multiobjective Optimization by MOEA/D with Gaussian Process Model,” IEEE Transactions on Evolutionary Computation, 14 (3), pp. 456-474, 2010.
9.Joao, A., Alemida, M., “MOTGA: A multiobjective Tchebycheff based genetic algorithm for the multidimensional knapsack problem,” Computers & Operations Research, pp. 3458-3470, 2007.
10.Mellor, P., “A Review of Job Shop Scheduling,” Operation Research Quarterly, 17, pp. 294-301, 1992.
11.Muruta, T., Ishibuchi, H., Tanaka, H., “Genetic Algorithm for Flowshop Scheduling Problem,” International Journal of Computers and Industrial Engineering, 30, pp. 1061-1071, 1996.
12.Lee, C. C., “Fuzzy logic in Control Systems: Fuzzy Logic Controller-Part I,” IEEE Transactions on Systems, Man and Cybernetics, 20 (2), pp. 404-418, 1990.
13.Ho, J. C., Chang, Y. L., “A New Heuristic for The n-Job, m-Machine Flow-shop Problem,” European Journal of Operational Research, 52, pp. 194-202, 1991.
14.Gangadharan, R., Rajendran, C., “A Simulated Annealing Heuristic for Scheduling in a Flowshop with Bicriteria,” Computers & Industrial Engineering, 27, pp. 437-476, 1994.
15.Rajendran, C., “Heuristics for Scheduling in Flowshop with Multiple Objectives,” European Journal of Operational Research, 82, pp. 540-555, 1995.
16.Nagar, A., Heragu, S., Haddock, S. J., “A Branch and Bound Approach for a Two-Machine Flowshop Scheduling Problem,” Journal of the Operational Research Society, 46, pp. 721-734, 1995.
17.Muruta, T., Ishibuchi, H., “MOGA: Multi-Objective Genetic Algorithm,” Proceedings of 2nd IEEE International Conference on Evolutionary Computation, pp. 170-175, 1996.
18.Neppali, V. R., Chen, C. L., Gupta, J. N. D., “Genetic Algorithms for the Two-stage Bicriteria Flowshop Problem,” European Journal of Operational Research, 95, pp. 356-373, 1996.
19.Sridhar, J., Rajendran, C., “Scheduling in Flowshop and Cellular Manufacturing Systems with Multiple Objectives-A Genetic Algorithm Approach,” Production Planning & Control, 7, pp. 374-382, 1996.
20.Funda, S. S., Ulusoy, G., “Parallel Machine Scheduling with Earliness and Tardiness Penalties,” Computers and Operations Research, 26 (8), pp. 773-787, 1999.
21.Hapke, M., Jaszkiewicz, A., Slowinski, R., “Pareto Simulated Annealing for Fuzzy Multi-Objective Combinatorial Optimization,” Journal of Heuristics, 6, pp. 329-345, 2000.
22.Gupta, J. N. D., Neppalli, V. R., Werner, F., “Minimizing Makespan Subject to minimum Flowtime on Two Identical Parallel Machines,” Computers & Operations Research, 28, pp. 705-717, 2001.
23.Sivakumar, A. I., “Multiobjective Dynamic Scheduling Using Discrete Event Simulation,” International Journal of Computer Integrated Manufacturing, 14 (2), pp. 154-167, 2001.
24.Kacem, I., Hammadi, S., Borne, P., “Pareto-Optimality Approach for Flexible Job-Shop Scheduling Problems: Hybridization of Evolutionary Algorithms and Fuzzy Logic,” Mathematics and Computers in Simulation, 60 (3-5), pp. 245-276, 2002.
25.T’kindt, V., Monmarche, N., Tercient, F., Laugt, D., “An Ant Colony Optimization Algorithm to Solve A 2-Machine Bicriteria Flowshop Scheduling Problem,” European Journal of Operational Research, 142, pp. 250-257, 2002.
26.Sankar, S. S., Ponnanbalam, S. G., Rajendran, C., “A Multiobjective Genetic Algorithm for Scheduling A Flexible Manufacturing System,” International Journal of Advanced Manufacturing Technology, 22 (3-4), pp. 229-236, 2003.
27.Sun, H., Wang, G., “Parallel Machine Earliness and Tardiness Scheduling with Proportional Weights,” Computers &Operations Research, 30 (5), pp. 801-808, 2003.
28.Chang, P. C., Hsieh, J. C., Lin, S. G., “The Development of Gradual Priority Weighting Approach for the Multi-Objective Scheduling Flowshop Scheduling Problem,” International Journal of Production Economics, 79 (3), pp. 171-181, 2002.
29.Zitzler, E., Laumanns, M., Bleuler, S., “A Tutorial on Evolutionary Multiobjective Optimization,” Proceedings of the Workshop on Multiple Objective Metaheuristics, 2004.
30.Coello Coello, C. A., “Evolutionary Multiobjective Optimization: Current and Future Challenges,” Advances in Soft Computing-Engineering, Design and Manufacturing, pp. 243-256, 2003.
31.Fonseca, C. M., Fleming, P. J., “An overview of evolutionary algorithms in multiobjective optimization,” Evolutionary Computation, 3 (1), pp.1-16, 1995.
32.Schaffer, J. D., “Multiple Objective Optimization with Vector Evaluated Genetic Algorithms,” Proceedings of 1st International Conference on Genetic Algorithms, pp. 93-100, 1985.
33.Goldberg, D. E., Richardson, J., “Genetic algorithm with sharing for multimodal function optimization,” Genetic Algorithms and Their Applications: Proceedings of the second International Conference on Genetic Algorithms, pp. 41-49, 1987.
34.Fourman, M. P., “Compaction of symbolic layout using genetic algorithms,” In Genetic Algorithms and their Applications: Proceedings of the First International Conference on Genetic Algorithms, pp. 141-153, 1985.
35.Srinivas, N., Deb, K., “Multiobjective Optimization Using Nondominated sorting in Genetic Algorithms,” Evolutionary Computation, pp. 221-248, 1995.
36.Horn, J., Nafpliotis, N., Goldberg, D. E., “A Niched Pareto Genetic Algorithm for Multiobjective Optimization,” Proceedings of 1st ICGA, pp. 82-87, 1994.
37.Erickson, M., Mayer, A., Horn, J., “The Niched Pareto Genetic Algorithm 2 Applied to Design of Groundwater Remediation Systems,” First International Conference on Evolutionary Multi-Criterion Optimization, pp. 681-695, 2001.
38.Zitzler, E., Thiele, L., “Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach,” IEEE Transactions on Evolutionary Computation, 3 (4), pp. 257-271, 1999.
39.Morse, J. N., “Reducing the size of the nondominated set: Pruning by clustering,” Computers and Operations Research, 7 (1-2), pp.55-66, 1980.
40.Zitzler, E., Laumanns, M., Thiele, L., “SPEA2: Improving the Strength Pareto Evolutionary Algorithm,” Technical Report 103, Computer Engineering and Networks Laboratory (TIK), Swiss Federal Institute of Technology (ETH) Zurich, Gloriastrasse 35, CH-8092 Zurich, Switzerland, 2001.
41.Knowles, J.D., Corne, D.W., “Approximating the nondominated front using the Pareto Archived Evolution Strategy,” Evolutionary Computation Journal, 8 (2), pp. 149-172, 2000.
42.Corne, D. W., Knowes, J. D., Oates, M. J., “The Pareto Envelope-based Selection Algorithm for Multiobjective Optimization,” Proceedings of the Parallel Problem Solving from Nature VI Conference, pp. 839-848, 2000.
43.Corne, D. W., Jerram, N. R., Knowes, J. D., Oates, M. J., “PESA-II: Region-based Selection in Evolutionary Multiobjective Optimization,” Proceedings of the Genetic and Evolutionary Computation Conference, pp. 283-290, 2001.
44.Deb, K., Amrit, P., Sameer, A., Meyarivan, T., “A Fast and Elitist Multi-Objective Genetic Algorithm-NSGA-II,” Proceedings of the Parallel Problem Solving from Nature VI Conference, pp. 849-858, 2000.
45.Van Veldhuizen, D. A., Lamont, G. B., “Multiobjective Optimization with Messy Genetic Algorithms,” Proceedings of the 2000 ACM Symposium on Applied Computing, pp. 470-476, 2000.
46.Goldberg, D. E. et al., “Messy Genetic Algorithms: Motivation, Analysis, and First Result,” Complex Systems, 3, pp. 493-530, 1989.
47.Zydallis, J. B., Lamont, G. B., Van Veldhuizen, A. D., “Messy Genetic Algorithm Based Multi-Objective Optimization: A Comparative Statistical Analysis,” PPSN/SAB Workshop on Multiobjective Problem Solving from Nature (MPSN), 2000.
48.Goldberg, D. E., Deb, K., Kargupta, H., Harik, G., “Rapid, Accurate Optimization of Difficult Problems Using Fast Messy Genetic Algorithms,” Technical Report 93004, 1993.
49.Coello Coello, C. A., Gregorio, T. P., “A Micro-Genetic Algorithm for Multiobjective Optimization,” First International Conference on Evolutionary Multi-Criterion Optimization, pp. 126-140, 2001.
50.Muruta, T., Ishibuchi, H., “Multi-objective Genetic Local Search Algorithm and Its Application to Flowshop Scheduling,” IEEE Transactions on SMC, 28, pp. 392-403, 1998.
51.Muruta, T., Ishibuchi, H., “Performance Evolution of Genetic Algorithms for Flowshop Scheduling Problems,” Proceedings of 1st IEEE International Conference on Evolutionary Computation, pp. 812-817, 1994
52.Muruta, T., Ishibuchi, H., “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.
53.Ishibuchi, H., Yoshida, T., Murata, T., “Balance between Genetic Search and Local Search in Memetic Algorithms for Multiobjective Permutation Flowshop Scheduling,” IEEE Trans. on Evolutionary Computation, 7 (2), pp. 204-223, 2003.
54.Brucker, P., Scheduling algorithms, Springer, Berin, 1998.
55.王治元,「智慧型基因演算法於多目標排程之發展與應用-以PCB鑽孔作業為例」,元智大學,碩士論文,2004。
56.林昆霖,「子群體基因演算法於多目標排程之應用-以PCB鑽孔作業為例」,元智大學,碩士論文,2005。
57.林水耕,「應用混合式基因演算法求解流程型工廠之多目標排程問題」,元智大學,碩士論文,2001。
58.林我聰,現場排程專家系統-應用個體導向技術建立之研究,資訊與電腦公司出版,1994。
59.王培珍,「應用遺傳演算法與模擬在動態排程問題之探討」,中原大學,碩士論文,1995。
60.周富得,「流程型工廠在雙評估準則下之排程研究」,國立交通大學,博士論文,1997。
61.汪玉柏,「運用基因演算法求解流程型工廠之多目標排程」,國立台灣科技大學,碩士論文,1999。
62.駱景堯,吳泰熙,張俊仁,「結合模糊理論與遺傳演算法於多目標彈性製造系統」,工業工程學刊,第16卷,第三期,1999。
63.許民聖,「運用模擬退火法求解流程型工廠之多目標排程」,國立台灣科技大學,碩士論文,2000。
64.阮永漢,「系統模擬與基因演算法於完全相同機台排程之應用」,碩士論文,元智大學,2002。
65.許志義,多目標決策,五南圖書出版公司,1995。


QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔