(44.192.112.123) 您好!臺灣時間:2021/03/07 17:49
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:簡琬蓉
研究生(外文):Wan-jung Chien
論文名稱:以知識為基礎之基因演算法於JSP問題上的應用
論文名稱(外文):A knowledge-based genetic algorithm for the job shop scheduling problem
指導教授:邱宏彬邱宏彬引用關係
指導教授(外文):Hong-bin Chiu
學位類別:碩士
校院名稱:南華大學
系所名稱:資訊管理學研究所
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:2006
畢業學年度:94
語文別:英文
論文頁數:43
中文關鍵詞:零工式排程問題改良式基因演算法知識
外文關鍵詞:knowledgehybrid GAJSP problem
相關次數:
  • 被引用被引用:0
  • 點閱點閱:244
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:37
  • 收藏至我的研究室書目清單書目收藏:0
  本論文提出一新的改良式基因演算法(KGA),此演算法透過由傳統基因演算法的結果搭配屬性的辨識去收集知識,並利用知識引導KGA的過程與交配時基因優良度的評估。此外,為了避免因為知識的應用而使演算過程容易落入區域最佳解,本研究利用突變的方式做區域搜尋,並在結果確定落入區域最佳解時,重新置換母體及替換舊有知識,藉由這些改變來使得本演算法可以同時兼顧集中性和多樣性。最後透過實驗的結果證實,本演算法確實是穩定的且可以找出不錯的排程,而知識的應用也可有效的提供引導的資訊。
  This study presents a novel use of attribution for the extraction of knowledge from job shop scheduling problem. Our algorithm improves the traditional GA and using knowledge to keep the quality of solution. Based on the knowledge, the search space will be leaded to a better search space. In addition, this study uses mutation to do local search and refresh the knowledge and population when the solution fall into local minimum. Based on those methods, our algorithm will have the intensification and diversification. Those can make the algorithm have good convergence and leap for the search space to find the better solution. The experiment results show that algorithm steadily and can find the approximate optimal solution. And the knowledge is useful in provide the gene selection information.
CHAPTER 1 INTRODUCTION 1
 
CHAPTER 2 RELATED WORKS 4
2.1 JOB SHOP SCHEDULING PROBLEM 4
2.2 GENETIC ALGORITHM 5
2.2.1 Crossover operator 5
2.2.2 Mutation operator 6
2.3 GA-BASED JSP ALGORITHM 6
2.3.1 Encoding of chromosome 7
2.3.2 Decoding of chromosome 7
 
CHAPTER 3 RESEARCH APPROACH 9
3.1 DATA PREPARATION 9
3.1.1 Attribution 9
3.1.2 Operations Table 11
3.2 COLLECT KNOWLEDGE 12
3.3 DESIGNING CROSSOVER OPERATOR 14
3.3.1 Eugenic crossover 15
3.3.2 Adjust child 16
 
CHAPTER 4 THE FLOWCHART OF ALGORITHM 18
4.1 COLLECT KNOWLEDGE BY SOLUTION FOR GA 18
4.1.1 Collect solutions by GA 18
4.1.2 Analyze solution to collect knowledge 20
4.2 KNOWLEDGE-BASED GA 22
4.2.1 Blended crossover 23
4.2.2 Forced mutation 24
4.2.3 Collect or replace new knowledge 25
4.2.4 The flowchart of KGA 25
 
CHAPTER 5 EXPERIENTIAL RESULTS 29
5.1 ESTABLISH PARAMETER 30
5.2 EVALUATE OFFSPRING 31
5.3 COMPARE WITH GA 33
5.4 10×10 BENCHMARK PROBLEM 34
 
CHAPTER 6 CONCLUSIONS AND DISCUSSIONS 38
 
REFERENCE 41
1.A. Colorni, M. Dorigo, V. Maniezzo and M. Trubian, “Ant system for Job-shop Scheduling”, Statistics and Computer Science, vol. 34, pp.39-53, 1994.
 
2.A. K. Jain and H. A. Elmaraghy, “Production Scheduling / Rescheduling in flexible manufacturing”, International Journal of Production Research, vol. 35, pp. 281-309, 1997.
 
3.A. S. Jain and S. Meeran, “Job-Shop Scheduling Using Neural Networks”, International Journal of Production Research, vol.36, No.5, pp.1249-1272, 1998.
 
4.A. S. Jain and S. Meeran, “Deterministic job-shop scheduling: Past, present and future”, European Journal of operational research, vol.13, pp. 390-434, 1999.
 
5.C. Dirk Mattfeld and Christian Bierwirth, “An efficient genetic algorithm for job shop scheduling with tardiness objectives”, European journal of operational research, vol. 155, pp.616-630, 2004.
 
6.D.A. Koonce and S.-C. Tsai, “Using data mining to find patterns in genetic algorithm solutions to a job chop schedule”, Computers & Industrial engineering, vol.38, pp.361-374, 2000.
 
7.E. Falkenauer, S. Bouffoix, “A genetic algorithm for job shop”, Proc. of the 1991 IEEE international Conference on Robotics and Automution, 1991.
 
8.E. Nowicki, C. Smutnicki, “A Fast Taboo Search Algorithm: for the Job Shop Problem”, Managemenr Science, vol. 42, pp. 797-813, 1996.
 
9.D.E. Goldberg, “Genetic Algorithms in Search”, Optimization, and Machine Learning, Addison-Wesley, USA, 1989.
 
10.D. Goldberg, R. Lingle Alleles, “Loci and the traveling Salesman Problem”, Proceedings of the First International Conference on Genetic Algorithms, pp. 154-163, 1985.
 
11.E.L. Lawler, J.K. Lenstra and Rinnooy Kan etc., ”Sequencing and scheduling: Algorithms and complexity”, Hardbook in operations research and management, 1993.
 
12.G. Syswerda, “Uniform crossover in genetic algorithms”, Proceedings of the Third International Conference on Genetic Algorithms, pp. 2-11, 1989.
 
13.G. Syswerda, “A study of reproduction in generational and steady-state genetic algorithms”, foundations of Genetic Algorithms, pp. 94-101, 1991.
 
14.J. Carlier and E. Pinson, “An algorithm for solving the job shop problem”, Management science, vol. 35, pp.164-176, 1989
 
15.J. F. Goncalves, M. Mendes, and Maurício G.C. resende, “A hybrid genetic algorithm for the job shop scheduling problem”, European journal of operational research, vol. 167, pp.77-95, 2005.
 
16.K. Morikawa, T. Furuhashi, Y. Uchikawa., “Single Populated Genetic Algorithm and its Application to Job-shop Scheduling”, Proc. of Industrial Electronics, Control, Instrumentation, and Automation on Power Electronics and Motion Control, pp. 1014-1019, 1992.
 
17.L. Davis, “Applying adaptive algorithms to epistatic domains”, Proceedings of the International Joint Conference on Artificial Intelligence, pp. 162-166, 1985.
 
18.L. Davis, “Applying adaptive algorithms to epistatic domains”, In Proc. of the Inter. Joint Con5 on Artificial Intelligence, pp. 162-164, 1985.
 
19.M, Gen and R. Cheng, “Genetic algorithms and engineering design”, New York: John Wiley & Sons, 1997.
 
20.M. Watanbe, K. Ida, and M. Gen, “A genetic algorithm with modified crossover operator and search area adaptation for the job-shop scheduling problem”, Computers & Industrial Engineering, vol. 48, pp.743-752, 2005.
 
21.M. Garey, D. Johnson and R. Sethi, “The complexity of flow shop and job shop scheduling”, Maths Ops Res, vol.1, pp.117-129, 1976.
 
22.M. Kolonko. Some new results on simulated, “annealing applied to the job shop scheduling problem”, European Journal of Operational Research, pp. 123-.136, 1999.
 
23.P.C. Chang, J.C. Hsieh and C.H. Hsiao, “Application of genetic algorithm to the unrelated parallel machine scheduling problem”, Chinese industrial of Industrial Engineers, vol. 19, pp.79-95, 2002.
 
24.R. Cheng, M. Gen, and Y. Tsujimura. “A tutorial survey of job-shop scheduling problems using genetic algorithms---I:Representation”. Computers ind. Engng vol. 30, No. 4, pp.983-997, 1996
 
25.R. Cheng, M. Gen, and Y. Tsujimura. “A tutorial survey of job-shop scheduling problems using genetic algorithms--- II: Hybrid genetic search strategies”. Computers & Engineering, vol. 36, pp.343-364, 1999
 
26.V.L. PJM, A. EHL, and L. JK, “Job shop scheduling by simulated annealing”, Operations Research, 40, pp.113-125, 1992.
 
27.W. K. Fisher, E.O. Thompson, “Amino acid sequence studies on sheep liver fructose-bisphosphatase. II. The complete sequence”, Aust J Biol Sci., vol. 36, pp. 235-250, 1983.
 
28.X. Li, W. Liu, S. Ren, and X. Wang, “A solution of job-shop scheduling .problems based on genetic algorithms”, IEEE Intemational Conference on Systems, Man, and Cybernetics, vol. 3, pp. 1823 -1828, 2001.
 
29.Z. Michalewicz and M. Schoenauer, “Evolutionary algorithms for constrained parameter optimization problems”, Evolutionary Computation, vol. 4, pp. 1-32, 1996.
 
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔