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

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:鄭興宏
研究生(外文):Hsing Hung Cheng
論文名稱:應用斐氏網路與遺傳基因演算法於組裝工業
論文名稱(外文):Petri Net Modeling and GA Based Scheduling for Assembly Industry
指導教授:傅立成傅立成引用關係
指導教授(外文):Li Chen Fu
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:資訊工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2004
畢業學年度:92
語文別:英文
論文頁數:83
中文關鍵詞:基因演算法斐氏網路分派法則製造排程組裝工業
外文關鍵詞:Petri NetSequencing RuleAssemblySchedulingGADispatching Rule
相關次數:
  • 被引用被引用:0
  • 點閱點閱:78
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
在組裝工業中,由於有組裝的動作、先後次序的關系、半成品完成的時間不相同,再加上太多不可預測的影響因素,所以很難找到一種兼顧準確性和變動性的方式來預測。然而,一個準確且能夠快速反應的預測器,不但可以提供顧客是否下單的依據,同時也可以提供系統管理者正確的資訊,以衡量廠區的生產效能。一個有效的排程策略不但可以使組裝工廠可以有較高的機台使用率、客戶達交率、與生產效能,同時也可以縮短待測品的等待時間,將廠中的待測品數量維持在一固定的水平以下,以提高獲利的機會。
在這篇論文中,為了在組裝工業去獲得更好的排程我們提出了一個新的派工策略和一個新的排序策略。而這兩個所提出的策略,我們考慮了靜態的廠內資訊 (像是處理時間、達交時間等);也考慮了動態的廠內資訊(像是剩餘的處理時間、機台佇列的長度等)。另外,我們使用一個圖形化和數學的模形工具 -- 具有時間和顏色屬性的斐式網路去建構廠內排程的流程。此外,我們應用基因演算幫助在這樣的排程機制下去獲得近似最佳化的解。本篇論文致力於發展一套系統化的模型建構方法,配合此模式,以具有時間和顏色屬性的斐式網路為基礎開發高效率的預測器及排程器,為組裝工業廠建構出一系統化的生產模型。如此一來,此建構模型不但可以模擬產品的流程,更可提供快速的及時反應和效能評估。
In this thesis, we propose a new dispatching rule and a new sequencing rule for assembly industry in order to obtain a better overall schedule. In addition, we use a graphical and mathematical modeling tool – Colored-Timed Petri Nets (CTPN) to model the scheduling flow in an assembly plant. By use of the proposed CTPN model, we can simulate the production under some scheduling policies. Moreover, we apply Genetic Algorithm (GA) to help the underlying scheduling mechanism to obtain a near-optimal solution.
In the scheduling phase, two effective rules have been proposed in addition to usage of a number of well-known methods. For the better ones, some use static information (such as setup time, processing time, due date, etc…), whereas others use dynamic information (such as remaining processing time, queue length, equipment workload, etc …). However, the aforementioned two proposed rules consider both static and dynamic information. Both set of rules together are proposed to construct the schedule. Generally speaking, these rules hold two viewpoints, namely, one is to select equipments for work order (WO) and another is to select (work order) WO for equipment.
Given such mechanism, we further apply genetic algorithm (GA) based approach to search for the optimal combination of the set of rules. Our approach can be considered as taking the advantage of obtaining the next fittest WO selection when the current WO finishes its assembly operation. The hereby proposed approach not only can increase the solution space but also can help us to locate a satisfactory solution. Besides that, the CTPN based GA scheduler takes less computation time than a lot of other schedulers, so that the present scheduler can meet the need for a rapidly changing environment.
Chapter 1 Introduction 1
1.1 Motivation 1
1.2 Literature Survey 3
1.3 Contribution 5
1.4 Organization 6
Chapter 2 Assembly Industry Environment 8
2.1 Overview of Assembly Industry 8
2.1.1 Assembly Industry 8
2.1.2 Assembly Constraints 10
2.2 Role of a Scheduler 12
2.3 Problem Formulation 13
Chapter 3 Modeling for Assembly Industry 18
3.1 Modeling 18
3.2 Overview of Petri Net (PN) 20
3.3 Assembly Industry Modeling 23
3.3.1 Route Module 25
3.3.2 Capability Module 26
3.3.3 Equipment Module 28
3.4 Summary 30
Chapter 4 Scheduling in Assembly Industry 31
4.1 Overview of the solutions 31
4.1.1 Problem of Scheduling 31
4.1.2 Dispatching Rule 33
4.1.3 Sequencing Rule 35
4.2 Overview of the Genetic Algorithm 47
4.3 GA Based Scheduling 51
4.3.1 Mixed Rules 54
4.3.2 Chromosome Representation 58
4.3.3 Fitness Function 60
4.3.4 Genetic Operators 63
4.3.5 Schedule Builder 64
4.4 Summary 66
Chapter 5 Experiment Result 68
5.1 Experiment Environment 68
5.2 Implementation 69
5.3 Experiment Results 70
5.3.1 Compared Method 70
Chapter 6 Conclusion 74
Reference 77
[1]Marath K. Reeja and Chandrasekharan Rajendran, "Dispatching rules for scheduling in assembly jobshops - Part 1," International Journal of Production Research, vol.38, no.9, pp.2051-2066, 2000.
[2]Marath K. Reeja and Chandrasekharan Rajendran, "Dispatching rules for scheudling in assembly jobshops - Part 2," International Journal of Production Research, vol.38, no.10, pp.2349-2360, 2000.
[3]Nabil R. Adam, J. Will M. Bertrand, Diane C. Morehead and Julius Surkis, "Priority assignment procedures in multi-level assembly jobshops," IIE Transactions, vol.19, pp.317-328, 1987.
[4]Nabil R. Adam, J. Will M. Bertrand and Julius Surkis, "Due date assignmentprocedures with dynamically updated coecients for multi-level assembly jobshops," European Journal of Operational Research, vol.68, pp.212-227, 1993.
[5]Patrick R. Philipoom, Roberta S. Russell and Timothy D. Fry, "A preliminary investigation of multiattribute based sequencing rules for assembly shops," International Journal of Production Research, vol.29, pp.739-753, 1991.
[6]C. H. Smith, E. D. Minor and H. J. Wen, "Regression-based due date assignment rules for improved assembly shop performance," International Journal of Production Research, vol.33, pp.2375-2385, 1995.
[7]Dominic Sculli, "Priority dispatching rules in jobshops with assembly operations and random delays," OMEGA, vol.8, pp.227-234, 1980.
[8]Jack S. Goodwin and James C. Goodwin, "Operating policies for scheduling assembled products," Decision Sciences, vol.13, pp.585-603, 1982.
[9]R. W. Conway, W. L. Maxwell and L. W. Miller, "Theory of Scheduling," Addison Wesley, 1967.
[10]Mikell P. Groover, "Automation, Production Systems, and Computer-Integrated Manufacturing," Prentice-Hall, INC, 1987.
[11]Geoffrey Boothroyd and George E. Dieter, "Assembly Automation and Product Design," Marcel Dekker, INC, 1992.
[12]David Goldberg, "Genetic Algorithm in Search, Optimization and Machine Learning," Addison-Wesley, 1989.
[13]T. Murata, H. Ishibuchi, and H. Tanaka, “Multi-Objective Genetic Algorithm and Its Applications to Flowshop Scheduling,” Computers and Industrial Engineering, vol. 30, no. 4, pp. 957-968, 1996..
[14]R. S. Lee, and M. J. Shaw, “A Genetic Algorithm-Based Approach to Flexible Flow-Line Scheduling with Variable Lot Sizes”, IEEE Transactions on Systems, Man, Cybernetics—Part B: Cybernetics, vol. 27, no. 1, pp. 36-54, 1997.
[15]R. Sikora, “A Genetic Algorithm for Integrating Lot-Sizing and Sequencing in Scheduling a Capacitated Flow Line,” Computers and Industrial Engineering, vol. 30, no. 4, pp. 969-981, 1996.
[16]R. Cheng, M. Gen, and Y. Tsujimura, “A Tutorial Survey of Job-Shop Scheduling Problems Using Genetic Algorithm, Part I: Representation,” Computers and Industrial Engineering, vol. 30, no. 4, pp. 983-997, 1996.
[17]C. Y. Lee, S. Piramuthu, and Y. K. Tsai, “Job Shop Scheduling with a genetic algothm and machine learning”, International Journal of Production Research, vol. 35, no. 4, pp. 1171-1191, 1997.
[18]K. Krishna, K. Ganeshan, and D.J. Ram, “Distributed Simulated Annealing Algorithms for Job Shop Scheduling,” IEEE Transaction on Systems, Man, and Cybernetics, Vol. 25, No. 7, pp. 1102-1109, July 1995.
[19]Deroussi, L.; Gourgand, M.; Tchernev, N., “Coupling Local Search Methods and Simulated Annealing to the Job Shop Scheduling Problem with Transportation,” Emerging Technologies and Factory Automation, 2001. Proceedings. 2001 8th IEEE International Conference, Vol. 1, pp. 659-667, 2001.
[20]Dahal, K.P.; Burt, G.M.; McDonald, J.R.; Galloway, S.J.; “GA/SA-Based Hybrid Techniques for the Scheduling of Generator Maintenance in Power Systems,” Evolutionary Computation, 2000. Proceedings of the 2000, Vol. 1, pp. 567-574, 2000.
[21]Peter J. M. Van Laarhoven, Emile H. L. Aarts, and Jan Karel Lenstra, “Job Shop Scheduling by Simulated Annealing,” Operations Research, Vol. 40, No. 1, January-February, 1992.
[22]K.W. Hansmann and M. Hoeck ,”Production Control of a Flexible Manufacturing System in a Job Shop Environment,” Int. Trans. Opl Res. Vol. 4, No. 5/6, pp. 341-351, 1997.
[23]L. Chwif, and R.J. Paul, “Simulation Optimization with the Linear Move and Exchange Move Optimization Algorithm,” Proceedings of the 1999 Winter Simulation Conference, pp. 806-810, 1999.
[24]A.H. Mantawy, Y.L. Abdel-Magid, and S.Z. Selim, “Integrating genetic Algorithms, Tabu Search, and Simulated Annealing for the Unit Commitment Problem,” IEEE Transactions on Power Systems, Vol. 14, No. 3, pp. 829-836, 1999.
[25]S. Oman, and P. Cunningham, “Using Case Retrieval to Seed Genetic Algorithms,” International Jouranl of Computational Intelligence and Applications, Vol. 1, No. 1, pp. 71-82, 2001.
[26]Imed Kacem, Slime Hammadi, and Pierre Borne, “Approach by Localization and Multiobjective Evolutionary Optimization for Flexible Job-Shop Scheduling Problems,” IEEE transactions on system, man, and cybernetics, Vol. 32, No.1, February 2002.
[27]Tadao Murata, "Petri Nets: Properties, Analysis and Application," Proceedings of the IEEE, Vol. 77, NO.4, April, 1989.
[28]A.A. Desrochers and R. Y. Al-Jaar, Applications of Petri Nets in Manufacturing Systems: Modeling, Control, and Performance Analysis, IEEE Press, New York, 1994.
[29]M. H. Lin and L. C. Fu, “Modeling, Analysis, Simulation, and Control of Semiconductor Manufacturing Systems: A Generalized Stochastic Colored-Timed Petri-Net Approach,” IEEE International Conference on Systems Man, and Cybernetics, 1999.
[30]J. Ezpeleta and J. M. Colom, “Automatic Synthesis of Colored Petri Nets for the Control of FMS,” IEEE Transactions on Robots and Automation, Vol. 13, No. 3, pp. 327-336, 1997.
[31]S. Y. Lin and H. P. Huang, “Modeling and Emulation of a Furnace in IC Fab Based on Colored-Timed Petri Net,” IEEE Transactions on Semiconductor Manufacturing, Vol. 11, No. 3, pp. 410-420, 1998.
[32]S. C. Huang, “Design of Colored Time Petri Net Based Simulation Modeling Environment,” Master Thesis, Department of Industrial Engineering & Engineer Management, National Tsing Hua University, 1996.
[33]I. Demongodin and N. T. Koussoulas, “Differential Petri Nets: Representing Continuous System in a Discrete-Event World,” IEEE Transactions on Automatic Control, Vol. 43, No. 4, pp. 573-579, 1998.
[34]R. Zurawski and M. C. Zhou, “Petri Nets and Industrial Applications: A Tutorial,” IEEE Transactions on Industrial Electronics, Vol. 41, No. 6, pp. 567-583, 1994.
[35]M. C. Zhou and M. D. Jeng, “Modeling, Analysis, Simulation, Scheduling, and Control of Semiconductor Manufacturing Systems: A Petri Net Approach,” IEEE Transactions on Semiconductor Manufacturing, Vol. 11, No. 3, pp. 333-357, 1998.
[36]M. Allam and H. Alla, “Modeling and Simulation of an Electronic Component Manufacturing System Using Hybrid Petri Nets,” IEEE Transactions on Semiconductor Manufacturing, Vol. 11, No. 3, pp. 374-383, 1998.
[37]M. D. Jeng, X. Xie, and S. W. Chou, “Modeling, Qualitative Analysis, and Performance Evaluation of the Etching Area in an IC Wafer Fabrication System Using Petri Nets,” IEEE Transactions on Semiconductor Manufacturing, Vol. 11, No. 3, pp. 358-373, 1998.
[38]S.Y. Lin, L.C. Fu, and T.C. Chiang, “Colored Timed Petri-Net and GA Based Approach to Modeling and Scheduling for Wafer Probe Center,” IEEE International Conference of Robotics and Automation, 2003.
[39]Y.S. Shen, L.C. Fu, and T.C. Chiang, “Adaptive Lot/Equipment Matching Strategy and GA Based Approach for Optimized Dispatching and Scheduling in a Wafer Probe Center,” IEEE International Conference of Robotics and Automation, 2004.
[40]T.C. Chiang and L.C. Fu, “Solving the FMS Scheduling Problem by Critical Ratio-Based Heuristics and the Genetic Algorithm,” IEEE International Conference of Robotics and Automation, 2004.
[41]Milad F. Sebaaly and Hideo Fujimoto, "A Genetic Planner for Assembly Automation," Evolutionary omputation, Proceedings of IEEE International Conference, 20-22, pp. 401 - 406, May, 1996
[42]Mu Der Jeng and Chung Shi Lin, "Scheduling Flexible Manufactruing Systems Containing Assembly Operations Baseed on Petri Net Structures and Dynamics," Proceedings of IEEE International Conference on Systems, Man, and Cybernetics, pp. 4430-4435, 1997.(Invited)
[43]A. Tharumarajah, R. Bemelman, P. Welgama, and A. Wells, "Distributed Scheduling of an Assembly Shop," IEEE International Conference, Vol.1, no.11-14, pp.433-438, Oct, 1998.
[44]C. Del Valle,M. Toro, E. F. Camacho, and R. M. Gasca, "A scheduling approach to assembly sequence planning," Proceedings of the IEEE International Symposium, pp. 103-108, 2003.
[45]T. Sawik, "Simultaneous versus Sequential Loading and Scheduling of Flexible Assembly Systems," International Journal of Production Research, Vol.38, no. 14, pp. 3267-3282, 2000.
[46]K. G. Shin and Q. Zheng, "Scheduling job operations in an automatic assembly line," Robotics and Automation, IEEE Transactions, Vol. 7, no.3, pp.333-341, June, 1991.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊