傅立成臺灣大學：資訊工程學研究所鄭興宏Cheng, Hsing HungHsing HungCheng2007-11-262018-07-052007-11-262018-07-052004http://ntur.lib.ntu.edu.tw//handle/246246/54034在組裝工業中，由於有組裝的動作、先後次序的關系、半成品完成的時間不相同，再加上太多不可預測的影響因素，所以很難找到一種兼顧準確性和變動性的方式來預測。然而，一個準確且能夠快速反應的預測器，不但可以提供顧客是否下單的依據，同時也可以提供系統管理者正確的資訊，以衡量廠區的生產效能。一個有效的排程策略不但可以使組裝工廠可以有較高的機台使用率、客戶達交率、與生產效能，同時也可以縮短待測品的等待時間，將廠中的待測品數量維持在一固定的水平以下，以提高獲利的機會。 在這篇論文中，為了在組裝工業去獲得更好的排程我們提出了一個新的派工策略和一個新的排序策略。而這兩個所提出的策略，我們考慮了靜態的廠內資訊 (像是處理時間、達交時間等)；也考慮了動態的廠內資訊(像是剩餘的處理時間、機台佇列的長度等)。另外，我們使用一個圖形化和數學的模形工具 -- 具有時間和顏色屬性的斐式網路去建構廠內排程的流程。此外，我們應用基因演算幫助在這樣的排程機制下去獲得近似最佳化的解。本篇論文致力於發展一套系統化的模型建構方法，配合此模式，以具有時間和顏色屬性的斐式網路為基礎開發高效率的預測器及排程器，為組裝工業廠建構出一系統化的生產模型。如此一來，此建構模型不但可以模擬產品的流程，更可提供快速的及時反應和效能評估。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 77454347 bytesapplication/pdfen-US基因演算法斐氏網路分派法則製造排程組裝工業Petri NetSequencing RuleAssemblySchedulingGADispatching Rulethesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/54034/1/ntu-93-R91922105-1.pdf