跳到主要內容

臺灣博碩士論文加值系統

(44.200.194.255) 您好!臺灣時間:2024/07/23 15:06
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:劉育伶
研究生(外文):Yu-Ling Liu
論文名稱:應用瀰母演算法於多目標排程問題之求解
論文名稱(外文):Applying Memetic Algorithm for Multi-objective Scheduling Problems
指導教授:張百棧張百棧引用關係
學位類別:碩士
校院名稱:元智大學
系所名稱:工業工程與管理學系
學門:工程學門
學類:工業工程學類
論文種類:學術論文
論文出版年:2008
畢業學年度:96
語文別:中文
論文頁數:105
中文關鍵詞:瀰母演算法鄰近搜尋法人造染色體
外文關鍵詞:Memetic AlgorithmLocal searchArtificial Chromosome
相關次數:
  • 被引用被引用:0
  • 點閱點閱:385
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
瀰母演算法(Memetic Algorithm, MA)是近年新興演算法,他不是制式的方法,而是一個通稱,舉凡具有演化並結合鄰近搜尋法(Evolutionary+Local search)都歸類為此方法。本研究所提出之方法稱為Sub-population with Memetic Algorithm(SPMA),應用於求解多目標流程型(Flowshop)之排程問題。
本研究主要分為四個主要部份,首先使用NEH作為建構解,在有限制搜尋時間下更有效找出較佳解,第二將母體賦予權重分群進行演化作更廣泛搜尋,第三結合鄰近搜尋法改變排序進行區域性搜尋,找出更多原先可能未搜尋到的有效解,最後在演化至一定世代時,導入具有機率矩陣所產生的人造解(Artificial Chromosome)注入個體中改善現有最佳解,此架構可具有快速收歛之成效。
在第一個測試問題上,SPMA與其他三個演算法比較,MGISPGA, NSGA-II 和 SPEA2,其衡量指標為D1r。在第二個測試問題上,SPMA與另一個演算法MOSA比較,其衡量指標為柏拉圖最佳解所佔比例。實驗結果顯示,SPMA在多目標流程型問題在測試案例上具有柏拉圖兩大特性-收斂性與擴散性。
Memetic Algorithm (MA) has been a new approach proposed for years; it is not a uniform method but is generally called as a philosophy. For those algorithms with neighboring search (Local Search) are classified to MA. The approach proposed in this paper is named as Sub-population with Memetic Algorithm (SPMA), which is applied for solving multi-objective Flowshop Scheduling Problems.
This paper consists of four phases which firstly apply NEH to be initial solution to search effectively better solution; the second phase is to apply weighted-approach to cluster solved problems for searching more widespread in time constraint; the third phase is to combine with neighboring search to shift the sequence for local search to find out the possible unsearchable feasible solutions; in the final phase, the Artificial Chromosome (AC) with probability matrix will be introduced when the algorithm evolves to certain iteration for injecting to individual to search better combination of chromosomes, this mechanism will make faster convergent time for evolving.
For the first test instance, SPMA compares with three algorithms which is MGISPGA, NSGA-II and SPEA2, the measuring index is D1r. In the second instance, the proportion of Pareto Optimal solutions is applied to be the index for evaluating SPMA and MOSA. The experiments result shows that SPMA has the two important characteristics of Pareto solutions simultaneously which is convergence and spread for solving multi-objective Flowshop Scheduling Problems in test instances.
目 錄
書名頁 i
論文口試委員審定書 ii
授權書 iii
中文摘要 iv
英文摘要 v
誌謝 vi
目錄 vii
圖目錄 ix
表目錄 xiv
第一章 緒論 1
1.1 研究動機 1
1.2 研究目的 2
1.3 研究範圍與限制 2
1.4 研究方法 3
1.5 研究架構與流程 5
第二章 文獻探討 7
2.1 排程問題分類 7
2.2 排程問題績效衡量準則 9
2.3 多目標排程問題 12
2.3.1 多目標最佳化問題 12
2.3.2 多目標排程之相關研究 16
2.4 多目標柏拉圖解集合方法 21
2.4.1 柏拉圖解集合定義 21
2.4.2 衡量柏拉圖解集合方法 22
2.5 瀰母演算法(Memetic Algorithms,MA) 29
2.6 瀰母演算法應用 30
2.7 Artificial Chromosome 2 34
第三章 問題定義 36
3.1 符號說明 36
3.2 雙目標流程型排程 36
3.3 Ishibuchi流程型排程測試資料 38
3.4 Taillard流程型排程測試資料 39
3.5 流程型排程問題之限制與假設 40
第四章 研究方法 41
4.1 SPMA特色 42
4.2 NEH演算法 43
4.2.1 改良NEH演算法之建構解 44
4.2.2 改良NEH演算法之建構解實例說明 45
4.3 SPMA演算流程 47
4.4 鄰近搜尋法(Local search) 52
4.5 衡量方法 56
4.5.1 D1r衡量方式 56
4.5.2 柏拉圖最佳解比例衡量方式 57
第五章 實驗結果與分析 58
5.1 參數設定 58
5.1.1 Ishibuchi測試例題之方法參數組合 58
5.1.2 Taillard測試例題之方法參數組合 61
5.2 各方法於流程型排程問題之比較 61
5.2.1 Ishibuchi測試例題之方法比較結果 61
5.2.2 Taillard測試例題之方法比較結果 66
5.3 分析與討論 77
第六章 結論與未來展望 78
6.1 結論 78
6.2 未來展望 80
參考文獻 81
附錄A. 文獻補充 85
附錄B. SPMA之參數分析 88
B.1 Ishibuchi測試例題 88
B.2 Taillard測試例題 91
附錄C. NEH_hui建構解說明 105
附錄D. 本研究數據成果 106
附錄E. 與實驗室同系列之研究比較表 111
1.Armentano, V. A. and J. C. Arroyo, “An Application of a Multi-Objective Tabu Search Algorithm to a Bicriteria Flowshop Problem,” Journal of Heuristics, 10, pp.463-481, 2004.
2.Baker, K. R., Introduction to Sequencing and scheduling, John Wiley & Sons, New York, 1974.
3.Buriol, L., P.Franca, and P.Moscato., “A new memetic algorithm for the asymmetric traveling salesman problem,” Journal of Heuristics, 10(5):483-506, 2004
4.Chang, P. C., J.C. Hsieh and S.G. Lin, “The Development of Gradual Priority Weighting Approach for the Multi-Objective Flow shop Scheduling Problem,” International Journal of Production Economics, 79(3), pp.171-183, 2002.
5.Chang, P. C., Y. W. Wang and C. H. Liu, “New Operators for Faster Convergence and Better Solution Quality in Modified Genetic Algorithm,” Lecture Notes in Computer Science, 3611, pp.983-991, 2005.
6.Chang, P. C., S. H. Chen and J. C. Hsieh, “A Global Archive Sub-Population Genetic Algorithm with Adaptive Strategy in Multi-Objective Parallel-Machine Scheduling Problem,” accepted by Lecture Notes in Computer Science, 2006.
7.Chu, P. C. and J. E. Beasley, “A Genetic Algorithm for the Multidimensional Knapsack Problem,” Journal of Heuristics, 4(1), p.63-86, 1998.
8.Cochran, j. k., S. M. Horng and J. W. Fowler, “A multi-population genetic algorithm to solve multi-objective scheduling problems for parallel machines,” Computers & Operations Research, 30, 1087-1102, 2003.
9.Coello Coello, C. A., “Evolutionary Multiobjective Optimization: Current and Future Challenges,” Advances in Soft Computing─Engineering, Design and Manufacturing, pp.243-256, 2003.
10.Czyzak, P. and A. Jaszkiewicz, “A Multiobjective Metaheuristic Approach to the Localization of a Chain of Petrol Stations by the Capital Budgeting Model,” Control and Cybernetics, 25(1), pp.177-187, 1996.
11.Deb, K., P. Amrit, A. Sameer and T. Meyarivan, “A Fast and Elitist Multi-Objective Genetic Algorithm: NSGA-II,” IEEE Transactions on Evolutionary Computation, 6(2), pp.182-197, 2002.
12.Franca, P., J. Gupta, A. Mendes, P. Moscato, and K. Veltink., “Metaheuristic approaches for the pure flowshop manufacturing cell problem,” Computers Industrial Engineering, 48(3):491-506, 2005.
13.Franca, P., A. Mendes, and P. Moscato., “A memetic algorithm for the total tardiness single machine scheduling problem,” European Journal of Operational Research, 132-1:224-242, 2000.
14.Gangadharan, R. and C. Rajendran, “A Simulated Annealing Heuristic for Scheduling in a Flowshop with Bicriteria,” Computers & Industrial Engineering, 27, pp.437-476, 1994.
15.Graves, S. C., “A Review of Production Scheduling,” Operations Research, 29(4), pp.646-675, 1981.
16.Gupta, J. N. D., V. R. Neppalli, and F. Werner, “Minimizing Makespan Subject to Minimum Flowtime on Two Identical Parallel Machines,” Computers & Operations Research, 28, pp.705-717, 2001.
17.Hansen, M. P. and A. Jaszkiewicz, “Evaluating the Quality of Approximations to the Non-dominated Set,” Technical Report IMM-REP-1998-7, Technical University of Denmark, 1998.
18.Hart, W., 1994, “Adaptive Global Optimization with Local Search,” PhD thesis. University of California, San Diego, USA.
19.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.
20.Ishibuchii, H., T. Yoshida and T. Murata, “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.
21.Ishibuchii, H., S. Kaige and K. Narukawa, “Comparison between Lamarckian and Baldwinian Rrpair on Multiobjective 0/1 Knapsack Problems,” Lecture Notes in Computer Science 3410: Evolutionary Multi-Criterion Optimization, pp.370-385, 2005.
22.Jaszkiewicz, A., “On the Performance of Multiple-Objective Genetic Local Search on the 0/1 Knapsack Problem-A Comparative Experiment,” IEEE Trans, on Evolutionary Computation, 6(4), pp.402-412, 2002.
23.Knowles, J. D., “Local-Search and Hybrid Evolutionary Algorithms for Pareto Optimization,” Ph.D. Thesis, University of Reading, Department of Computer Science, Reading, U.K., 2002.
24.Krasnogor, N., D. Pelta, J. Verdegay, “Fuzzy memes in multimeme algorithms: a fuzzyevolutionary hybrid, in: Fuzzy Sets based Heuristics for Opt.”, Springer. , 2002
25.Land, M., 1998, “Evolutionary Algorithms with Local Search for Combinatorial Optimization,” PhD thesis. University of California, San Diego, USA.
26.Lei, D. and Z. Wu, “Crowding-measure-based multiobjective evolutionary algorithm for job shop scheduling” The International Journal of Advanced Manufacturing Technology, Online First, 08 October, 2005.
27.Leung, Y. W. and Y. Wang, “Multiobjective Programming Using Uniform Design and Genetic Algorithm,” IEEE Trans. Systems, Man Cybern.-Part C, 30, pp. 293-04, 2000.
28.Maheswaran R., S.G. Ponnambalam, C. Aravindan, ” A meta-heuristic approach to single machine scheduling problems,” Int J Adv Manuf Technol,25: 772–776,2005
29.Mellor, P., “A Review of Job Shop Scheduling,” Operation Research Quarterly, 17, pp.294-301, 1992.
30.Mendes, A., F. Muller, P. Franca, and P. Moscato., “Comparing meta-heuristic approaches for parallel machine scheduling problems with sequence-dependent setup times.” Production Planning L Control,13(2):143-154, 2002.
31.Merz, P., 2000,” Memetic Algorithms for Combinatorial Optimization Problems: Fitness Landscapes and Efective Search Strategies,” PhD thesis. Department of Electrical Engineering and Computer Science, University of Siegen, Germany.
32.Muruta, T. and H. Ishibuchii, “Performance Evolution of Genetic Algorithms for Flowshop Scheduling Problems,” Proceedings of 1st IEEE International Conference on Evolutionary Computation, pp.812-817, 1994.
33.Muruta, T. and H. Ishibuchii, “Positive and Negative Combination Effects of Crossover and Mutation Operators in Sequencing Problems,” Proceedings of IEEE International Conference on Evolutionary Computation, pp170-175, 1996.
34.Moscato, P., “On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms,” Tech. Rep., Caltech Concurrent Computation Program, California Institute of Technology, Pasadena, California,USA, Report.826,1989
35.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.
36.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.
37.Nawaz, M., Encore, EE and Ham, I., “A Heuristic Algorithm for the m-Machine, n-Job Flow-shop Sequencing Problem,” OMEGA, Management Science, 11, No.1, pp91-95.
38.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.
39.P. Moscato and M. Norman, “A memetic aapproach for the traveling salesman problem: implementation of a computational ecology for combinatorial optimization on message-passing system”, Proceeding of 20th International Conference on Parallel Computing and Transportation Applications, 1992.
40.Rajendran, C., “Heuristics for Scheduling in Flowshop with Multiple Objectives,” European Journal of Operational Research, 82, pp.540-555, 1995.
41.Runwei,C. and M.Gen, “Parallel Machine Scheduling Problems Using Memetic Algorithas,” Computers Ind .Engng Vol.33, No. 3-4, pp. 761-764, 1997.
42.Sankar, S. S., S. G. Ponnanbalam. and C. Rajendran, “A Multiobjective Genetic Algorithm for Scheduling A Flexible Manufacturing System,” International Journal of Advanced Manufacturing Technology, 22(3-4), pp.229-236, 2003.
43.Schaffer, J. D., “Multiple Objective Optimization with Vector Evaluated Genetic Algorithms,” Proceedings of 1st International Conference on Genetic Algorithms, pp.93-100, 1985.
44.Sridhar, J. and C. Rajendran, “Scheduling in Flowshop and Cellular Manufacturing Systems with Multiple Objectives–A Genetic Algorithm Approach,” Production Planning & Control, 7, pp.374-382, 1996.
45.Srinivas, N., and K. Deb, “Multiobjective Optimization Using Nondominated sorting in Genetic Algorithms,” Evolutionary Computation, 2, pp.221-248, 1995.
46.Steuer R. “Multiple criteria optimization: theory, computation and application.” NewYork:Wiley; 1986.
47.Taillard, E., “Benchmarks for basic scheduling problems,” European Journal of Operational Research, 64(2), pp.278-285, 1993.
48.T’kindt, V., N. Monmarche, F. Tercient and D. Laugt, “An Ant Colony Optimization Algorithm to Solve A 2-Machine Bicriteria Flowshop Scheduling Problem,” European Journal of Operational Research, 142, pp.250-257, 2002.
49.Varadharajan, T. K., Rajendran, C.,” A multi-objective simulated-annealing algorithm for scheduling in flowshops to minimize the makespan and total flowtime of jobs” European Journal of Operational Research ,(167),pp.772-792,2005.
50.Veldhuizen, D. A., “Multiobjective Evolutionary Algorithm: Classification, Analyses, and New Innovations,” Ph.D. Thesis, Department of Electrical and Computer Engineering, Graduate School of Engineering, Force Institute of Technology, Wright-Patterson AFB, Ohio, 1999.
51.Whitely, D., T. Starkweather and D. Fuquay, “Scheduling Problems and Traveling Salesman: The Genetic Edge Recombination Operator,” in Schafer(ed), Proceedings of the Third International Conference for Genetic Algorithms, Morgan Kaufmann PubIishers, Inc., pp.133-140, 1989.
52.Yeh, W.C, “A Memetic Algorithm for the n/2/Flowshop/αF+ βCmax Scheduling Problem,” the international journal of advanced manufacturing technology,(20),PP.464-473.
53.Zitzler, E. and L. Thiele, “Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach,” IEEE Transactions on Evolutionary Computation, 3(4), pp.257-271, 1999.
54.Zitzler, E., M. Laumanns and L. Thiele, “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.
55.王治元,「智慧型基因演算法於多目標排程之發展與應用—以PCB鑽孔作業為例」,碩士論文,元智大學, 2004。
56.王培珍,「應用遺傳演算法與模擬在動態排程問題之探討」,碩士論文,中原大學, 1995。
57.李家智,「順序性移動式精英政策之子群體基因演算法於多目標問題之應用」,碩士論文,元智大學, 2006。
58.林水耕,「應用混合式基因演算法求解流程型工廠之多目標排程問題」,碩士論文,元智大學, 2001。
59.林我聰,現場排程專家系統-應用個體導向技術建立之研究,資訊與電腦公司出版,1994。
60.林昆霖,「子群體基因演算法於多目標排程之應用─以PCB鑽孔作業為例」,碩士論文,元智大學, 2005。
61.柯瓊惠,「基因演算法結合人造解在生產排程之應用」,碩士論文,元智大學, 2007。
62.許民聖,「運用模擬退火法求解流程型工廠之多目標排程」,碩士論文,國立台灣科技大學, 2000。
63.陳啟嘉,「基因結構探勘於承接式子群體基因演算法求解多目標組合性問題」,碩士論文,元智大學, 2006。
64.湯璟聖,「動態彈性平行機群排程的探討」,碩士論文,中原大學, 2003。
65.傅和彥,生產與作業管理,前程企業管理有限公司,1999。
66.趙淑妙譯,自私的基因(Dawkins, R., 1976),初版,台北:天下遠見出版股份有限公司,頁 287-306 (1995)。
67.劉志宏,「不確定加工時間之平行機台排程」,碩士論文,國立清華大學,1990。
68.謝日章,「柔性計算於生產管理之應用」,博士論文,元智大學, 2002。
電子全文 電子全文(本篇電子全文限研究生所屬學校校內系統及IP範圍內開放)
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊