跳到主要內容

臺灣博碩士論文加值系統

(44.192.67.10) 您好!臺灣時間:2024/11/09 19:10
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:林建民
研究生(外文):Chan-Min Lin
論文名稱:混合基因演算法應用於具迴流特性流程工廠之研究
論文名稱(外文):Research on the Hybrid Genetic Algorithm in Re-entrant Flow Shop and Re-entrant Permutation Flow Shop Problems
指導教授:潘昭賢潘昭賢引用關係
指導教授(外文):Chao-Hsien Pan
學位類別:碩士
校院名稱:國立臺灣科技大學
系所名稱:工業管理系
學門:商業及管理學門
學類:其他商業及管理學類
論文種類:學術論文
論文出版年:2003
畢業學年度:91
語文別:中文
論文頁數:64
中文關鍵詞:混合基因演算法迴流流程式工廠
外文關鍵詞:Hybrid Genetic AlgorithmRe-entrantFlow Shop
相關次數:
  • 被引用被引用:5
  • 點閱點閱:456
  • 評分評分:
  • 下載下載:66
  • 收藏至我的研究室書目清單書目收藏:3
在生產管理中排程問題可被定義為某特定作業的時間設定,包括設備及人員活動的使用,亦即是要完成某些工作時,對資源做一有效之分配。大部分在生產排程中相關的一些假設為工作最多只拜訪某一機台一次,但這通常與實際的情況相違背。現在一種新的製造環境越來越受到重視,那就是迴流特性流程型工廠。在迴流式工廠中的基本特徵為一個工作拜訪同一機台最少一次。這種製造環境特徵在複雜的半導體製程中是非常重要與常見的,像是一個晶片重複拜訪同一機台多次以去進行多重的加工步驟。而迴流型排列流程工廠是迴流式流程型工廠中的一個特例,再迴流式流程型工廠中工作在所有的機器上成相同次序之安排就是迴流型排列流程工廠。
本論文的目的在於利用基因演算法應用於迴流型流程型工廠和迴流型排列流程工廠並以總生產時間最短為目標,利用基因演算法的良好特性:跳脫區域最佳解以達到接近整體最佳解的解。並利用混合式基因演算法去改善績效。
Scheduling problem in production management can be defined the usage of time, equipment, and labor for a particular process in production. It is accomplish a job by allocating resources efficiently. Most production scheduling-related research assumes that a job visits certain machines at most once, but this is often violated in practical situations. A new type of manufacturing environment, the reentrant flow shop, has recently attracted attention. The basic characteristic of a reentrant shop is that a job visits certain machines more than once. These systems are particularly important in complex manufacturing environments such as semiconductor manufacturing where each wafer re-visits the same machines for multiple processing steps. This environment is one of the re-entrant flow shop (RFS) scheduling problems.
The reentrant permutation flow shop (RPFS) problem is a special case of the reentrant flow shop (RFS) problem. The RFS scheduling problem where no passing is allowed is called the RPFS.
The aim of this thesis is to minimize makespan by using the specialty of Genetic Algorithm to escape from local optimal solution to near-optimal solution for RFS and RPFS scheduling problems. In addition, hybrid genetic algorithms (HGA) are proposed to improve the performance of GA for solving RFS and RPFS.
Chinese Abstract I
Abstract II
Acknowledgement III
Contents IV
Contents of Figures VI
Contents of Tables VII
CHAPTER 1 INTRODUCTION 1
CHAPTER 2 LITERATURE REVIEW 3
2.1 Flow Shop Scheduling Problem 3
2.2 Permutation Flow Shop Scheduling Problem 3
2.3 Re-entrant Flow Shop 5
2.4 Re-entrant Permutation Flow Shop 7
2.5 Genetic Algorithm 8
CHAPTER 3 PROBLEM STATEMENT AND HYBRID GENETIC ALGORITHM 10
3.1 Problem Description 10
3.1.1 Integer Programming Model for RFS 11
3.1.2 Integer Programming Model for RPFS 12
3.2 Basic Genetic Algorithm Structure 14
3.3 The Difference Between GA and Traditional Methods 16
3.4 Hybrid Genetic Algorithm 17
3.5 The Proposed Hybrid Genetic Algorithms for Reentrant Flow-Shop and Reentrant Permutation Flow-Shop 18
3.5.1 Parameters Setting 20
3.5.2 Encoding 20
3.5.3 Generation of Initial Population 21
3.5.4 Crossover 22
3.5.5 Mutation 24
3.5.6 Other Genetic Operators 26
3.5.7 Fitness Function: 28
3.5.8 Termination 28
3.5.9 Selection 29
CHAPTER 4 ILLUSTRATIVE EXAMPLES 31
4.1 Examples 31
4.1.1 Example for RFS 31
4.1.2 Example for RPFS 37
CHAPTER 5 ANALYSIS OF EXPERIMENT RESULTS AND CONCLUSIONS 44
5.1 Experiment Design 44
5.1.1 Types of Problems 44
5.1.2 Performance of Exact and Heuristic Algorithms 45
5.1.3 Experimental Environment and Facility 45
5.2 Analysis of RFS Experiment Results 45
5.2.1 Small Problems 45
5.2.2 Medium Problems 49
5.2.3 Large Problems 51
5.3 Analysis of RPFS Experiment Results 52
5.3.1 Small Problems 53
5.3.2 Medium Problems 55
5.3.3 Large Problems 56
5.3 Conclusions and Suggestions for Future Study 58
5.3.1 Conclusions 58
5.3.2 Suggestions for Future Study 58
REFERENCES 60
1. Baker, K. R., (1974). Introduction to sequencing and scheduling. John Wiley & Sons, New York.
2. Baker, K. R., Balas, E., and Zawack, D., (1998). The shifting bottleneck procedure for job-shop scheduling. Management Science, 34: pp.391-401.
3. Beasly, J. E., (1990). OR-library: Distribution Test Problems by Electronic Mail, Journal of the Operational Research Society, 41, no.11. http://mscmga.ms.ic.ac.uk/info.html.
4. Bispo, C. F., and Tayur, S., (2001). Managing simple re-entrant flow lines: theoretical foundation and experimental results. IIE Transactions, 33: pp.609-623.
5. Bjegal, J. E., and Davern, J. J., (1990). Genetic algorithms and job shop scheduling. Computers and Industrial Engineering 19.
6. Blazewicz, J., Ecker, K., Schmidt, G.., and Weglarz, J., (1993). Scheduling in computer and manufacturing Systems. Springer, Berlin.
7. Bowden, Jr., R. O., (1992). Genetic algorithm based machine learning applied to the dynamic routing of discrete parts. Dissertation, Department of Industrial Engineering, Mississippi State University.
8. Campbell, H., Dudek, R., and Smith, M., (1970). A heuristic algorithm for the n-job m-mahcine sequencing problem. Management Science, 16B: pp.630-637.
9. Chen, C., Vempati, V., and Ajabber, N., (1995). An application of genetic algorithms for flow shop problems. European Journal of Operational Research, 80: pp.389-396.
10. Cheng, R., (1997). A study on genetic algorithms-based optimal scheduling techniques. PhD thesis, Tokyo Institute of Technology.
11. Cheng, R, Gen, M., and Tsujimura, Y., (1996). A tutorial survey of job-shop scheduling problems using genetic algorithms, part Ⅰ: International Journal of Computers and Industrial Engineering, 30: pp.983-997.
12. Cheng, R. Gen, M. and Tsujimura, Y., (1999). A tutorial survey of job-shop scheduling problems using genetic algorithms, part Ⅱ: hybrid genetic: genetic search strategies, Computers and Operations Research, 36: pp.343-364.
13. Cleveland, G. A., and Smith, S.F., (1989). Using genetic algorithms to schedule flow shop release. in: J. D. Schaffer (ed.), Proceedings of the Third International Conference on Genetic Algorithms Applications, Morgan Kanufmann, San Mateo, CA, pp.160-169.
14. Conway, R., Maxwell, W., and Miller, L., (1967). Theory of scheduling. Addison-Wesley.
15. Dannenbring, D. G.., (1977). An evaluation of flow shop sequencing heuristics. Management Science, 23: pp.1174-1182.
16. Davis, L., (1985). Job shop scheduling with genetic algorithms. in: J. J. Grefenstette (ed.), Proceedings of an International Conference on Genetic Algorithms and Their Applications, Carnegie-Mellon University, Pittsburgh, PA, pp.136-140.
17. Demirkol, E., Uzsoy R., (2000). Decomposition methods for reentrant flow shops with sequence-dependent setup times. Journal of Scheduling, 3: pp.155-177.
18. French, S., (1982). Sequencing and scheduling: An introduction to the mathematics of the job-shop. Ellis Horwood, Chichester, U. K.
19. Garey, M.R., Johnson, D.S., and Sethi, R., (1976). The complexity of flow-shop and job-shop scheduling. Mathematics of Operations Research, 1: pp.117-129.
20. Gillies, A., (1985). Machine learning procedures for generating image domain feature detectors. Ph. D. thesis, University of Michigan, Ann Arbor.
21. Goldberg, D. E., (1989). Genetic algorithms in search. Optimization and Machine Learning, Addison-Wesley, Reading, Ma.
22. Goldberg, D.E., and Lingle, Jr., R., (1985). Alleles, loci and the Traveling Salesman Problem, in: J. J. grefenstette(ed.)k Proceedings of an International Conference on Genetic Algorithms and Their Applications, Carnegie-Mellon University, Pittsburgh, PA, pp.154-159.
23. Graves, S. C., Meal, H.C., Stefek, D., Zeghmi, A.H., (1983). Scheduling of re-entrant flow shops. Journal of Operations Management, 3: pp.197-207.
24. Grefenstette, J. and Baker, J., How genetic algorithms work: a critical look at implicit parallelism. in Schaffer, pp.20-27.
25. Grefenstette, J., Gopal, R., Rosmaita, B., and Van Gucht, D., (1985) Genetic algorithm for the traveling salesman problem, in: J.J. Grefenstette (ed.), Proceedings of an International Conference on Genetic Algorithms and Their Applications, Carnegie-Mellon University, Pittsburgh, PA, pp.160-168.
26. Gupta J. N. D. (1971). A functional heuristic algorithm for the flow shop scheduling problem. Operations Research. 22: pp.39-47.
27. Holland, J., (1975). Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor.
28. Hwang, H. and Sun, J. U., (1998). Production sequencing problem with re-entrant work flows and sequence dependent setup times. International Journal of Production Research, 36: pp.2435-2450.
29. Johnson, S. M., (1954). Optimal two- and three-stage production schedules with setup times included. Naval Res. Logist., 1: pp.287-326
30. Kubiak W, Lou SXC, Wang, Y. M., (1996). Mean flow time minimizations in re-entrant job shops with hub. Operations Research, 44: pp764-776.
31. Kubota, A., (1995). Study on optimal scheduling for manufacturing system by genetic algorithms. Master’s thesis, Ashikaga Institute of Technology, Ashikaga, Japan.
32. Manne, A. S., (1960). On the job-shop scheduling problem. Operations Research. 8: pp.219223.
33. Michalewicz, Z., (1994). Genetic Algorithm + Data Structure = Evolution Programs, 2nd ed., Springer-Verlag, New York.
34. Murata, T., Ishibuchi, H. and Tanaka, H., (1996). Genetic algorithms for flows shop scheduling problems. Computers Industrial Engineering, 30: pp.1061-1071.
35. Nawaz, M., Enscore, E., and Ham, I., (1983). A heuristic algorithm for the m-machine n-job flow shop sequencing problem. Omega, 11: pp.11-95.
36. Palmer, D. S. (1965). Sequencing jobs through a multi-stage process in the minimum total time-A quick method of obtaining a near optimum. Operations Research. 16: pp.101-107.
37. Pan, J. C. H. and Chen, J. S., (2003). A comparative study of scheduling-generation procedures for the reentrant shops scheduling problem. Accepted by International Journal of Industrial Engineering.
38. Pan, J. C. H. and Chen, J. S., (2003). Minimizing makespan in reentrant permutation flow-shops. Accepted by Journal of the Operational Research Society.
39. Pinedo, M., (1995). Scheduling: theory, algorithms, and systems. Prentice-Hall, New Jersey.
40. Reeves, C. and Wright, C., (1995). A genetic algorithm for flow shop sequencing. Computers and Operations Research, 22: pp.5-13.
41. Rinnooy Kan, A. H. G., (1976). Machine Scheduling Problems: Classification, Complexity and Computations. Martinus Nijhoff, The Hague.
42. Sannomiya, N. and Iima, H., (1996). Application of genetic algorithms to scheduling problems in manufacturing process. in Fogel, pp523-528.
43. Tsujimura, Y., Gern, M. Parts loading scheduling in a flexible forging machine using an advanced genetic algorithm. Journal of Intelligent Manufacturing, 10(2): pp.49-56.
44. Tsujimura, Y., M. Gen and Kubota, E., (1995). Flow-shop scheduling with fuzzy processing time using genetic algorithms. The 11th Fuzzy Systems Symposium, Okinawa.(in Japan): pp.248-252.
45. Vargas-Villamil, F. D. and Rivera, D. E. (2001). A model predictive control approach for real-time optimization of reentrant manufacturing lines. Computers in Industry, 45: pp.45-57.
46. Wagner, H. M. (1959). An integer linear-programming model for machine scheduling. Naval Res Logist. 6: pp.131140.
47. Wang, M. Y., Sethi SP and Van De Velde SL (1997). Minimizing makespan in a class of reentrant shops. Operations Research 45: pp.702-712.
48. Whitley, D., Starkwether, T., and Shaneer, D., (1991). The Traveling Salesman and Sequence Scheduling Problems: Quality solutions using genetic edge recombination, in: L. Davis (ed.), Handbook of Genetic Algorithms, van Nostrand Reinhold, New York, pp.350-372.
49. Wilson, J. M. (1989). Alternative formulations of a flow-shop scheduling problem. Operations Research. 40: pp.395399.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top