跳到主要內容

臺灣博碩士論文加值系統

(44.201.99.222) 您好!臺灣時間:2022/12/04 01:05
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:曾佳瑩
研究生(外文):Jia-Ying Tzeng
論文名稱:應用多目標進化演算法於集束式設備排程
論文名稱(外文):Applications of Multi-objective Evolutionary Algorithms to Cluster Tool Scheduling
指導教授:劉東官
指導教授(外文):Tung-Kuan Liu
學位類別:碩士
校院名稱:國立高雄第一科技大學
系所名稱:機械與自動化工程所
學門:工程學門
學類:機械工程學類
論文種類:學術論文
論文出版年:2005
畢業學年度:94
語文別:英文
論文頁數:80
中文關鍵詞:多目標進化演算法不等式集束式設備排程死鎖田口實驗法
外文關鍵詞:Method of InequalitiesMulti-objective Evolutionary Algorithm
相關次數:
  • 被引用被引用:0
  • 點閱點閱:93
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
中文摘要
本論文中,提出一種新穎的全域搜尋法,稱「多目標進化演算法」(MOEA)
來解決晶圓集束式設備排程最佳化問題。MOEA主要結合多目標理論、不等式法
(MOI) 和基因遺傳演算法 (GA) 之特性,同時針對問題的目標及參數空間全域搜
尋而求出最佳或鄰近解;另外,加入多樣性策略,亦為減少每代個體適應值相同
的機會,以防止提早收歛現象。
本文利用所提出之 MOEA 及彈性式程序,應用於兩種特定之集束式設備排
程問題並涵誑|種實際限制條件,雖彈性式程序是最有效率的製造方式,但將易
產生出死鎖問題,故本法於適應函數的建構中加入懲罰值,經不斷的進化而排除
不適合解;而為了提昇 MOEA 之效能,此論文採用田口實驗法及全因子實驗來
選取 MOEA 最佳參數及不等式中之輔助向量效能指標誤差值;最後,經多次實
驗驗證可知其效果將比其他學者所提出方法穩健及精確。
ABSTRACT
In this thesis, we propose a novel global heuristic method which is called
“Multi-objective Evolutionary Algorithm” (MOEA) to solve cluster tool scheduling
problems. The MOEA approach, a method of combining the multi-objective theory,
methods of inequalities (MOI) and genetic algorithm, can consider the relation of the
parameter and the objective space simultaneously to explore whole solution space and
find an optimum or near optimal solution. In addition, using diversity strategy to reduce
the opportunity of the same fitness values in each generation, and then to avoid
premature convergence phenomenon.
This thesis applies MOEA with flexible process to two types of particular cluster
tool scheduling problems that includes four practical constraint conditions. The flexible
process is an effective manufacturing way, but it may come about deadlock state easily.
Therefore, we deal with this problem by assigning a high penalty value to the objective
in fitness function and eliminate unfeasible solutions in the course of evolution
constantly. To enhance performance of MOEA, this thesis adopts Taguchi experiment
iii
method and Full-factorial experiments to find the best parameters of MOEA and
admissible vector of auxiliary vector performance index in MOI. In conclusion, many
experiments demonstrated that the proposed MOEA approach is more robust and more
accurate than other methods by some scholars reported.
Contents
中文摘要........................................................................................................................... i
ABSTRACT .................................................................................................................... ii
誌 謝............................................................................................................................. iv
Contents.......................................................................................................................... v
List of Tables ................................................................................................................. vii
List of Figures .............................................................................................................. viii
Define Parameters ......................................................................................................... ix
Chapter 1 Introduction .................................................................................................. 1
1.1 Background of the study......................................................................................... 1
1.2 Literature Survey .................................................................................................... 2
1.3 Problems in Cluster Tool Scheduling..................................................................... 3
1.4 Motivation of Research .......................................................................................... 4
1.5 Thesis Organization................................................................................................ 5
Chapter 2 Fundamentals of Multi-objective Evolutionary Algorithm (MOEA)...... 6
2.1 The Concepts of Multi-objective Optimizations .................................................... 6
2.2 The Method of Inequalities and Vector Performance Index .................................. 7
2.3 Auxiliary Vector Performance Index in MOI......................................................... 8
2.4 Improved Rank-based Fitness Assignment Method............................................... 9
2.5 Genetic Algorithms .............................................................................................. 10
2.5.1 The structure of Genetic Algorithm............................................................... 11
2.5.2 Properties of Genetic Algorithm ................................................................... 14
Chapter 3 MOEA for Cluster Tool Scheduling Problems......................................... 15
3.1 Cluster Tool .......................................................................................................... 15
3.2 Problem Statement of Cluster Tool Scheduling ................................................... 17
3.2.1 Scheduling of the Flexible Process for the Cluster Tool............................... 17
3.2.2 Deadlock-free Schedule with Limited Buffers.............................................. 20
3.3 MOEA Approach for Cluster Tool Scheduling Problems.................................... 24
vi
3.3.1 Initialization (Chromosome Representation)................................................. 25
3.3.2 Fitness Assignment........................................................................................ 27
3.3.3 Selection Operation (Reproduction).............................................................. 30
3.3.4 Crossover Operation...................................................................................... 30
3.3.5 Mutation Operation ....................................................................................... 31
3.3.6 Maintain Diversity Strategy........................................................................... 32
3.3.7 Calculate the variance of Genes .................................................................... 33
3.3.8 Auxiliary Vector Performance Index in MOI................................................ 34
3.3.9 Improved Rank-based Fitness Assignment Method...................................... 35
3.4 Detailed steps of MOEA....................................................................................... 35
Chapter 4 Case Study................................................................................................... 37
4.1 Scheduling Material Handling Problem ............................................................... 37
4.1.1 Definition of Problems .................................................................................. 37
4.1.2 Design of Parameters in MOEA.................................................................... 40
4.1.3 Design of the Admissible Vector of AVPI in MOI ....................................... 45
4.1.4 Convergence Curve of MOEA ...................................................................... 46
4.1.5 Experiment Results........................................................................................ 46
4.2 Scheduling with Multiple Lot and Finite Buffer sizes Problem........................... 49
4.2.1 Definition of Problems .................................................................................. 49
4.2.2 Design of Parameters in MOEA.................................................................... 50
4.2.3 Design of the Admissible Vector of AVPI in MOI ....................................... 53
4.2.4 Convergence Curve of MOEA ...................................................................... 54
4.2.5 Experiment Results........................................................................................ 56
4.3 The best solutions by MOEA for Cluster Tool Scheduling.................................. 58
Chapter 5 Conclution and Future Works................................................................... 64
Reference ....................................................................................................................... 65
vii
List of Tables
Table 3-2-1:Job requirements for flexible process ...................................................... 19
Table 3-2-2:Job requirements for schedule with limited buffers................................. 22
Table 3-3-1:Precedence and processing time of the operations .................................. 26
Table 4-1-1:The precedence of operation.................................................................... 38
Table 4-1-2:The operation time and transporting time................................................ 38
Table 4-1-3:The precedence of operation.................................................................... 39
Table 4-1-4:The operation time of chamber................................................................ 39
Table 4-1-5:Definition of factor level for scheduling material handling problem ...... 40
Table 4-1-6:L9(34) Orthogonal array ........................................................................... 41
Table 4-1-7:Experiment results of scheduling material handling problem ................. 42
Table 4-1-8:Response table of scheduling material handling problem ....................... 43
Table 4-1-9:Analysis of Variance for scheduling material handling problem ............ 44
Table 4-1-10:Definition of factor level for scheduling material handling problem .... 45
Table 4-1-11:32 Full-factorial results for scheduling material handling problem ....... 45
Table 4-1-12:The best parameters of the scheduling material handling problem ....... 46
Table 4-1-13:The best parameters of the no buffer and one transporter case ............. 47
Table 4-1-14:The experiment results of the no buffer and one transporter case ......... 47
Table 4-1-15:The best parameters for schedule with deadlock and re-entrant............ 48
Table 4-1-16:The experiment results for schedule with deadlock and re-entrant ....... 48
Table 4-2-1:The several different lot sizes cases......................................................... 49
Table 4-2-2:Definition of factor level for multiple lot and finite buffer sizes problem50
Table 4-2-3:Experiment results of multiple lot and finite buffer sizes problem ......... 51
Table 4-2-4:Response table of multiple lot and finite buffer sizes problem ............... 52
Table 4-2-5:Analysis of variance for multiple lot and finite buffer sizes problem ..... 53
Table 4-2-6:Definition of factor level for multiple lot and finite buffer sizes problem54
Table 4-2-7:32 Full-factorial results for multiple lot and finite buffer sizes problem . 54
Table 4-2-8:The best parameters of multiple lot and finite buffer sizes problem ....... 55
Table 4-2-9:The best parameters of no buffer case ..................................................... 56
Table 4-2-10:The experiment results of no buffer case............................................... 56
Table 4-2-11:The best parameters of several different lot sizes case.......................... 57
Table 4-2-12:The experiment results of several different lot sizes case ..................... 57
viii
List of Figures
Figure 2-5-1:Flowchart of Genetic Algorithm ............................................................ 13
Figure 3-1-1:The schema of the cluster tool................................................................ 16
Figure 3-2-1:The steps of the flexible process ............................................................ 19
Figure 3-2-2:A schedule with deadlock state .............................................................. 20
Figure 3-2-3:The schedule with deadlock state ........................................................... 22
Figure 3-2-4:The schedule with circular wait state ..................................................... 23
Figure 3-3-1:Flowchart of MOEA............................................................................... 24
Figure 3-3-2:The operations of the jobs and the corresponding chambers
(a) for job 1, (b) for job 2, (c) for job 3 .................................................. 26
Figure 3-3-3:The processing time of jobs on chamber 2 (indicated by arrow) ........... 27
Figure 3-3-4:The chromosome of an order for lot sizes is three ................................. 27
Figure 3-3-5:Definitions of the variables and symbols ............................................... 28
Figure 3-3-6:An example of the mutation operation ................................................... 31
Figure 3-3-7:An example of diversity strategy with material handling considered .... 32
Figure 3-3-8:The example of diversity strategy for several different lot sizes............ 33
Figure 3-3-9:The example of the variance of gene...................................................... 34
Figure 4-1-1:The configuration of an automated manufacturing system .................... 38
Figure 4-1-2:Response plot of scheduling material handling problem ....................... 43
Figure 4-1-3:The best convergence curve of scheduling material handling problem . 46
Figure 4-2-1:Response plot of multiple lot and finite buffer sizes problem................ 52
Figure 4-2-2:The best convergence curve of multiple lot and finite buffer sizes
problem................................................................................................... 55
Reference
[1] W. J. Lu, 2001, The Monitoring System for a Cluster Tool in Semiconductor,
Department of Mechanical Engineering, National Taiwan University of Science
and Technology, Master Thesis.
[2] W. H. Chen, 2002, Reliability of Cluster Tools in Semiconductor Production
Equipment, Department of Mechanical Engineering, National Chiao Tung
University, Master Thesis.
[3] T. Murata, 1989, “Petri Nets: Properties, Analysis and Applications”, Proc. of the
IEEE, vol. 77, No. 4, pp. 541-580.
[4] H. H. Xiong and M. C. Zhou, 1997, “Deadlock-free Scheduling of an Automated
Manufacturing System Based on Petri nets”, Proc. of the IEEE Int. Conf. Robotics
and Automation, vol. 2, New Mexico, pp. 945-950.
[5] D. S. Chang, 2002, Real-Time Search for Optimal Scheduling of Cluster Tool,
Department of Mechanical Engineering, National Chiao Tung University, Master
Thesis.
[6] M. P. Fanti, 2002, “A Deadlock Avoidance Strategy for Systems Modeled by
Coloured Petri Nets,” Proc. of the IEEE Sixth International Workshop, Discrete
Event Systems, pp. 61-66.
[7] J. H. Holland, 1975, “Adaptation in Natural and Artificial Systems”, Ann Arbor:
University of Michigan Press.
[8] D. E. Goldberg, 1989, Genetic Algorithms in Search Optimization and Machine
Learning, Addison-Wesley, Massachusetts.
66
[9] X. Gang and Z. Wu, 2002, “A kind of deadlock-free scheduling method based on
Petri net,” Proc. of the 7th IEEE International Symposium, High Assurance
Systems Engineering, pp. 195-200.
[10] H. W. Yuan, 1999, Modeling, Scheduling, and Prediction in Wafer Fabrication
Systems Using Queueing Petri Net and Genetic Algorithm, Department of
Computer Science and Engineering, National Taiwan University, Master Thesis.
[11] C. J. Kuo, 2004, Applications of Coloured Petri Net and Genetic Algorithms to
Cluster Tool Scheduling, Department of Mechanical and Automation Engineering,
National Kaohsiung First University of Science and Technology, Master Thesis.
[12] Michael Pinedo, 1995, Scheduling: theory, algorithms, and systems, pp. 19-21,
Prentice-Hall, New Jersey.
[13] Vladimir Zakian and T. K. Liu, 2005, Control Systems Design: A New
Framework, pp. 231-248, Springer Verlag, London.
[14] T. K. Liu, 1997, Application of Multiobjective Genetic Algorithm to Control
System Design, National Tohoku University, Ph. D.
[15] Hwang C. and K. Yoon, 1981 Multiple Attribute Decision Making: Methods and
Applications, Springer-Verlage, Berlin.
[16] Y. Sawaragi, H. Nakayama, and T. Tanino, 1985, “Theory of Multiobjective
Optimization”, Tokyo: Academic Press.
[17] V. Zakian and U. Al-Naib, 1973, “Design of Dynamical and Control Systems by
the Method of Inequalities,” Proceedings of IEE, vol. 120, no. 11, pp. 1421-1427.
67
[18] J. D. Schaffer, 1985, “Multiple Objective Optimization with Vector Evaluated
Genetic Algorithms,” Proc. of the first International Conference on Genetic
Algorithms and Their Applications, Lawrence Erlbaum, pp. 93-100.
[19] C. M. Fonseca and P. J. Fleming, 1993, “Genetic algorithms for multiobjective
optimization: formulation, discussion, and generalization”, Proc. of the fifth
International Conference on Genetic Algorithms, San Mateo, pp. 416-423.
[20] N. Srinivas and K. Deb, 1995, “Multiobjective Optimization Using
Nondominated Sorting in Genetic Algorithms”, Evolutionary Computation, vol. 2,
no. 3, pp. 221-248.
[21] T. K. Liu, T. Satoh, T. Ishihara, and H. Inooka, 1994, “An Application of
Multiobjective Genetic Algorithms to Control System Design”, Proc. of the first
Asian Control Conference, Tokyo, pp. 701-704.
[22] K. Kristinsson and G. A. Dumont, 1992, “System Identification and Control using
Genetic Algorithms,” IEEE Transactions on Systems, Man, and Cybernetics, Vol.
22, no. 5, pp. 1033-1046.
[23] J. Y. Tzeng, T. K. Liu, and J. H. Chou, 2006, ”Applications of Multi-objective
Evolutionary Algorithms to Cluster Tool Scheduling”, Proc. of the first
International conference on Innovative Computing, Information and Control,
Beijing, (Accepted).
[24] M. Gen and R. Cheng, 1997, Genetic Algorithms and Engineering Design, John
Wiley and Sons, New York.
[25] M. Pinedo, 2002, Scheduling Theory, Algorithms, and Systems, pp. 14-19, 2nd ed.
Prentice Hall, New Jersey.
68
[26] T. K. Liu, J. T. Tsai, and J. H. Chou, 2006, “Improved genetic algorithm for the
job-shop scheduling problem,” International Journal of Advanced Manufacturing
Technology Vol. 27, no. 9-10, pp. 1021-1029.
[27] Bazaraa, M., J. Jarvis, and H. Sherali, 1990, Linear Programming and Network
Flows, John Wiley and Sons, New York.
[28] C. H. Lai, 2005, Applications of Intelligent Taguchi Genetic Algorithm to Solve
Scheduling Problems, Department of Mechanical and Automation Engineering,
National Kaohsiung First University of Science and Technology, Master Thesis.
[29] Chou, J. H., W. H. Liao and J. J. Li, 1998, “Application of Taguchi-Genetic
Method to Design Optimal Grey-Fuzzy Controller of a Constant Turning Force
System”, Proc. of the 15th CSME Annual Conference, Taiwan, pp. 31-38.
[30] M. S. Phadke, 1989, Quality Engineering Using Robust Design, Prentice-Hall,
New Jersey.
[31] P. J. Ross, 1989, Taguchi Techniques for Quality Engineering, McGraw-Hill,
Singapore.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top