成功大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	黃文定 Huang, Wengding
論文名稱：	混合基因演算及資料探勘法求解平行機台自動搬運車之搬運排程 Hybriding genetic algorithm and data mining methods for The Handling Scheduling of Parallel Machine Automatic Guided Vehicle
指導教授：	利德江 Li, Der-Chiang
學位類別：	碩士 Master
系所名稱：	管理學院 - 工業與資訊管理學系碩士在職專班 Department of Industrial and Information Management (on the job class)
論文出版年：	2010
畢業學年度：	98
語文別：	中文
論文頁數：	52
中文關鍵詞：	TFT-LCD 、自動搬運車、平行機台、基因演算法、k-means分群法、決策樹
外文關鍵詞：	TFT-LCD, AGV, Parallel Machine, Genetic Algorithm, k-means, decision tree
相關次數：	點閱：88 下載：2
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

TFT-LCD（Thin-Film Transistor Liquid-Crystal Display）光電面板產業屬於高度資本密集的產業，所以如何保持設備在高產能利用率是相當重要的議題，而造成面板工廠生產設備閒置的常見原因之一，就是因工件搬運不及導致生產設備缺貨。本研究將平行機台的概念應用於自動搬運車排程(Scheduling)，先以K-Means分群法將案例中所有搬運需求進行分群，並以各種產品尺寸載具搬運順序為基因碼，總完成時間(Makespan)為目標函數，運用基因演算法(Genetic Algorithm)來求取案例中每一次搬運需求之近似最佳解，再以決策樹探勘搬運需求與搬運排程之對應規則，最後以統計方法Paired T，檢定測試資料與訓練資料無顯著差異，增加規則可信度。由於本研究之結果可快速求解近似最佳之搬運排程，故本研究所提出的方法在實務上可有效協助管理者執行搬運排程相關之作業，具實際應用價值。

Thin-Film Transistor Liquid-Crystal Display is the high level technology in the world, so it’s important that how the production machine keep high utility. One of the reason with lower utility is abnormal transfer with Automatic Guide Vehicle. To reduce the probability of the production machine idleness, this study proposed one solution with “Parallel Machine” concept for the Automatic Guide Vehicle, and help them finish all transfer demand in the shortest time.
In this study, the method is called “Hybriding genetic algorithm and data mining methods”. It includes three phases. In the phase one, we create many transfer demand for training sample and classify all of them by “k-means method”, then we can have golden training sample. In the phase two, we deal with them and testing sample by “genetic algorithm method”, and Makespan as the objective function. In the last phase, we use “decision tree” to find out the relation between transfer demand and standard scheduling. To prove the rule is useful, we use “Paired T-test” for the golden training sample and testing sample. The result is not significant so that the rule we mining is work.

目錄
摘要.......................................................I
Abstract .................................................II
致謝.................................................... III
目錄..................................................... IV
圖目錄...................................................VII
表目錄..................................................VIII

第一章 緒論............................................... 1
1.1 研究背景與動機........................................ 1
1.1.1 LCD製程簡介......................................... 2
1.1.2 自動化生產簡介...................................... 4
1.1.3 搬運問題簡介........................................ 4
1.2 研究目的.............................................. 5
1.3 研究範圍與限制........................................ 5
1.4 研究方法與步驟........................................ 6
第二章 文獻探討........................................... 8
2.1 自動化物料搬運系統(AMHS)相關研究...................... 8
2.2 派工法則與平行機台排程............................... 11
2.3 基因演算法........................................... 13
2.3.1 基因演算法之特點................................... 14
2.3.2 基因演算法之步驟................................... 15
2.4 資料探勘............................................. 22
2.4.1 資料探勘之功能..................................... 22
2.4.2 群集分析........................................... 23
2.4.3 決策樹............................................. 25
2.5 小結................................................. 25
第三章 研究方法.......................................... 27
3.1 問題描述與定義....................................... 27
3.2 K-means分群法之模式建構.............................. 29
3.2.1 K-means分群法...................................... 29
3.2.2 分群參考指標- Silhouette Coefficient .............. 29
3.3 基因演算法之模式建構................................. 30
3.3.1 模式符號說明....................................... 30
3.3.2 數學模式........................................... 31
3.3.3 基因演算法......................................... 31
3.4 決策樹............................................... 36
第四章 實證分析.......................................... 38
4.1 實作環境介紹與案例描述............................... 38
4.1.1 實作環境介紹....................................... 38
4.1.2 案例描述........................................... 38
4.2 K-means分群法與結果分析.............................. 39
4.3 基因演算法與結果分析................................. 40
4.3.1 參數設定........................................... 40
4.3.2 基因演算法......................................... 41
4.4 決策樹資料探勘與結果分析............................. 41
4.5 統計檢定............................................. 44
4.6 小結................................................. 47
第五章 結論與建議........................................ 48
5.1 結論................................................. 48
5.2 未來研究建議......................................... 49
參考文獻................................................. 50

圖目錄
圖1.1 TFT-LCD製造流程圖................................... 3
圖1.2 LCD製造流程圖....................................... 3
圖1.3 研究方法流程圖...................................... 7
圖2.1 基因演算法之基本流程............................... 16
圖2.2 單點交配法(One-Point Crossover).................... 19
圖2.4 部分配對交配(Partially Matched Crossover (PMX) Operator)................................................ 20
圖2.5 順序配對(Order Crossover (OX) Operator) ........... 20
圖2.6 SC(Silhouette Coefficient)指標參考標準............. 25
圖3.1 研究架構流程圖......................................28
圖3.2 本研究之基因演算法流程............................. 32
圖3.3 本研究之染色體編碼................................. 33
圖3.4 三個自動搬運車，六種產品載具，L設定為8之編碼範例... 33
圖4.1 SSE Trand Chart.................................... 40
圖4.2 平均側影係數(Silhouette Coefficient) .............. 40
圖4.3 Boxplot of Differences ............................ 45
圖4.4 Individual Value Plot of Differences .............. 46
圖4.5 Histogram of Differences .......................... 46

表目錄
表2.1 平行機台排程之相關文獻整理......................... 13
表4.1 各產品載具的單位搬運時間........................... 39
表4.2 案例產品組合....................................... 39
表4.3 代表性搬運排程與最快完工時間....................... 41
表4.4 測試資料對應之代表性排程與最短完工時間............. 44
表4.5 Paired T統計檢定................................... 45
                                    

宋志龍，『應用基因演算法於特用化學品工廠排程之研究』，國立成功大學工業與資訊管理研究所，碩士論文，民國96年。
Akturk, M. S., and Yilmaz, H., 1996, “Scheduling of automated guided vehicles in a decision making hierarchy,” International Journal of Production Research, 34(2),pp.577-591.
Bandyopadhyay, S. and Maulik, U., 2002, “An evolutionary technique based on K-Means algorithm for optimal clustering in RN”, Information Sciences, 146, pp.221-237.
Beasley, J. E., and Chu, P. C. , 1996 , “A genetic algorithm for the set overing problem.” European Journal of Operational Research, 94, pp.392-404.
Bo, Z. W., Hua, L. Z., and Yu, Z. G. , 2006 , “Optimization of process route by genetic algorithms.“ Robotics and Computer-Integrated Manufacturing, 22,pp.180-188.
Byung. H. J., and Sabah U. R., 2001, “A muti-attribute dispatching rule for automated guided vehicle systems,” International Journal of Production Research, 39(13), pp.2817-2832.
Chan, K. Y., Aydin, M. E., and Fogarty, T. C. , 2006 , “Main effect fine-tuning of the mutation operator and the neighbourhood function for uncapacitated facility location problems.” Soft Computing - A Fusion of Foundations, Methodologies and Applications, 10, pp.1075-1090.
Chen, R. S., Lu, K. Y., and Yu, S. C. , 2002 , ”A hybrid genetic algorithm approach on multi-objective of assembly planning problem.” Engineering Applications of Artificial Intelligence , 15, pp.447-457.
Deris, S., Omatu, S., Ohta, H., Shaharudin, K. L. C., and Samat, P.A. , 1999 , “Ship maintenance scheduling by genetic algorithm and constraint-based reasoning. “European Journal of Operational Research, 112, pp.489-502.
Egbelu, P. J. and Tanchoco, J. M. A., 1984, “Characterization of automatic guided vehicle dispatching rules,” International Journal of Production Research, 22(3),pp.359-374.
Fishwick, R. J., Liu X. L., and Begg, D. W. , 2000 , “Adaptive search in discrete limit analysis problems.” Computer Methods in Applied Mechanics and Engineering, 189, pp.931-942.
Gen, M., and Cheng, R. , 1997 , “Foundations of Genetic Algorithms, Genetic Algorithms & Engineering Design. ” New York : John Wiley & Sons, Inc.
Goldberg, D. , 1989, ”Genetic algorithms in search, optimization and machine learning.” Boston : Addison-Wesly.
Goldberg, D., and Lingle, R. , 1985, “Alleles, loci, and the traveling salesman problem.” Proceedings of International conference on Genetic Algorithms and Their Applications, pp.154-159.
Han, J., and Kamber, M., 2000, “Data Mining: Concepts and Techniques,” Morgan Kaufmann.
Haupt, R., 1989 , “A survey of priority rule-based scheduling,” OR Spectrum, 11, pp.3-16.
Holland, J. H., 1975, “Adaptation in Nature and Artificial Systems,” Ann Arbor: University of Michigan Press.
Kaufman,L., Rousseeuw, P.J., 1990 , “Finding froups in data: an introduction to cluster analysis,”NY: John Wiley & Sons, Inc.
Kwok, Y. K., and Ahmad, I. , 1997 , “Efficient scheduling of arbitrary task graphs to multiprocessors using a parallel genetic algorithm.” Journal of Parallel and Distributed Computing, 47, pp.58-77.
Leung, J. Y. T., and Pinedo, M., 2003 ,“Minimizing total completion time on parallel machines with deadline constraints.” SIAM JOURNAL ON COMPUTING, 32(5), pp.1370-1388.
Mitchell, M. , 1998 , “Davis, L.D, Handbook of genetic algorithms.” Artificial Intelligence, 100, pp.325-330.
Pinedo, M., 1995, “Scheduling theory, algorithm, and systems.” New Jersey :Prentice Hall.
Quinlan,J.R., 1979, “Discovering rules from large collections of examples:a case study.” In Michie, D., editor , Expert System in the Microelectronic Age. Edinburgh Scotland: Edinburgh University Press.
Quinlan,J.R., 1993, “C4.5:Programs for Machine Learning.” San Mateo CA :Morgan Kaufmann.
Selim, S.Z. and Ismail, M.A. , 1984,“K-means-type algorithms: A generalized convergence theorem and characterization of local optimality”, IEEE Transactions on Pattern Analysis and Machine Intelligence, 6(1), pp.81-87.
Tou, J.T. and Gonzalez, R.C., 1974,.“ Pattern Recognition Principles ”, Addison-Wesley, Reading, MA.
Tseng, H.-E. , 2006 , ”Guided genetic algorithms for solving a larger constraint assembly problem.” International Journal of Production Research, 44(3), pp.601-625.
Wang, P. T., Wang, G. S., and Hu, Z. G. , 1997 , “Speeding up the search process of genetic algorithm by fuzzy logic.” Proceeding of the Fifth European Congress on Intelligent Techniques and Soft Computing, pp.665-671.
Yun, Y. S. , 2002, “Genetic algorithm with fuzzy logic controller for preemptive and non-preemptive job-shop scheduling problems.” Computers & Industrial Engineering, 43, pp.623-644.

校內：2013-01-01公開
校外：不公開電子論文尚未授權公開，紙本請查館藏目錄

簡易檢索 / 詳目顯示

相關論文