進階搜尋

 
查詢範圍:「   」
顯示範圍:第筆 論文書目資料
顯示格式:全部欄位
共 8 筆
------------------------------------------------------------------------ 第 1 筆 ---------------------------------------------------------------------
系統識別號 U0026-0707201016274600
論文名稱(中文) 限制理論於印刷電路板生產排程之運用-以E公司為例
論文名稱(英文) The Application of TOC on Production-Scheduling of PCB Industry – A Case Study of E Company
校院名稱 成功大學
系所名稱(中) 工學院工程管理碩士在職專班
系所名稱(英) Institute of Engineering Management
學年度 98
學期 2
出版年 99
研究生(中文) 曾煥捷
學號 n0796120
學位類別 碩士
語文別 中文
口試日期 2010-06-14
論文頁數 87頁
口試委員 指導教授-陳澤生
口試委員-王榮泰
口試委員-王育民
口試委員-石孟勳
口試委員-楊開南
關鍵字(中) 印刷電路板
限制理論
生產排程
鼓–緩衝–繩
關鍵字(英) Printed Circuit Board
Theory of Constrains
Production Scheduling
Drum-Buffer-Rope
學科別分類
中文摘要 印刷電路板 (Printed Circuit Board, PCB) 在電子產業供應鏈中屬於不可或缺的一環,因其功能主要在於提供電子零組件安裝與互連時的主要支撐體,而在經歷 2008 年的金融海嘯風暴後,使得產業外在環境產生劇烈之變化,因此為了企業的永續發展,各同業無不以符合客戶需求標準 (品質、交期…等) 當作營運之最高準則,而在這個準則下,如何發揮工廠的最高效率進而降低成本成為首要之課題。
本研究嘗試以限制理論 (Theory of Constrains, TOC) 為基礎,並以最大產出為績效指標,再搭配上印刷電路板廠作為實例來進行生產排程之實驗研究,本研究在實驗階段一是以限制理論之「鼓–緩衝–繩」(Drum-Buffer-Rope, DBR) 排程規則來針對某印刷電路板廠作改良,修改其生產排程派工之順序,並與其目前現行之 EDD 排程規則來作為比較,而實驗階段二則是以限制理論如何持續改善為概念如何繼續提昇系統效能來進行分析研究。
經過本研究之實驗證實 DBR 排程規則其模擬結果,不管在完成時間、平均流程間及限制產能資源工作佔之稼動比率…等績效指標均優於 EDD 排程規則,進而增加 PCB 廠之有效產出,並藉由實驗結果提出相關結論與建議,以提供 PCB 廠於生產排程作業時、日後擴建產能或是建置新廠時之參考。
英文摘要 Printed Circuit Board (PCB) plays an essential role in the electronic industry supply chain, since it functions as the major support in the installment and mutual connections between electronic components. After the global financial crisis that hit the world in 2008, the external industry environment has been became fierce change. All of electronic industries faced to pay more attention to the customer requirement standards for their future operation of sustainability, such as product quality and delivery date. Under the criterion, the issues of how to trigger the most efficiency of factories with the lower production cost comes into the first priority.
The Theory Of Constrains (TOC) was tried to apply to simulate a maximum output for the production performance target in an electronic factory. The selected E Company with producing PCB components is a case study. The experimental researches were run for various production schedules. Firstly, the Drum-Buffer- Rope (DBR) scheduling was used to improve the current scheduling. A comparision result was also obtained with the existing Earliest Due Date (EDD) scheduling. Secondly, we used the TOC to analyze how the production system performance can be improved and promoted for the case study.
It was clarified from the results of the simulation experiment in the study. We found that the DBR scheduling is better than the EDD scheduling on the dimensions of completion time, average flow time and overall equipment effectiveness. The conclusions can be referred to the PCB industries in their production scheduling, capacity enlargement as well as the new plants establishment in the future.
論文目次 摘要 I
Abstract II
誌謝 III
目錄 IV
表目錄 VII
圖目錄 IX
中英文縮寫對照 XI
第1章 緒論 1
1-1 研究背景與動機 1
1-2 研究目的 3
1-3 研究範圍與限制 4
1-4 研究步驟與架構 5
第2章 文獻探討 7
2-1 印刷電路板產業與相關文獻 7
2-1-1 印刷電路板發展 7
2-1-2 印刷電路板之生產排程 12
2-2 限制理論 14
2-2-1 限制理論簡介 14
2-2-2 限制理論的步驟 15
2-2-3 限制驅導式排程 19
2-2-4 限制理論之應用 22
2-3 生產排程 24
2-3-1 生產排程分類 24
2-3-2 生產排程相關文獻 27
第3章 研究方法 30
3-1 PCB 生產製造流程 30
3-2 建構生產系統產出鏈圖 35
3-3 DBR 排程法 36
3-3-1 確認系統 CCR 37
3-3-2 緩衝時間設定 38
3-3-3 CCR 排程建立 39
3-3-4 決定投料時間 45
3-4 非 CCR 排程規劃 45
3-5 排程軟體系統介紹及功能 46
第4章 研究結果與分析 52
4-1 研究假設 52
4-2 PCB 生產系統之架構建立 52
4-2-1 產品加工與製程設備資訊 52
4-2-2 確認系統限制資源 54
4-2-3 緩衝時間設定 57
4-3 實驗階段一結果比較分析 58
4-3-1 E 公司 EDD 之排程實驗 62
4-3-2 本研究 DBR 之排程實驗 64
4-3-3 排程實驗結果比較分析 65
4-4 實驗階段二結果比較分析 69
4-4-1 新增 CCR 機台設備之排程實驗 69
4-4-2 排程實驗結果比較分析 71
第5章 結論與建議 77
5-1 研究結論 77
5-2 後續研究建議 79
參考文獻 80
附錄 A-1 E 公司 G 產品之連續十二個月需求彙整表 83
附錄 A-2 E 公司 H 產品之連續十二個月需求彙整表 84
附錄 A-3 E 公司 P 產品之連續十二個月需求彙整表 85
附錄 A-4 E 公司 W 產品之連續十二個月需求彙整表 86
參考文獻 1. Allahverdi, A. & Mittenthal, J., “Scheduling On M parallel machines subject to random breakdowns to minimize expected mean flow time”, Naval Research Logistic, 41(5), 1994
2. Chase, R.B., Aquilano, N.J. & Jacobs, F.R., “Production and Operations Management-manufacturing and service (8th Edition)”, McGraw-Hill Company, New York, 1998.
3. Kim, Y. et al., “Search heuristics for a flow shop scheduling problem in a printed circuit board assembly process,” European Journal of Operational Research, Vol. 91, 1996.
4. Lambert, Serge, Cyr Bernard, Abdul Nour Georges, Drolet Jocelyn, “Comparsion Study of Scheduling Rules and Set-up Policies for a SMT Production Lin”, Computers & Industrial Engineering, 1997.
5. Leung, J.Y.T., Li, H., Pinedo, M.L. & Zhang, J., “Minimizing total weighted completion time when scheduling order in a flexible environment with uniform machines, Information Processing Letters”, 103(3), 2007
6. Lin, F. and Shaw, M.J., “Scheduling printed circuit board production systems using the two-level scheduling approach,” Journal of Manufacturing Systems, Vol.16, 1997.
7. Lim, J.M., “A genetic algorithm for a single hoist scheduling in the printed-circuit-board electroplating line,” Computers & Industrial Engineering, Vol.33, 1997.
8. Pinedo, M.L., “Scheduling:Theory, Algorithms, and Systems (3rd Edition)”, Springer, New York, 2008
9. Ruiz-Torres, A.J., Lopez, F.J. & Ho, J.C., “Scheduling uniform parallel machines subject to a secondary resource to minimize the number of today jobs, European Journal of Operational Research”, 179(2), 2007
10. Shakhlevich, N.V. & Strusevich, V.A., “Preemptive scheduling on uniform parallel machines with controllable job process time, Algorithmic”, 51(4), 2008
11. 王立志,「系統化運籌與供應鏈管理」,滄海書局,台中市,1999
12. 王彥文,「印刷電路板鑽孔作業生產排程之研究」,私立元智大學碩士論文,2001
13. 王相弼,「DBR模式在記憶體晶圓針測廠之應用」,國立交通大學碩士論文,2007
14. 王銘祿,「限制理論之有效產出運用於成本管制之探討」,私立逢甲大學碩士論文,2006
15. 吳玉琦,「先進規劃與排程系統應用於印刷電路板產業之研究」,私立東海大學碩士論文,2004
16. 吳鴻輝、李榮貴,「限制驅導式現場排程與管理技術」,二版,全華科技圖書股份有限公司,台北縣,2007
17. 呂泰福,「應用拉式供應鏈管理降低面板庫存之研究 -以HannStar公司為例」,國立成功大學碩士論文,2008
18. 李榮貴、張盛鴻,「TOC 限制理論 - 從有限走到無限」,中國生產力中心,2005
19. 汪家平,「以限制理論為基礎建構安防產業知識缺口診斷程序」,國立臺灣科技大學碩士論文,2008
20. 林定皓,「多層與高密度電路板全覽」,亞洲智識科技有限公司,桃園市,2002
21. 林定皓,「印刷電路板概論‧養成篇」,台灣電路板協會,桃園市,2005
22. 徐烈昭,「應用塔布搜尋法於非等效平行機台之研究-以PCB鑽孔為例」,私立元智大學碩士論文,2001
23. 高德拉特 (Eliyahu Goldratt),齊若蘭譯,「目標 - 簡單而有效的常識管理」,天下文化,2002
24. 張喬齡,「TOC 式扣件生產系統之模擬實例研究」,國立成功大學碩士論文,2004
25. 郭建男,「基因演算法應用於面板產業 Cell 製程後段排程之研究 – 以 H 公司為例」,國立成功大學碩士論文,2009
26. 陳嶽漢,「TOC式煉鋼生產系統模擬實例研究」,國立成功大學碩士論文,2009
27. 曾盈慈,「利用數學規劃及啟發式演算法求解等效平行機台之排程規劃研究」,國立成功大學碩士論文,2009
28. 湯璟聖,「動態彈性平行機群排程的探討」,私立中原大學碩士論文,2003
29. 黃萱懿,「印刷電路板工廠現場排程之研究」,國立政治大學碩士論文,2003
30. 工研院,http://ieknet.itri.org.tw/,2010/03
31. 鼎誠資訊股份有限公司,http://www.digichain.com.tw/,2010/03

------------------------------------------------------------------------ 第 2 筆 ---------------------------------------------------------------------
系統識別號 U0026-0812200910200675
論文名稱(中文) 以電子化供應鏈主生產排程系統 降低前置時間之研究
論文名稱(英文) none
校院名稱 成功大學
系所名稱(中) 工業管理科學系碩博士班
系所名稱(英) Department of Industrial Management Science
學年度 90
學期 2
出版年 91
研究生(中文) 鄭漢中
學號 r3688112
學位類別 碩士
語文別 中文
口試日期 2001-07-19
論文頁數 129頁
口試委員 指導教授-呂執中
口試委員-梁文耀
口試委員-陸行
口試委員-張秀雲
關鍵字(中) 供應鏈管理,主生產排程,前置時間
關鍵字(英) none
學科別分類
中文摘要 企業界常利用生產規劃來安排各產品群組之生產計劃,之後再利用主生產排程來處理個別產品之訂單的安排、製造與外包及生產控制。由於顧客下訂單到產品送至顧客手上有一段滿長的前置時間,而且較短的前置時間可以改善顧客滿意度、使存貨量減少,所以很多公司都把生管改善之焦點放在前置時間之縮短上。由於電子化供應鏈環境的形成,企業中之生產流程也比以往更加的多變複雜,這使得傳統之生產排程系統很難在有限時間內對客戶訂單及生產資源作有效的處理及安排,造成整個前置時間可能變長,但是也提供一個機會讓企業重新建立主排程系統來因應電子化供應鏈環境,並且以前置時間的縮短來獲得競爭優勢和市場佔有率,也是值得深入探討之課題。
本研究提出一個電子化供應鏈主排程系統及流程上的改變之方法來支持企業和顧客之間是以Web-based的方式做即時資訊交換及回應並且可以縮短規劃的前置時間,而且可利用此方法來改善企業主生產排程系統之效率與效能。研究中首先結合一些供應鏈管理的軟體模組及網路來建立一個電子化供應鏈環境,並分析此系統之輸出入的資料及流程,推導出合適的主排程模式來幫助企業縮短前置時間,再以一個前置時間評估模式來確定前置時間縮短的效果。之後並以一個案公司來評估其可行性,且討論所提出之電子化供應鏈主排程系統如何結合個案公司原本的生管系統,以及探討此系統對個案公司有何影響及效益。最後提出本研究的結論及未來研究方向。



英文摘要 none


論文目次 摘 要…………………………………………………………………………I
誌 謝……………………………………………………………………….II
目 錄………………………………………………………………………III
表目錄…………………………………………………………………………V
圖目錄……………………………………………………………………….VI
第一章 緒 論…………………………………………………………..1
第一節 研究動機…………………………………………………….1
第二節 研究目的…………………………………………………….2
第三節 研究範圍與限制…………………………………………….3
第四節 研究方法及流程…………………………………………….4
第二章 文 獻 探 討……………………………………………………...6
第一節 供應鏈管理………………………………………………….6
2-1-1 供應鏈管理的定義與重要性……………………………..6
2-1-2 供應鏈管理的作法與目的……………………………...12
2-1-3 電子化供應鏈…………………………………………...15
第二節 主生產排程系統…………………………………………..20
2-2-1 主生產排程的意義與重要性…………………………...20
2-1-2 主生產排程系統之衡量指標…………………………...23
2-2-3 訂單式生產及主生產排程其他相關文獻……………...28
第三節 前置時間…………………………………………………..33
2-3-1 前置時間的意義與重要性……………………………...33
2-3-2 前置時間評估方法……………………………………...36
2-3-3 前置時間其他相關文獻………………………………...40
第三章 研究方法與架構………………………………………………....42
第一節 企業環境………………………………………………....42
第二節 企業生產策略…………………………………………....45
第三節 整體架構…………………………………………………..47
第四節 電子化供應鏈主排程系統………………………………..53
3-4-1 建構流程………………………………………………...54
3-4-2 系統分析………………………………………………...56
3-4-3 模式推導………………………………………………...58
3-4-4 衡量指標………………………………………………...64
第五節 前置時間效益評估………………………………………...66
第四章 個案研究-鋼鐵業之應用………………………………………..72
第一節 產業描述…………………………………………………..72
第二節 個案描述…………………………………………………..73
第三節 流程分析及系統說明……………………………………..75
4-3-1 流程分析...……………………………………………..76
4-3-2 系統說明…..…………………………………………….77
第四節 討論……………………………………………………….102
第五章 結論與未來研究方向…………………………………………..110
第一節 結論……………………………………………………….110
第二節 未來研究方向…………………………………………….111
參考文獻…………………………………………………………………..113
參考文獻 中文部分
1. 王立志,「系統化運籌與供應鏈管理」,滄海,民88年6月初版。
2. 林弘肯,「影響組織應用資訊科技於供應鏈管理之因素研究-製造業
實證分析」,中山大學資訊管理研究所碩士論文,民國88年。
3. 張君龍,「全球運籌告理之環境與背景:扭轉企業變革之策略轉折
時代」,中衛簡訊,138期,民國87年,12-21頁。
4. 張萬權,「我國鋼鐵產業現況與展望」,金屬工業第34卷第6期,
民國89年11月。
5. 蔡幸甫,「我國特殊鋼工業的現況與展望」,金屬工業第32第6期,
民國87年11月。

英文部分
1. Anderson, D. L., Britt, F. E. and Favre, D. J. (1997), “The Seven Principles of Supply Chain Management,” Supply Chain Management Overview.
2. Agrawal, A., Minis, I., and Nagi, R. (2000), “ Cycle time reduction by
improved MRP-based production planning,” International Journal of
Production Research, Vol. 38, No. 18, p.p. 4823-4841.
3. Bridleman, D. and Herrmann, J. (1997), “Supply chain management in a make-to order world,” APICS: The Performance advantage, March, pp. 32-38.
4. Bertrand, J., W., M. and Ooijen, H., P., G. (2000), “Customer order
lead times for production based on lead time and tardiness costs,”
International Journal of Production Economics, No. 64, pp.257-265.
5. Carravilla, M. A. and Sousa, J. P. (1995), “Hierarchical production planning in Make-To-order company: A case study,” European Journal of Operation Research, No. 86, p.p. 43-56.
6. Chance, V. and Goldfel,t C. (1985), “Lead Time Determinination and Control, Proceedings of Twenty-Eights,”Annual International Conference of the American Production and Inventory Control Society, 308-310.
7. Dam, P. V., Gaalman, G. J. C., and Sierksma, G. (1998), “Designing scheduling system for packaging in process industries: A tobacco company case,” International Journal of Production Economics, No. 56-57, p.p. 649-659.
8. Easton, F. F. and Moodie D. R. (1999), “Theory and methodology: Pricing and lead time decision for make-to-order firms with contingent order,” European Journal of Operational Research, No. 116, pp. 305-318.
9. Fogarty, D. W., Blackstone, J. H. and Hoffmann, T. R. (1991) “Production and Inventory Management,” Sourth-Western.
10. Gonzlez, J. J. and Reeves, G. R. (1983), “Master production scheduling: a multiple-objective linear programming approach,” International Journal of Production Research, Vol. 21, No. 4, pp. 553-562.
11. Giesberts, P. M. J.(1991), “A functional based approach,” International Journal of Production Economics, No. 24, pp. 65-76.
12. Harland, C. (1997), “Supply chain operation performance roles,” Integrated Manufacturing Systems,Vol.8 No.2.
13. Hills, M. (1997), “Intranet business strategies,” John Wiley & Sons, Inc.
14. Hill, J. A., Berry, W. L., Leong, G. K. and Schilling, D. A. (2000), “Master production scheduling in capacitated sequence- dependent process industries,” International Journal of Production Research, Vol. 38, No. 18, p.p. 4743-4761.
15. Jahnukainen, J. and Lahti, M. (1999), “Efficient purchasing in make-to-order supply chains,” International Journal of Production Economics, No.59, p.p. 103-111.
16. Jones, R. M. and Towill D. R. (1999), “Total cycle time compression and the agile supply chain,” International Journal of Production Economics, No. 62, p.p. 61-73.
17. Kalakota, R., and Robinson, M. (1999), “e-Business roadmap for success, ” Addison-Wesley Longman..
18. King, B. E. and Benton, W. C. (1987), “Alternative master master production scheduling techniques in an assemble-to-order environment,” Journal of Operations Management, Vol. 7, pp. 179-201.
19. Kern, G., M. and Ebsary, J. C. (1996), “Master Production Rescheduling Policy in Capacity-Constrained Just-In-Time Make-To-Stock Environment,” Decision Sciences, Vol. 27,No.2, pp. 365-387.
20. Kochhar, A. K., Ma, X. and Khan, M. N. (1998), “Knowledge-based system approach to the development of accurate and realistic master production schedules,” Proc Instn Mech Engrs, Vol. 212, Paet B, pp.453-460.
21. Kimgsman, B., Hendry, L., Mercer, A. and Souza, A. D. (1995), “Responding to customer equiries in make-to-order companies Production and solutions,” International Journal of Production Economics, No.46-47, p.p. 219-231.
22. Kim, I. and Tang, C. S. (1997), “Lead time and response time in a pull production control system,” European Journal of Operational Research, No. 101, pp.474-485.
23. Lan, S. P., Chu, P., Chung, K. J., Wan, W. J. and Lo, R. (1999), “A simple method to locate the optimal solution of the inventory model with variable lead time,” Computer & Operation, No. 26, pp. 599-605.
24. Liao, C. J. and Shyu, C. H. (1991), “An Analytical Determination of Lead Time with Normal Demand.”, International Journal of Operations & Production Management, No.11, pp. 72-78.
25. Li, Y ,Fan, Z. and Zhao, X. (1999), “An Integrated Framework of Supply Chain Management System,” IEEE, pp. 196-199.
26. Lambert, M. D. and Cooper, M. C. (2000), “Issues in Supply Chain Management,” Industrial Marketing Management, Vol 29, pp. 65-83.
27. Maloni, M. J. and Benton, W. C. (1997), “Supply chain partnerships: opportunities for operations research,” European Journal of Operational Research, Vol. 101, No. 3, pp. 419-429.
28. Markland, R. E. (1990)“Coordinated production scheduling for make-to-order manufacturing,” European Journal of Operation Research, Vol. 45, No. 1, pp.155-176.
29. Miltenburg, J. and Sparling, D. (1996), “Managing and reducing total
cycle time: models and analysis,” International Journal of Production
Economics, No. 46-47, p.p. 89-108.
30. Naylor, J. B. and Naim, M. M. and Berry, D. (1999), “Leagility: Integrating the lean and agile manufacturing paradigms in the total supply chain,” International Journal of Production Economics, No. 62, p.p. 107-118.
31. Ouyang, L. Y and Wu, K. S. (1997), “Mixture Inventory model involving variable leas time with a service level constraint,” Computer Ops. Res., Vol. 24 ,No. 9, pp.875-882.
32. Ozdamar, L. and Yazgac T. (1997), “Capacity driven due date settings in make-to-order production systems,” International Journal of Production Economics, No. 49, pp. 29-44.
33. Ozdamar, L., Bozyel, M. A. and Birbil, S. I. (1998), “A hierarchical support system for production planning (with case study)” European Journal of Operational Research, Vol. 104, pp. 403-422.
34. Prakash, A. (1996), “The internet as a global strategic is tool,” Information Systems Management, Summer, pp. 45-49.
35. Poirier, Charles C. and Reiter, S. E. (1996), Supply Chain Optimization:Building the Strongest Totel Business Network, 1st ed, San Fransciso, CA:Berrett-Koethler..
36. Ruben, R. A. and Mahmoodi, F. (2000), “Lead time prediction in unbalanced production system,” International Journal of Production Research, Vol. 38, No. 7, p.p. 1711-1729.
37. Rho, B. H. and Yu, Y. M. (1998), “A comparative study on the structural relationships of manufacturing practices, lead time and productivity in Japan and Korea,” Journal of Operations Management, No. 16, pp. 257-270.
38. Sridharan, V. and Berry, W. L. (1990), “Master Production scheduling Make-to-stock Product:A Framework for Analysis,” International Journal of Production Research, Vol. 28, No. 3, pp. 541-558.
39. Tomiura, A. (1997), “Productivity in Japan’s manufacturing industry,” International Journal of Production Economics, No.52, pp. 239-246.
40. Thomas, D. J. and Griffin, P. M. (1996), “Coordinated supply chain management,” European Journal of Operational Research, Vol. 94, No. 1, pp. 1-15.
41. Viswanathan, S. and Goyal S.K. (1997), “ Optimal cycle time and production rate in a family production context with shelf life considerations,” International Journal of Production Research, Vol.35, No. 6, p.p. 1703-1711.
42. Vollamnn, T. E., Berry W. L. and Whybark, D. C. (1997), “Manufacturing planning and control systems,” McGraw-Hill.
43. Venkataraman, R. and Smith, S. B. (1996), “Disaggregation to a Rolling Horizon Master Production Schedule with Minimum Batch-Size Production Restrictions,” International Journal of Production Research, Vol. 34, No. 6, pp. 1517-1537.
44. Vrijhoel, R. and Koskeia, L. (2000), “The four roles of supply chain management in construction,” European Journal of Purchasing & Supply Management, Vol. 6, pp 169-178.
45. Wall, B., Higgins, P. and Browne, J. (1992), “A prototype system for short-term supply planning,” Computers in Industry, Vol. 19, pp. 1-19.
46. Wedel, J. and Lumsdn, K. (1995), “The influence of lead-time reduction on decision and rule in the production planning process,” International Journal of Production Economics, No. 41, pp. 399-404.
47. Wu, M. C. and Chen, S. Y. (1996), “Cost model for justifying the acceptance of rush Orders,” International Journal of Production Research, Vol. 34, No.7, Jul. 1996, pp. 1963-1974.
48. Weinstein, L. and Chung, C. H. (1999), “Integrating maintenance and production decision in a hierarchical production planning environment,” Computers & Operations Research, No. 26, p.p. 1059-1074.
49. Yucesan,E. and Groote, X. D. (2000), “Theory and Methodology:Lead time, order mechanisms, and customer service,” European Journal of Operational Research, No. 120, pp.118-130.
50. Zijm, W. H. M. and Buitenhek, R. (1996), “Capacity planning and lead time management,” International Journal of Production Economics, No. 46-47, pp. 165-179.

------------------------------------------------------------------------ 第 3 筆 ---------------------------------------------------------------------
系統識別號 U0026-0812200910252375
論文名稱(中文) 封裝廠植球區之雙機台排程模式
論文名稱(英文) Scheduling model of dual machines for solder ball mount process of semiconductor assembly plant
校院名稱 成功大學
系所名稱(中) 工學院工程管理碩士在職專班
系所名稱(英) Institute of Engineering Management
學年度 93
學期 2
出版年 94
研究生(中文) 許浚鳴
學號 n0790125
學位類別 碩士
語文別 中文
口試日期 2005-01-17
論文頁數 76頁
口試委員 指導教授-張行道
召集委員-李在長
口試委員-楊大和
口試委員-施勵行
關鍵字(中) 生產管理
生產排程
封裝廠
排程法則
雙機台排程
演算法
關鍵字(英) production scheduling
dual machine scheduling
assembly plant
BGA.
algorithm
production management
rules of scheduling
學科別分類
中文摘要   封裝業在半導體產業供應鏈中扮演重要角色,為符合客戶需求,在品質、交期上必定要更具競爭力,在有限生產規模下,生產線的規劃、變更調整變得非常重要。本研究以BGA系列產品封裝廠植球區如何提升生產效率為主題,探討為符合多元化產品、顧客需求量、生產週期、及機器環境與能力,分析並建立適當的排程模式,使人員、設備、品質及產能有最佳組合。
  研究建立以產品為導向之雙機台排程模式,以產品種類及作業複雜度作為機台負荷分類基礎,參考最近出貨產品種類,替每一客戶的固定接腳產品,平均建立在二台植球機上,避免重複性生產訂單發生等待,讓每一種產品在植球機有固定作業路徑。同時封裝廠為使資源充分應用,面對少量多樣產品需求,彙整多家接腳數相近產品在同一機台,讓產能堆疊達機台最大能力。在植球機上有固定規則依循,配合先進先出、最短加工時間優先方法,讓植球區排程保持最佳彈性。最後以實證方式,將本排程模式導入生產線,確認排程模式運作情形。
  實證過程中說明排程觀念在植球區製造現場演變的重要性。就植球區作業管理來看,排程不能僅專注在產量及時間因素,需有更多的考量如產品特殊規格需求、機器環境與機器能力、及產品多元特性。面對這些製造要素,本研究排程模式應用於BGA產品植球區,帶來幾項優勢:(1)減少機台作業程式管理,(2)縮短換模時間,(3)提昇生產週期達成率,(4)對產能波動具有穩定效果,(5)改善機台換模造成子批生產週期異常,(6)每種產品有固定作業路徑。



英文摘要   Assembly plays an important role in the supply chain of semiconductor industry. In order to conform the requirements of customers, it is competitive on quality and delivery time. It has becoming more and more important to plan and modify production line under restricted production scale. This research focuses on how to raise production efficiency for BGA (Ball Grid Array) products at solder ball mount process of an assembly plant. In responding to the diversified products, demands of customers, production cycle time, and machine environment, this study analyzes and establishes a applicable scheduling model to form a better mix for staffs, facilities, quality, and capacity.
  In the product oriented scheduling model for dual machines, the loads of machines are classified according to the product types and the production complexity. Two machines are based for every pin count product in the solder ball mount process to avoid waiting of repeat orders and let the same type of product have the same path. At the same time, to make fully use of the resources and face diversified products, the products of similar pin counts are arranged in the same machine to reach the machine’s capacity. The solder ball mount process is scheduled to follow the first in first out (FIFO), and shortest processing time first (SPTF) rules to keep flexibility. At last, the scheduling model is tested on real production lines.
  The test shows that the developed scheduling model for dual machines of BGA products has the following advantages: (1) reduced numbers of programs for machines, (2) shortened mold change time, (3) completion in cycle time, (4) less fluctuated output, (5) improved cycle time deviation, and (6) fixed operating path for every product.


論文目次 摘 要                        I
Abstract                     II
目 錄                       III
圖目錄                        VI
表目錄                       VII
第一章 緒論                     1
 1.1 研究動機                   1
 1.2 研究目的                   2
 1.3 研究流程 2
 1.4 研究範圍與限制 3
第二章 封裝廠生產線作業與排程              5
 2.1 IC封裝作業流程與特性            5
  2.1.1 IC封裝作業流程             5
  2.1.2 半導體封裝之特性            8
  2.1.3 封裝廠作業現場特性            9
 2.2 生產排程理論                11
  2.2.1 生產排程                11
  2.2.2 排程環境                12
 2.3 IC封裝生產流程                15
 2.4 封裝生產系統                17
第三章 植球區作業分析                19
 3.1 作業現場問題                19
 3.2 作業子批分割模式               22
 3.3 產品轉換週期時間                22
 3.4 各產品模具配置                24
 3.5 產品需求狀況                26
 3.6 植球機換模效率                29
第四章 植球區排程模式                34
 4.1 理論背景                  34
  4.1.1 基本動線                34
  4.1.2 排程作業規則                35
  4.1.3 雙機台排程建構背景           37
 4.2 產品排程                  38
  4.2.1 主排程與主生產排程           38
  4.2.2 日程安排與現場控制           39
 4.3 派工規劃                  39
 4.4 產品雙機台排程方法                44
 4.5 理論觀點比較                49
第五章 實例應用                 52
 5.1 實例應用設計                52
 5.2 產能規劃                  54
 5.3 植球區設備規模與排程            56
  5.3.1 植球區資料與作業            56
  5.3.2 現有排程觀點與缺失           56
 5.4 植球區機台調整                 57
  5.4.1 植球機產品配置             57
  5.4.2 植球區換模               60
  5.4.3 植球區時間損失比率           62
 5.5 產能波動                  63
  5.5.1 每日產能波動               64
  5.5.2 每週產能波動               65
  5.5.3 每月產能波動               66
 5.6 波動時間週期分析               66
 5.7 生產週期差異分析               67
 5.8 雙機台排程優點               68
第六章 結論與建議                 70
 6.1 結論                   70
 6.2 建議                   72
參考文獻                       73

參考文獻 一、中文部份
1. 大野耐一,「豐田生產方式與現場管理」,日本能率協會,中華企業管理發展中心,民
70。
2. 田國興,「有設置時間之流程型工廠多階段平行機台總排程時間最小化問題」,中原大
學工業工程研究所碩士論文,民89。
3. 李昇芳,「半導體封裝之混線生產研究」,逢甲大學工業工程研究所碩士論文,民88。
4. 李嘉柱,李佳穎,「半導體後段廠之現場生產流程與作業管制條件分析辦法探討」,機
械工業雜誌,12月,pp.109-115,民88。
5. 李晉裕,「半導體測試廠有限資源產能規劃研究」,中原大學工業工程學系碩士論文,
民89。
6. 李榮貴等,「現場流程資料模式的建構與應用—以半導體封裝業在製品管制系統為
例」,中華管理評論,Vol.2, No.5, p.1-24,民88。
7. 宋身元,楊麗青,「淺談排程系統設計之相關要素」,機械工業雜誌,12月,
PP.233-239,民82。
8. 李友錚,「作業管理:創造競爭優勢」-二版修訂,前程企業,台北,民92年8月。
9. 林龍欽,「現場流程資料模式的建構與應用--以半導體封裝在製品管制系統為例」,
交通大學工業工程與管理研究所博士論文,民89。
10. 張盛鴻,「生產計畫與管理」-二版修訂,高立圖書,台北,民87。
11. 張保隆,陳文賢,蔣明晃,姜齊,盧昆宏,王瑞深,「生產管理」-二版,華泰,台
北,民89。
12. 黃宏文,「具製程規格能力機台之負荷分配」,Journal of the Chinese institute
of industrial engineers, Vol.18, No.4, pp.82-96, 2001
13. 賴士葆,「生產/作業管理:精要與個案」,華泰書局,民80年2月。
14. 傅和彥,「生產與作業管理」—三版,前程企業管理有限公司,台北,民88。
15. 日月光半導體公司製造八廠製二部作業現場訪談,2004。
二、西文部份
1. Adam, F., Fahy, T. and Murphy, C. (1998), “A framework for the classification of DSS usage across organizations “, Decision Support System, 22, 1-13.
2. Adler, L., Fraiman, N., Kobacker, E., Pinedo, M., Plotnicoff, J., C., and Wu, T., P. (1993), “BPSS : A scheduling support system for the packaging industry”, Operations Research, Vol.41, No.4, 641-648.
3. Ahmadi, R. H., and Matsuo, H. (2000), “A mini-line approach for pull production “, European Journal of Operations Research, 125, 340-358.
4. Azizoglu, M., and Kirca ,O. (1999), “On the minimization of total weighted flow time with identical and uniform parallel machines”, European Journal of Operational Research, Vol.113, 91-100.
5. Dannenbring, D. G. (1977), “An evaluation of flow shop sequencing heuristics”, Management Science, Vol.23, No.11, 1174-1182.
6. Friscia, A., and Baer, A. (1994), “MES: Missing Link,” InTech, Vol. 41, No. 5, 20-23.
7. Glassey, C. R., and Resende, M. G. C. (1988), “Closed- loop Jop shop Release Control for VLSI Circuit Manufacturing”, IEEE Transactions on Semiconductor Manufacturing, Vol.1, No.1, 26-46.
8. Graves, S. C. (1983), ”Scheduling of Re-Entrant Flow Shops“, Journal of Operations Management, Vol.3, No.4, 197-207.
9. Gupta, J. N. D. (1971), “A functional heuristic algorithm for the flowshop scheduling program”, Operational Research Quarterly, Vol.22, No.1, 39-47.
10. Gupta, J. N. D., and Tung, E. A. (1991), “Schedules for a two-stage hybrid flowshop with parallel machines at the second stage”, INT.J.PROD.RES., Vol.29, No.7, 1489-1502.
12. Hakanson and Bill (1996), “Manufacturing Execution Systems: Where’s the Payoff ?”, I&CS, March, 47-50.
13. Hastings, N. A. J., and Yeh, C. H. (1992), "Bill of manufacturing", Production and Inventory Management Journal, Fourth Quarter, 27-31.
14. Hundal, T. S., and Rajgopal, J. (1988), “An extension of Palmer’s heuristic for the flow shop scheduling problem”, INT.J.PROD.RES., Vol.26, 1119-1124.
15. Kochhar, S., and Morris, R. J. T. (1998), “Heuristic methods for flexible flow line scheduling”, Journal of Manufacturing System, Vol.6, No.4, 299-314.
16. Kovalyov, M. Y., and Shafransky, Y. M. (1997), “Batch scheduling with deadlines on parallel machines : An NP-hard case “, Information Processing Letters, Vol.64, 69-74.
17. Lou, S. X. C., and Kager, P. W. (1989), “A Robust Production Control Policy for VLSI Wafer Fabrication”, IEEE Transaction on Semiconductor Manufacturing, Vol.2, No.4, 159-164.
18. Lu, S. C. H., Ramaswamy, D., and Kumar, P. R. (1994), “Efficient Scheduling Policies to Reduce Mean and Variance of Cycle-Time in Semiconductor Manufacturing Plants”, IEEE Transaction on Semiconductor Manufacturing, Vol.7, No.3, 374-388.
19. Mandel, M., and Mosheiov, G. (2001), “Minimizing maximum earliness on parallel identical machines”, Computers and Operations Research, Vol.28, 317-327.
20. Melnyk, S. A., Carter, P. L., Dilts, D. M. and Lyth, D. M. (1985), Shop Floor Control, Dow Johns – Irwin, Homewood, Illinois.
21. MESA International (1997), “MES Functionalities & MRP to MES Data Flow Possibilities,” White Paper No.2.
22. MESA International (1995), “The Controls Layer:Controls Definition & MES to Controls Data Flow Possibilities,” White Paper No. 3.
23. Moder, J. J., Philips, C. R., and Davis, E. W. (1983), Project Management with CPM, PERT and Precedence Diagramming. 3rd Edition, Van Nostrand Reinhold, NY.
24. Morton, T. E., and Pentico, D. W. (1993), “Heuristic Scheduling System with Application to Production Systems and Project Management.”
25. Nowicki, E., and Smutnicki, C. (1998), “The flow shop with parallel machines : A Tabu search approach”, European Journal of Operational Research, Vol.106, 226-253.
26. Piersma, N., and Vam Dijk, W. (1996), “Local search heuristic for unrelated parallel machine scheduling with efficient neighborhood search.”, Mathematical and Computer Modeling, Vol.24, No.9, 191-194.
27. Pinedo, M., and Lee, Y. H. (1997), “Scheduling jobs on parallel machines with sequence-dependent setup times”, European Journal of Operation Research, Vol.100, 69-74.
28. Pillutla, S. N., and Nag, B. N. (1996), ”Object-oriented model construction in production scheduling decisions” , Decision Support System, 18, 357-375.
29. Richard J., and Tersine, A. (1985), Production Operations Management: Concepts Sucture and analysis, 2nd. ed. New York : North-Holland.
30. Santo, D. L., Carpender, D. A., and Schniederjans, M. J. (1995), “Global lower bounds for flow shops with multiple processors”, European Journal of Operational Research, 80, 112-120.
31. Santo, D. L., Carpender, D. A., and Schniederjans, M. J. (1996), “An evaluation of sequencing heuristics in flow shops with multiple processors”, Computers and Engineer, Vol.30, No.4, 681-692.
32. Uzsoy, R., Church, L. K., and Ovacik, I. M. (1992), “Dispatching Rules for Semiconductor Testing operations : A computational Study”, Thirteenth IEEE/CHMT International, 272-276.
33. Weng, W. W., and Leachman, R. C. (1993), “An Improvement Methodology for Real-time Production Decision at Batch-process Workstations.”, IEEE Transactions on Semiconductor Manufacturing, Vol.6, No.3, 219-225.
34. Wittrock, R. J. (1988), “An Adaptable scheduling algorithm for flexible flow lines”, Operations Research, Vol.36, No.3, 445-453.


------------------------------------------------------------------------ 第 4 筆 ---------------------------------------------------------------------
系統識別號 U0026-0812200911512175
論文名稱(中文) 應用基因演算法於彈性流線型工廠排程之研究
論文名稱(英文) Research on Genetic Algorithm applied on Production Scheduling of Flexible Flow Shop
校院名稱 成功大學
系所名稱(中) 工業與資訊管理學系專班
系所名稱(英) Department of Industrial and Information Management (on the job class)
學年度 94
學期 2
出版年 95
研究生(中文) 莊文化
學號 r3793117
學位類別 碩士
語文別 中文
口試日期 2006-05-28
論文頁數 60頁
口試委員 口試委員-楊太宏
口試委員-吳植森
指導教授-蔡長鈞
關鍵字(中) 彩色濾光片
平行機台
生產排程
彈性流線型工廠
基因演算法
關鍵字(英) Genetic Algorithm
Color Filter
Parallel Machine
Production Scheduling
Flexible Flow Shop
學科別分類
中文摘要 在一般彈性流線型工廠(Flexible Flow Shop)研究中,通常只考慮單一站點之平行機台(Parallel Machine),沒有人針對跨站點可同時運用之平行機台進行研究。但因製造機台設備之成本過於昂貴、廠房地形面積限制、有效節省空間之設施規劃、機台功能之多元化設計、相同製程需要重複加工,故常有跨站點運用同一群組平行機台之個案。故本研究將以彈性流線型工廠為例,考量相同功能之平行機台擺放位置和製造流程之相對關係特性,來探討可跨站點運用平行機台之排程規劃,進而模擬不同的訂單加工順序和加工機台選擇方式,來求得各批量最小化總完工時間,最終將計算其最小化總懲罰成本,期能有效提昇加工效率,求得各訂單批量之最佳產出時間和公司總懲罰成本最小化,增加工廠之實際產能,並將此研究成果提供生管部門做為產品生產排程(Production Scheduling)規劃之參考。
本研究根據文獻探討及彩色濾光片(Color Filter)工廠實務上的了解,訂定出可共用平行機台選擇之因子,並藉由基因演算法(Genetic Algorithm)之來求出最佳解,並使用Visual C++軟體撰寫其程式碼,使爾後能依實際狀況,模擬演練並能實際應用。且經由實證研究顯示,應用基因演算法求解少筆、多筆工件批量之案例,於求解效率、最小化總完工時間和總懲罰成本最小化之求解品質,都有極佳之成果。


英文摘要 In most researches of flexible flow shop, only the parallel machine of the single stage is considered instead of the parallel machine which conducts simultaneous utility in cross stages. But parallel machine with simultaneous utility in cross stages is essential for the high cost of equipment, limitation of the factory terrain, utility maximization of space, diversified design of the equipment functions, and required repetition in process. This research, therefore, takes the flexible flow shop as an example to study how to arrange the production schedule for the parallel machine with simultaneous utility in cross stands and the relative relational characteristic between the position and producing process of same parallel machines is considered. The simulation of different choice of producing process and machines based on different order is practiced as a further step to calculate the manufacturing time of each batch which is the key to minimize the total penalty cost and improvement of manufacturing efficiency. With the best manufacturing time of each batch and minimization of total penalty cost, the capacity will literally enhanced and the result of this research will be a production scheduling reference for the PC department.
This research, based on literature study and actual plant understanding, use the genetic algorithm to simulate production scheduling and develop possible factors of common parallel machine. This research uses the elite preserve strategy of the genetic algorithm and the program code written by Visual C++ to stimulate and practice. And researches have shown that Genetic Algorithm is a much better way to calculate the results of minimize total working time and total punishment cost in spite of cases of more or less working sheets.


論文目次 摘要 i
論文目錄 ii
表目錄 v
圖目錄 vii
第一章 緒論 1
第一節 研究背景與動機 1
第二節 研究目的 2
第三節 研究假設與限制 2
第四節 研究架構與大綱 3
第二章 文獻探討 6
第一節 排程依機器環境分類 6
第二節 彈性流線型工廠 8
第三節 基因演算法 11
2.3.1 基因演算法之優點 11
2.3.2 基因演算法之之演算流程 12
第三章 研究方法 20
第一節 問題描述 20
3.1.1 彩色濾光片製程簡介 20
3.1.2 彩色濾光片廠設施規劃和機台位置 23
3.1.3 問題描述 24
第二節 模式建置 24
3.2.1 符號定義 24
3.2.2 數學模式 26
第三節 基因演算法 28
第四章 實證研究與分析 35
第一節 基因演算法之求解測試 35
4.1.1 範例描述 35
4.1.2 實作環境之介紹 37
4.1.3 測試方法 37
4.1.4 求解品質分析 37
4.1.5 求解效率分析 43
第二節 多工作批量投產實證研究 44
第三節 總懲罰成本分析 51
第五章 結論與建議 54
第一節 結論與成果 54
第二節 未來研究方向與建議 55
參考文獻 57
參考文獻 Amirjanov, A. and Sobolev, K. (2006), “Genetic algorithm for cost optimization of modified multi-component binders,” Building and Environment, 41, 195-203
Bo, Z. W., Hua, L. Z. and Yu, Z. G. (2005), “Optimization of process route by genetic algorithms,“ Robotics and Computer-Integrated Manufacturing, In Press, Corrected Proof, Available online, 1 August
Carlier, J. and Rebaï, I. (1996), “Two branch and bound algorithms for the permutation flow,” European Journal of Operational Research, 90, 238-251
Chang, P. C., Chen, S. H. and Lin K. L. (2005), ”Two-phase sub population genetic algorithm for parallel machine-scheduling problem,” Expert Systems with Applications, 29, 705-712
Chang, Y. C. (2005), “Genetic algorithm based optimal chiller loading for energy conservation” Applied Thermal Engineering, 25, 2800-2815
Chang, P. C., Hsieh, J.C. and Hsiao, C.H. (2002), "Application of genetic algorithm to the unrelated parallel machine problem scheduling," Journal of the Chinese Institute of Industrial Engineering, 19, 79-95
Chen, K. C. and Tansri, H. (1994), “A study of genetic crossover opertions on the facilities layout problem,” Computers Industrial Engineering, 26 , 537-550
Davis, L.D. (1998), “Handbook of genetic algorithms.” Artificial Intelligence, 100, 325-330
Falkenauer, E. and Bouffouix, S. (1991), “A genetic algorithm for job shop scheduling,” Proceedings of IEEE International Conference on Robitcs and Automaion Sacramento, 824-829
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, 931-942
Forgaty, T. C. (1989), “Varying the probability of mutation in the genetic algorithm”, Proceedings of the 3rd International Conference on Genetic algorithms, 104-109
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 TheirApplications, 154-159
Grefenstette, J. J., (1986), “Optimization of control parameters for genetic algorithms,” IEEE Transactions on systems, 16, 122-128
Gupta, J.N.D., Ho, J. C. and Ruiz-Torres, J. C. (2004), “Makespan minimization on identical parallel machines subject to minimum total flow-time,” Journal of the Chinese Institute of Industrial Engineers, 21, 220-229
Gupta, J. N. D. and Tung, E. A. (1991), “Schedules for a two-stage hybrid flowshop with parallel machines at the second stage”, International Journal of Production Research, 29, 1489-1502.
Holland, J. H. (1975), “Adaptation in natural and artificial Systems,” Ann Arbor:University of Michigan Press
Hoogeveen, J. A., Lenstra, J. K. and Veltman, B. (1996), “Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard,” European Journal of Operational Research, 89, 172-175
Jou, C. (2005), “A genetic algorithm with sub-indexed partitioning genes and its application to production scheduling of parallel machines,” Computers & Industrial Engineering, 48, 39-54
Kochhar, S., Morris, R. J. T. (1987), “Heuristic methods for flexible flow line scheduling,” Journal of Manufacturing Systems, 6, 299-314.
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, 58-77
Kyparisism, G. J. and Koulamas, C . (2005), “A note on makespan minimization in two-stage flexible flow shops with uniform machines,” European Journal of Operational Research, In Press, Corrected Proof, Available online 24 August
Kyparisism, G. J. and Koulamas, C. (2006), “Flexible flow shop scheduling with uniform parallel machines,” European Journal of Operational Research, 168, 985-997
Murata, T., Ishibuchi, H. and Tanaka, H. (1996), “Genetic algorithm for flowshop scheduling problem,” International Journal of Computers and Industrial Engineering, 30, 1061-1071
Nowicki, E. and Smutnicki, C. (1998), “The flow shop with parallel machines : A tabu search approach”, European Journal of Operational Research, 106, 226-253.
Peng, J. and Liu, B. (2004), “Parallel machine scheduling models with fuzzy processing times,” Information Sciences, 166, 49-66
Pinedo, M. (1995) “Scheduling theory, algorithm, and systems.” New Jersey: Prentice Hall
Santos, D. L., Hunsucker, J.L. and Deal D.E. (1996), “An evaluation of sequencing heuristics in flow shops with multiple processors”, Computers & Industrial Engineering, 30, 681-692
Schaffer, J. D., Caruana, R. A., Eshelman, L. J. and Das, R.(1989), “A study of control parameters affecting online performance of genetic algorithms for function optimization,” Proceedings of the Third International Conference on Genetic Algorithms, 51-60
Soewandi, H. and Elmaghraby, S., (2003), “Sequencing on two-stage hybrid flowshops with uniform machines to minimize makespan.” Institute of International Education Transaction, 35, 467–477
Sridhar, J. and Rajendran, C. (1993), “Scheduling in a cellular manufacturing system: a simulated annealing approach” International Journal of Production Research, 31, 2927-2945
Ting, C. K., Li, S. T. and Lee, C. N. (2001), “TGA: A new integrated approach to evolutionary algorithms”, Congress on Evolutionary Computation, 2, 917-924
Wittrock, R. J. (1985), “Scheduling algorithms for flexible flow lines.” IBM Journal of Research and Development, 29, 401-412
Yao, M. J. and Huang, J. X. (2005), “Solving the economic lot scheduling problem with deteriorating items using genetic algorithms” Journal of Food Engineering, 70, 309-322

------------------------------------------------------------------------ 第 5 筆 ---------------------------------------------------------------------
系統識別號 U0026-0812200911515039
論文名稱(中文) 利用修正式德爾菲法建立管理本體論之關係運算子-以主生產排程規劃為例
論文名稱(英文) Applying the Modified Delphi Method to Implement the Relational Operators in Management Ontology—The Case of Master Production Schedule Planning Ontology
校院名稱 成功大學
系所名稱(中) 資訊管理研究所
系所名稱(英) Institute of Information Management
學年度 94
學期 2
出版年 95
研究生(中文) 丘婉儷
學號 r7693407
學位類別 碩士
語文別 中文
口試日期 2006-05-28
論文頁數 100頁
口試委員 指導教授-王泰裕
口試委員-陳梁軒
口試委員-謝中奇
口試委員-林君維
關鍵字(中) 主生產排程規劃
本體論關係子
管理本體論
修正式德爾菲法
關鍵字(英) Modified Delphi Method
Management Ontology
Ontology Relation Operators
Master Production Schedule Planning.
學科別分類
中文摘要 由於知識管理時代來臨,本體論(ontology)的盛行,針對不同領域皆有其專屬本體論,以幫助使用者去互相分享和共同理解該領域知識,然而現今一般在建立本體論時,仍主要在於將知識中不同的概念抽取出來建成物件,並定義物件內的屬性,透過屬性來間接定義概念之間關係,卻很少直接將不同概念(classes)間或是不同案例(instances)間關係,甚而不同本體論間關係明確定義出來,因此,在本研究中,將利用修正式德爾菲法直接把不同知識項目間的關係運算子定義出來,去連結之間的關係,並假設管理層面下應具有不同階層關係的本體論,不同階層本體論中會具有不同關係運算子,階層較高本體論的關係運算子在階層較低的本體論中亦可使用。本研究以最基本單元-管理層面本體論中生產管理內的主生產排程規劃領域,以修正式德爾菲法探討其本體論中不同項目間關係運算子。透過關係運算子的建立可增進本體論的完整性及整合性,來幫助未來此領域專家可建立更完善的本體論,並讓此本體論的使用者可快速了解此領域知識,此本體論的管理者未來可更方便維護。
本研究在實作方面,將透過ontology建立工具:Protégé 3.1.1,以Java為程式語言開發工具,撰寫其關係運算子外掛模組,使知識工程師在建立主生產排程規劃領域本體論時,可利用此模組去建立不同概念或不同案例間關係,並可讓使用者透過此模組,直接對這些關係更了解,最後從建立、測試與實際執行系統的過程,對本研究做出結論,並對未來可延伸或是改進地方提出建議。


英文摘要 Different ontologies are specifically applicable to different domains in order to help the users to share their domain knowledge as the knowledge management is blooming in these days. However, most researchers usually create classes for the concepts of the domain, define the properties of the classes, and set the relations among concepts indirectly via these properties when developing their ontology. They seldom define the relations directly among classes, instances, and ontologies.
In this research, we apply Modified Delphi Method to define the relational operators among knowledge items directly. These relational operators, on one hand, will link the relationship among knowledge items. And the relational operators, on the other hand, provide the foundation of management ontology. We assume that there exists different ontology under different management levels. And different relational operators are needed for different ontologies in each management levels. Thus, the relational operators of high level ontology can be used in lower level ontology. The Master Production Schedule Planning is used as the production management domain to develop the relational operators of the ontology. These relational operators can improve the integration of ontology, help the domain experts to build more complete ontology, and make the users understand the domain knowledge more quickly.
Specifically, we use Protégé 3.1.1 as an ontology-developing environment and Java is used as a program-developing tool to implement the relational operator plug-in for protégé. When the knowledge engineers develop Master Production Schedule Planning ontology, they can use the plug-in to implement relations among concepts or instances. And users can understand these relations thoroughly.


論文目次 目錄
摘要 I
ABSTRACT II
誌謝 III
目錄 IV
表目錄 VI
圖目錄 VII
第一章 緒論 1
第一節 研究動機 1
第二節 研究目的 1
第三節 研究範圍及限制 2
第四節 研究方法與架構 2
第五節 論文大綱 4
第二章 文獻探討 5
第一節 內隱知識的擷取方法 5
第二節 德爾菲法 11
第三節 本體論 15
第四節 本體論關係子 18
第五節 管理層面知識管理 29
第六節 小結 33
第三章 關係運算子建構方法 35
第一節 研究設計流程架構 35
第二節 準備階段 38
第三節 問卷設計 40
第四節 實際驗證 44
第五節 小結 45
第四章 問卷設計及實證 46
第一節 問卷設計 46
第二節 主生產排程規劃本體論建立 56
第三節 系統實作及驗證 61
第四節 小結 70
第五章 結論與建議 71
第一節 結論 71
第二節 建議及未來研究 72
參考文獻 74
附錄一 79
附錄二 90

表目錄
表2-1 內隱知識與外顯知識的來源 6
表2-2 六種不同部分關係以及其性質限制 21
表4-1 第二回合問卷結果 50
表4-2 第三回合問卷結果 53
表4-3 第三回合問卷穩定度分析 53
表4-4 第四回合問卷結果 55
表4-5 第四回合問卷穩定度分析 55


圖目錄
圖1-1 研究架構流程圖 3
圖2-1 德爾菲法流程圖 14
圖2-2 ONTOLOGY的類型 18
圖2-3 空間彼此間關係之示意圖 25
圖2-4 TRANSFORMATION_OF 26
圖2-5 三種不同的衍生關係(A) 延續 (B) 融合 (C) 分裂 26
圖2-6 T FIRST_INSTANT P 28
圖2-7 T LAST_INSTANT P 28
圖2-8 P IMMEDIATELY_PRECEDED_BY P1 28
圖2-9 資訊的三個維度 31
圖2-10 生產排程中的五大概念 33
圖3-1 建構主生產排程規劃本體論關係運算子流程圖 37
圖3-2 管理層面本體論相對階層關係圖 39
圖3-3 建構主生產排程規劃本體論關係運算子(問卷設計流程圖) 40
圖3-4 PRECEDED_BY 示意圖 43
圖3-5 建構主生產排程規劃本體論關係運算子(實際驗證流程圖) 44
圖4-1 MSE ONTOLOGY內主要類別 57
圖4-2 主生產排程規劃本體論類別圖 60
圖4-3 主生產排程規劃本體論案例圖 61
圖4-4 關係運算子模組架構圖 62
圖4-5 PROTÉGÉ 3.1.1系統畫面圖 63
圖4-6 關係查詢介面圖 63
圖4-7 聚集關係運算子圖 65
圖4-8 拆解關係運算子圖(ㄧ) 66
圖4-9 拆解關係運算子圖(二) 67
圖4-10 混合關係運算子圖 68
圖4-11 暗示關係運算子圖 69
圖4-12 處於…之前關係運算子圖 70

參考文獻 中文:
王存國、季延平、范懿文,決策支援系統,三民書局,台北,1996。
王美音、楊子江譯,創新求勝,譯自 Nonaka, I., H. Takeuchi(The Knowledge-Creating Company),遠流出版社,台北,1997。
林隆儀譯,創造性思考與腦力激盪法,譯自Rawlinson, J.G. (Creative thinking and brainstorming),清華出版,台北,1988。
胡幼慧,質性研究:理論、方法及本土女性研究實例,巨流圖書公司,台北,1996。
陳國華等合譯,未來學導論:歷史、目的與知識,譯自Bell, W (Foundations of futures studies: History, Purposes, and Knowledge),學富,台北,2004。
黃俊英,企業研究方法,東華書局,台北,1999。
歐素汝譯,焦點團體 :理論與實務,譯自Stewart, D.W., P. N. Shamdasani (Focus Groups: Theory and Practice),弘智出版社,台北,2000。
鍾倫納,應用社會科學研究法,臺灣商務印書館,台北,1996。

西文:
Abecker A., A. Bernardi, K. Hinkelmann, O. Kuhn, and M. Sintek, “Toward a Technology for Organizational Memories”, IEEE Intelligent Systems, vol. 13, no. 3, pp. 40-48, 1998.
Artale A., E. Franconi, N. Guarino, and L. Pazzi, “Part-whole relations in object-centered systems: An overview,” Data and Knowledge Engineering, vol. 20, pp. 347-383, 1995.
Davies J., D. Fensel and F. van Harmalen, Towards the semantic web :ontology-driven knowledge management, Wiley Press, 2003.
Elst L.V., and A. Abecker, “Ontologies for information management: balancing formality, stability, and sharing scope,” Expert Systems with Applications, vol. 23, pp. 357-366, 2002.
Fensel D., Ontologies: A Silver Bullet for Knowledge Management and Electronic Commerce, Springer Press, 1998.
Fernandez I.B., A. Gonzalez, and R. Sabherwal, Knowledge Management: Challenges,Solutions, and Technologies, Pearson Press, 2004.
Guarino N., “Formal ontology, conceptual analysis and knowledge representation,” International Journal of Human-Computer Studies, vol. 43, pp. 625-640, 1995.
Guarino N., “Formal Ontology and Information Systems. Formal Ontology in Information System,” Proceedings of FOIS’98, Trento, Italy, 6-8. Amsterdam, IOS Press, pp. 3-15, 1998.
Green B., M. Jones, D. Hughes, and A. Williams, “Applying the Delphi technique in a study of GPs’ information requirements,” Health and Social Care in the Community, vol. 7, no. 3, pp. 198-205, 1999.
Gessner R.A., Master Production Schedule Planning, Wiley Press, 1996.
Horrocks I., P.F. Peter-Schneider, and F. van Harmelem, “From SHIQ and RDF to OWL: The Making of a Web Ontology Language,” Journal of Web Semantics, vol. 1, no. 1, pp. 7-26, 2003.
Krueger R.A., Focus Groups: A Practical Guide for Applied Research, Sage Press, 1988.
Linstone H.A., and M. Turoff, The Delphi Method: Techniques and Applications, Olaf Helmer Press, 2002.
Lin H.-K., J.A. Harding, and M. Shahbaz, “Manufacturing system engineering ontology for semantic interoperability across extended project teams,” International Journal of Production Research, vol. 42, no. 24, pp. 5099-5118, 2004.
McKenna H.P., “The Delphi technique: a worthwhile research approach for nursing,” Journal of Advances Nursing, vol. 19, pp. 1221-1225, 1994.
Metaxiotis K.S., J.E. Psarras, and D. Askounis, “Building ontologies for production scheduling systems: towards a unified methodology,” Information Management & Computer Security, vol. 9, no. 1, pp. 44-50, 2001.
Murry J.W., and J.O. Hammons, “Delphi: A versatile methodology for conducting qualitative research,” The Review of Higher Education, vol. 18, no. 4, pp. 423-436, 1995.
Noy N.F., and D.L. McGuinness, Ontology Development 101: A Guide to Creating Your First Ontology, Stanford Univ. Press, 2001.
Roche C., “Corporate ontologies and concurrent engineering,” Journal of Material Processing Technology, vol.107, pp. 187-193, 2000.
Schlenoff C., R. Ivester, and A. Knutilla, “A robust process ontology for manufacturing systems integration,” Proceedings of the 2nd International Conference on Engineering Design and Automation, 1998.

Smith B., W. Ceuster, B. Klagges, J. Kohler, A. Kumar, J. Lomax, C. Mungall, F. Neuhaus, A.L. Rector, and C. Rosse, “Relations in Biological Ontologies,” Genome Biology, vol. 6, no. R46, pp. 1-15, 2005.
Staab S., R. Studer, H. -P. Schnurr, and Y. Sure, “Knowledge Processes and Ontologies,” IEEE Intelligent Systems, vol. 16, no. 1, pp. 26-34, 2001.
Sumsion T., “The Delphi Technique: An Adaptive Research Tool,” British Journal of Occupational Therapy, vol. 61, no. 4, pp. 153-156, 1998.
Taylor S.J., and R. Bogdan, Introduction to qualitative research methods: a guidebook and resource, 3rd ed, Wiley Press, New York, 1998.
Ushold M., and M. Gruninger, “Ontologies: Principles, Methods and Application,” Knowledge Engineering Review, vol. 11, no. 2, pp. 93-136, 1996.
Walker A.M., “A Delphi Study of Research Priorities in the Clinical Practice of physiotherapy,” Physiotherapy, vol. 80, pp. 205-207, 1994.
Williams P.L., and C. Webb, “The Delphi technique: a methodological discuss,” Journal of Advances Nursing, vol. 19, pp. 180-186, 1994.
Winston M.E., R. Chaffin, and D. Herrmann, “A Taxonomy of Part-Whole Relations,” Cognitive Science, vol. 14, pp. 417-444, 1987.
Zack M.H., “Managing Codified Knowledge,” Management Review, summer. pp. 45-58, 1999.
Zikmund W.G., Exploring marketing research, 4th ed, Dryden Press, New York, pp.268-269, 1991.

網站:
BMO, ”The Open Source Business Management Ontology,”
http://www.bpiresearch.com/Resources/RE_OSSOnt/re_ossont.htm, September 2003.

OWL, “Ontology Web Language Overview,” http://www.w3.org/TR/owl-features/, February 2004.

------------------------------------------------------------------------ 第 6 筆 ---------------------------------------------------------------------
系統識別號 U0026-0812200913373300
論文名稱(中文) 應用基因演算法於特用化學品工廠排程之研究
論文名稱(英文) Research on Genetic Algorithm applied on Scheduling of Specialty Chemical Plant
校院名稱 成功大學
系所名稱(中) 工業與資訊管理學系專班
系所名稱(英) Department of Industrial and Information Management (on the job class)
學年度 95
學期 2
出版年 96
研究生(中文) 宋志龍
學號 r3794107
學位類別 碩士
語文別 中文
口試日期 2007-05-26
論文頁數 58頁
口試委員 指導教授-蔡長鈞
口試委員-吳植森
口試委員-林水順
口試委員-楊太宏
關鍵字(中) 基因演算法
總完成時間
特用化學品
平行機台
生產排程
關鍵字(英) Genetic Algorithm
Makespan
Specialty Chemicals
Parallel Machine
Production Scheduling
學科別分類
中文摘要 特用化學品(Specialty Chemicals)生產為批次生產,隨著產能的增加反應槽的建構成本將成比例增加。如何將訂單有效切割以求取反應槽最大運用效益將成為重要的課題。針對特用化學品生產排程的研究尚不多見,因此本研究將平行機台(Parallel Machine)的概念應用於特用化學品的生產排程(Production Scheduling)。本研究以各反應槽的產品生產順序為基因碼,總完成時間(Makespan)為目標函數並運用基因演算法(Genetic Algorithm)來求其近似最佳解。
本研究結果與傳統派工方式-最早到期日優先派工法則(EDD)比較其求解品質。在大量排程,總完成時間可有效降低13個單位時間;在小量排程,總完成時間可有效降低21個單位時間,由此可證,本研究方法確實有其求解效果。本研究使用MATLAB軟體撰寫程式碼,爾後可依實際狀況修正並能實際應用於工廠。因此本研究提出的方法在實務上能夠有效地協助管理者執行排程相關之作業,且具有實際應用的價值。
英文摘要 Batch production technique is applied to the production of specialty chemicals. As the capacity increasing, the construction cost of reactors will be added proportionably. How to divide up orders efficiently to gain the greatest use of reactors will be an important issue. There is few research about the idea of parallel machine used in the production scheduling of specialty chemicals so far;therefore, this research will be applied on the production scheduling of specialty chemicals with the concept of parallel machine.At this point, this research use the genetic algorithm to evaluate the approximate best value with the product sequence of reactors as genes and Makespan as objective function.
After comparing the traditional dispatching method, earliest due date (EDD), with the result of this research, it shows that, in makespan, 13 units of time span reduced effectively in terms of big quantity of production scheduling, and 21 units of time span lowered in terms of small quantity. Thus it can be seen that this research method does obtain the greatest outcome of its application in specialty chemicals production. And then the method of research applied by program code written by MATLAB can be revised according to actual situation and also put it into practice in the plant. Consequently, the method of this research can assist the managers to make related production scheduling efficiently and have practical application value.
論文目次 摘要..................................................................................................................i
致謝................................................................................................................iii
論文目錄........................................................................................................iv
表目錄...........................................................................................................vii
圖目錄............................................................................................................ix
第一章 緒論....................................................................................................1
第一節 研究背景與動機................................................................................1
第二節 研究目的............................................................................................2
第三節 研究假設與限制................................................................................3
第四節 研究架構與大綱................................................................................3
第二章 文獻探討............................................................................................6
第一節 特用化學品工廠簡介與排程特性....................................................6
第二節 派工法則與平行機台排程................................................................8
第三節 基因演算法......................................................................................14
2.3.1 基因演算法之特點...............................................................................14
2.3.2 基因演算法之步驟...............................................................................16
第三章 研究方法..........................................................................................27
第一節 問題描述..........................................................................................27
3.1.1特用化學品工廠製程與設備簡介.......................................................27
3.1.2特用化學品工廠生產程序...................................................................28
3.1.3問題定義...............................................................................................29
第二節 模式建置.........................................................................................30
3.2.1符號定義...............................................................................................30
3.2.2數學模式...............................................................................................31
第三節 基因演算法.....................................................................................32
第四章 實證研究與分析.............................................................................38
第一節 案例描述.........................................................................................38
第二節 基因演算法之求解測試-小量排程................................................39
4.2.1實作環境介紹.......................................................................................39
4.2.2窮舉法與EDD法求解結果-小量排程..................................................39
4.2.3以實驗設計法進行基因演算法求取最佳解-小量排程......................41
第三節 基因演算法之求解測試-大量排程................................................44
4.3.1 EDD法求解結果-大量排程.................................................................44
4.3.2以實驗設計法進行基因演算法求取最佳解-大量排程......................45
第五章 結論與建議.....................................................................................50
第一節 成果與結論.....................................................................................50
第二節 未來研究方向與建議.....................................................................51
參考文獻......................................................................................................53
參考文獻 [1]張百棧、謝日章與蕭陳鴻。“基因演算法於非等效平行機台排程之應用” Journal of the Chinese Institute of Industrial Engineers, 19(2), 79-95, 2002。

[2]經濟部。2005特用化學品工業年鑑(編號:ITRIEK-0453-T411)。台北市:
洪世淇, 2005。

[3]Balasubramanian, H., Mönch, L., Fowler, J., and Pfund, M., “Genetic algorithm based scheduling of parallel batch machines with incompatible job families to minimize total weighted tardiness.” International Journal of Production Research, 42(8), 1621-1638, 2004.

[4]Beasley, J. E., and Chu, P. C. , “A genetic algorithm for the set overing problem.” European Journal of Operational Research, 94, 392-404, 1996.

[5]Bo, Z. W., Hua, L. Z., and Yu, Z. G., “Optimization of process route by genetic algorithms.“ Robotics and Computer-Integrated Manufacturing, 22,
180-188, 2006.

[6]Cao, D., Chen, M. Y., and Wan, G. H., “Parallel machine selection and job scheduling to minimize machine cost and job tardiness.” COMPUTERS & OPERATIONS RESEARCH, 32(8), 1995-2012, 2005.

[7]Chan, K. Y., Aydin, M. E., and Fogarty, T. C., “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, 1075-1090, 2006.

[8]Chen, B., Ye, Y. Y., and Zhang, J. W., “Lot-sizing scheduling with batch setup times.” JOURNAL OF SCHEDULING, 9(3), 299-310, 2006.

[9]Chen, J. F., “Unrelated parallel machine scheduling with secondary resource constraints.” INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 26(3), 285-292, 2005.

[10]Chen, R. S., Lu, K. Y., and Yu, S. C., ”A hybrid genetic algorithm approach on multi-objective of assembly planning problem.” Engineering Applications of Artificial Intelligence , 15, 447-457, 2002.

[11]Davis, L., “Handbook on Genetic Algorithms.” New York : Van Nostrand Reinhold, 1991.

[12]Deris, S., Omatu, S., Ohta, H., Shaharudin, K. L. C., and Samat, P.A., “Ship maintenance scheduling by genetic algorithm and constraint-based reasoning. “ European Journal of Operational Research, 112, 489-502, 1999.

[13]Dessouky, M. M., and Kijowski, B. A., “Production scheduling of single-stage multi-product batch chemical processes with fixed batch sizes.” IIE Transactions, 29(5), 399–408, 1997.

[14]Fishwick, R. J., Liu X. L., and Begg, D. W., “Adaptive search in discrete limit analysis problems.” Computer Methods in Applied Mechanics and Engineering, 189, 931-942, 2000.

[15]Gen, M., and Cheng, R., “Foundations of Genetic Algorithms, Genetic Algorithms & Engineering Design. ” New York : John Wiley & Sons, Inc, 1997.

[16]Gen, M., and Cheng, R., “Genetic algorithm and engineering design.” New York : Wiley, 1997.

[17]Goldberg, D., ”Genetic algorithms in search, optimization and machine learning.” Boston : Addison-Wesly, 1989.

[18]Goldberg, D., and Lingle, R., “Alleles, loci, and the traveling salesman problem.” Proceedings of International conference on Genetic Algorithms and TheirApplications, 154-159, 1985.

[19]Haupt, R., “A survey of priority rule-based scheduling,” OR Spectrum, 11, 3-16, 1989.

[20]Holland, J. H., “Adaptation in natural and artificial Systems.” Ann Arbor : University of Michigan Press, 1975.

[21]Jayamohan, M. S., and Rajendran, C., “Development and analysis of cost-based dispatching rules for job shop scheduling” European Journal of Operational Research, 157, 307-321, 2004.

[22]Jou, C., “A genetic algorithm with sub-indexed partitioning genes and its application to production scheduling of parallel machines.” Computers and Industrial Engineering, 48(1), 39-54, 2005.

[23]Kim, D. W., Kim, K. H., Jang, W., and Chen, F. F., “Unrelated parallel machine scheduling with setup times using simulated annealing.” ROBOTICS AND COMPUTER-INTEGRATED MANUFACTURING, 18(3-4), 223-231, 2002.

[24]Kwok, Y. K., and Ahmad, I., “Efficient scheduling of arbitrary task graphs to multiprocessors using a parallel genetic algorithm.” Journal of Parallel and
Distributed Computing, 47, 58-77, 1997.

[25]Leung, J. Y. T., and Pinedo, M., “Minimizing total completion time on parallel machines with deadline constraints.” SIAM JOURNAL ON COMPUTING, 32(5), 1370-1388, 2003.

[26]Mitchell, M., “An Introduction to Genetic algorithms.” Cambridge, MA : MIT Press, 1996.

[27]Mitchell, M., “Davis, L.D, Handbook of genetic algorithms.” Artificial Intelligence, 100, 325-330, 1998.

[28]Mokotoff, E., “Parallel machine scheduling problems: A survey.” ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH, 18(2), 193-242, 2001.

[29]Pinedo, M., “Scheduling theory, algorithm, and systems.” New Jersey :Prentice Hall, 1995.

[30]Rippin, D. W., “The big advantage offered by batch processing is flexibility.” Chemical Engineering, 98(5), 101–107, 1991.

[31]Tseng, H.-E. ”Guided genetic algorithms for solving a larger constraint assembly problem.” International Journal of Production Research, 44(3), 601-625, 2006.

[32]Venkatachalam, A.R., ”An analysis of an embedded crossover scheme on a ga-hard problem.” Computers and Operations Research, 22(1), 149-157, 1995.

[33]Van Hop, N., and Wan, G. H., “The scheduling problem of PCBs for multiple non-identical parallel machines.” EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 158(3), 577-594, 2004.

[34]Wang, P. T., Wang, G. S., and Hu, Z. G., “Speeding up the search process of genetic algorithm by fuzzy logic.” Proceeding of the Fifth European Congress on Intelligent Techniques and Soft Computing, 665-671, 1997.

[35]Yalaoui, F., and Chu, C. B., “Parallel machine scheduling to minimize total tardiness.” INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 76(3), 265-279, 2002.

[36]Yun, Y. S., “Genetic algorithm with fuzzy logic controller for preemptive and non-preemptive job-shop scheduling problems.” Computers & Industrial Engineering, 43, 623-644, 2002.

------------------------------------------------------------------------ 第 7 筆 ---------------------------------------------------------------------
系統識別號 U0026-0812200914050241
論文名稱(中文) 成比例的彈性產流式生產排程最佳化問題之研究
論文名稱(英文) Optimization of proportionate flexible flow shop scheduling problem
校院名稱 成功大學
系所名稱(中) 工程科學系碩博士班
系所名稱(英) Department of Engineering Science
學年度 96
學期 1
出版年 97
研究生(中文) 蕭德芳
學號 N9891107
學位類別 博士
語文別 英文
口試日期 2007-12-21
論文頁數 92頁
口試委員 口試委員-錢炳全
口試委員-郭英峰
口試委員-陳澤生
口試委員-朱治平
召集委員-李宗南
指導教授-黃悅民
關鍵字(中) 建構式基因演算法
建構啟發式
行產生法
總加權完成時間
平行機器排程
成比例產流式生產排程
禁忌搜尋法
關鍵字(英) Total weighted completion time
Constructive genetic algorithm
Proportionate flow shop
Constructive heuristic
Column generation
Parallel machine scheduling
Tabu search
學科別分類
中文摘要 排序與排程在製造生產系統及資訊處理環境中扮演著重要的角色,而且也應用在不同的領域中。在生產排程的問題中,包括工作生產排程(job shop scheduling)、產流式生產排程(flow shop scheduling)、開放式生產排程(open shop scheduling)及混合式生產排程(mixed shop scheduling),已有許多不同的方法發展出來解決複雜的排程問題。近年來人工智慧(artificial intelligence)搜尋技術,包括了類神經網路(neural network)、基因演算法(genetic algorithm)、禁忌搜尋(tabu search)、模擬退火(simulated annealing)及蟻群演算法(ant colony optimization)等方法有效的解決排程問題。這些方法大部分所找出的解趨向總體最佳解(global optimal),而跳脫局部最佳解(local optimal)。另外行產生法(column generation)在文獻中已被證實有效的解決線性規劃問題,而且也已經成功的應用在不同的平行機器排程(parallel machine scheduling)問題。
在本論文中,主要是探討成比例彈性產流式生產排程問題(proportionate flexible flow shop, PFFS)。 首先我們先討論成比例產流式生產排程問題(proportionate flow shop, PFS),在這問題下,有一系列不同的機器是被安排在s個階層(stage)中,而且每一個階層包含單一機器。每個工作包括了s個操作程序(operations),每個操作程序在機器上都需要一個處理時間,而且每個工作在不同的機器上的處理時間是相等。PFS的問題在近年來才吸引較多的注意力,並不像產流式生產排程(flow shop)在不同條件限制已有許多的文獻參考。PFFS問題結合了PFS的特性及平行機器排程問題 (也就是說在每一個階層存在多台相同的機器平行處理)。在本論文中,排程的目標函數(objective function)是找出最小總加權完成時間(total weighted completion time, TWCT),然而在PFFS問題與平行機器排程問題中找出最小的TWCT,兩者之間有極顯著的不同;在平行機器排程最佳解中,單一機器上的工作(jobs)是依加權最短處理時間(weighted shortest processing time)法則進行排序,然而在PFFS問題找出最小的TWCT需要較複雜的方法才能得到最佳解。
本文中我們結合行產生法(column generation)與建構啟發式(constructive heuristic)方法有效的解決PFFS問題。首先,我們將PFFS問題公式化為一個限制的主要問題(restricted master problem, RMP)及包含一個集合分割的公式(set partitioning formulation),而它的線性規劃寬鬆式是藉由行產生法來得到最佳解。再來,我們利用禁忌搜尋法搭配候選列表策略來產生在RMP所需的起始解。接下來,我們導出一個動態規劃演算法來解決單一機器的次問題(single-machine subproblem)。最後,當一個線性規劃寬鬆式完整解得到後(也就是說,當行產生法終止時),我們利用了建構啟發式方法將單一機器上所排定的工作(jobs)做最佳化的排序。
然而,當工作數量和機器數目的比率高的時候,我們發現行產生法需要較長的時間得到最好的解;因此本論文提出另一個替代方法,稱為混合建構式基因演算法(hybrid constructive genetic algorithm, HCGA),不僅解決了行產生法在工作數量和機器數目的比率高所需較長時間的問題,此外HCGA也可以有效的應用在其他平行機器排程上的問題。實驗模擬結果顯示行產生法與建構啟發式方法在合理的時間內得到最優的解,特別是當工作數量和機器數目的比率低的時候能在很短的時間內得到最優的解。另外實驗的結果也顯示混合建構式基因演算法在工作數量和機器數目的比率高的時候所需的時間優於行產生法。
英文摘要 Sequencing and scheduling describes a decision-making process that plays an important role in most manufacturing and production systems as well as in most information-processing environments. It also exists in many applications and most of them have demonstrated as NP complete. For the shop scheduling problems such as job shop, flow shop, open shop and mixed shop, many schemes are introduced to solve shop scheduling problem. There are several types of artificial intelligence (AI) search techniques in solving scheduling problems: neural networks (NN), genetic algorithm (GA), tabu search (TS), simulated annealing (SA) and ant colony optimization (ACO). Most AI search approaches try to find a better solution or escape from a local optimal to obtain the globally better solution. In recent times, column generation (CG) has proved an effective means of solving the linear relaxation programming involving huge set covering or set partitioning problems, and has been applied successfully to various parallel machine scheduling problems.
The studied scheduling problem is focused on the special case of the m machine flow shop problem, known as proportionate flow shop (PFS). In such a shop, a series of different machines is arranged in s stages (s > 1) with only a single machine at each stage. Each job consists of s sequential operations and each operation requires a processing time on machines and processing time for each job is equal on all machines. Unlike the flow shop scheduling problem under certain constraints that has attracted considerable attention, the PFS problems have recently gained considerable attention. Proportionate flexible flow shop (PFFS) scheduling problems combine the properties of proportionate flow shop scheduling problems and parallel machine scheduling problems (i.e., there are several identical machines in parallel at each stage). Minimizing the total weighted completion time in a PFFS problem significantly differs from the parallel-identical-machine scheduling problem, an optimal schedule in which the jobs on each machine are in weighted shortest processing time (WSPT) order. Thus, the PFFS problem of minimizing TWCT needs a more intricate approach.
In this study, a combined column generation and constructive heuristic (combined approach) is proposed to solve the PFFS problem with excellent quality solutions. First, the PFFS problem can be formulated into a restricted master problem (RMP) with a set partitioning formulation, whose linear relaxation is solved efficiently by a CG procedure. Moreover, to have an initial feasible RMP, a feasible schedule is generated, which is based on tabu search with a candidate list strategy. To solve single-machine subproblems, a dynamic programming algorithm is derived according to the optimality properties of a PFS problem. Finally, a constructive heuristic is employed for reconstructing jobs on a single machine to form an optimal sequence while an integral solution of the linear relaxation problem is obtained (i.e., when the CG procedure is terminated).
However, in situations involving that the ratio of the number of jobs to the number of machines is relatively high, the CG approach consumes considerable CPU time. Therefore, an alternative approach, named hybrid constructive genetic algorithm (HCGA), is also proposed in this dissertation to resolve the problem that the CG approach consumes much CPU time when the ratio of the number of jobs to the number of machines is relatively high. Furthermore, HCGA can be considered as another effective approach for other parallel machine scheduling problems. Simulation results demonstrate the effectiveness of the combined approach in obtaining excellent quality solutions in a reasonable time. In particular, the combined approach works extremely well when the ratio of the number of jobs to the number of machines is relatively small. Furthermore, experimental simulations also show that the HCGA approach consumes less computational time when the ratio of the number of jobs to the number of machines is relatively high.
論文目次 TABLE OF CONTENTS
摘 要 I
Abstract III
誌 謝 V
LIST OF TABLES IX
LIST OF FIGURES X
Chapter 1 Introduction 1
1.1 The scheduling problem 1
1.2 The job shop scheduling 2
1.3 The flow shop scheduling 3
1.4 The open shop scheduling 4 1.5 The mixed shop scheduling 5
1.6 Organization of this dissertation 6
Chapter 2 The flexible flow shop scheduling problem 7
2.1 Problem description and application area 7
2.2 Solution approaches for FFS scheduling problems 9
2.3 Genetic algorithms approach 10
2.4 Tabu search approach 11
2.5 Simulated annealing approach 13
2.6 Ant colony optimization approach 14
2.7 Column generation approach 16
Chapter 3 The proportionate flexible flow shop scheduling
Problem 18
3.1 Proportionate flow shop 18
3.1.1 Problem description and the merits and significance 18
3.1.2 Literature review 19
3.2 Proportionate flexible flow shop 20
Chapter 4 Combined column generation and constructive heuristic 22
4.1 The properties of optimality 22
4.2 Column generation approach 24
4.2.1 The Restricted Master Problem (RMP) 24
4.2.2 Single-machine subproblem 27
4.2.3 Dynamic programming for the subproblem 28
4.2.4 Branch-and-bound algorithm 31
4.3 Reconstruction of the best schedule using constructive heuristic 34
Chapter 5 Hybrid constructive genetic algorithm 37
5.1 Representation of structure and schema 38
5.2 CGA modeling 41
5.2.1 Tabu search 42
5.3 The evolution process 43
5.3.1 Initial population 44
5.3.2 Selection and recombination operators 45
5.3.3 Mutation operator 46
5.4 The algorithm 46
Chapter 6 Experimental results 49
6.1 Computational results using combined approach 49
6.1.1 Experiment 1 49
6.1.2 Experiment 2 51
6.2 Hybrid constructive genetic algorithm 53
6.2.1 Experimental setup 53
6.3 Comparison and analysis of the combined approach and HCGA 54
6.4 Comparison of HCGA and pure tabu search 56
Chapter 7 Conclusions and future works 59
References 61
Appendix: Tabu search for generating an initial schedule in the
initial RMP 72
自 述 76

LIST OF TABLES
Table 6.1 Computational results from the CG approach for problems with
n = 20, 30, 30, 40, 50 51
Table 6.2 Computational results from the CG approach for problems with
n = 60, 80, 100 52
Table 6.3 Comparisons of combined approach (CG+WSPT-MCI), HCGA and PTS for problems with n = 20, 30, 40 and 50 57
Table 6.4 Comparisons of HCGA, CG-PFFS and PTS for problems with
n = 60, 80, 100 58

LIST OF FIGURES
Figure 2.1 An FFS scheduling problem with n jobs and three production stages 8
Figure 2.2 Simulated annealing algorithm 14
Figure 2.3 ACS for TSP 16
Figure 4.1. Gantt chart for the example of the PFS problem in WSPT order 29
Figure 4.2. Gantt chart for the final sequence of the example 30
Figure 5.1. An example of three-machine schema 38
Figure 5.2. Framework of HCGA 48
參考文獻 1. P. Brucker, Y. N. Sotskov and F. Werner, Complexity of shop-scheduling problems with fixed number of jobs: a survey. Math Meth Oper Res, 65, 461–481, 2007.
2. M. L. Pinedo, Scheduling: Theory, algorithms, and systems. 2nd ed., Englewood Cliffs, NJ: Prentice-Hall, 2002.
3. R. Cheng, M. Gen and Y. Tsujimura, A tutorial survey of job shop scheduling problems using genetic algorithms, Part Ⅱ: Hybrid genetic search strategies. Computers & Industrial Engineering, 36, 343–364, 1999.
4. T. C. Chiang and L. C. Fu, Using dispatching rules for job shop scheduling with due date-based objectives. International Journal of Production Research, 45, 3245–3262, 2007.
5. M. S. Jayamonhan and C. Rajendran, New dispatching rules for shop scheduling: a step forward. International Journal of Production Research, 38, 563–586, 2000.
6. T. S. Raghu and C. Rajendran, An efficient dynamic dispatching rule for scheduling in a job shop. International Journal of Production Economics, 32, 301–313, 1993.
7. A. Baykasoglu, Linguistic-based meta-heuristic optimization model for flexible job shop scheduling. International Journal of Production Research, 40, 4523–4543, 2002.
8. Y. K. Kim, K. Park and J. Ko, A symbiotic evolutionary algorithm for the integration of process planning and job shop scheduling, Computers and Operations Research, 30, 1151–1171, 2003.
9. M. Garey, D. Johnson and R. Sethi, The complexity of flow shop and job shop scheduling. Mathematics Operations Research, 1, 117–129, 1976.
10. S. M. Johnson, Optimal two and three stage production schedules with setup time included. Naval Research and Logistics Quarterly, 1, 61–68, 1954.
11. C. R. Reeves, Genetic algorithm for flowshop scheduling problems. Computers and Operations Research, 15, 5–23, 1995.
12. I. H. Osman and C. N. Potts, Simulated annealing for permutation flow-shop scheduling. OMEGA, 17, 551–557, 1989.
13. F. A. Ogbu and D. K. Smith, The application of the simulated annealing algorithm to the solution of the n/m/Cmax flowshop problem. Computers and Operations Research, 17, 243–253, 1989.
14. M. Ben-Daya and M. Al-Fawzan, A tabu search approach for the flow shop scheduling problem. European Journal of Operational Research, 109, 88–95, 1998.
15. H. G. Campbell, R. A. Dudek and M. L. Smith, A heuristic algorithm for n-job, m-machine sequencing problem. Management Science, 16/B, 630–637, 1970.
16. D. G. Dannenbring, An evaluation of flow-shop sequencing heuristics. Management Science, 23, 1174–1182, 1977.
17. J. N. D. Gupta, A functional heuristic algorithm for the flow-shop scheduling problem. Operational Reaerch Quarterly, 22, 39–47, 1971.
18. T. S. Hundal and J. Rajgopal, An extension of Palmer’s heuristic for the flow–shop scheduling problem. International Journal of Production Research, 26, 1119–1124, 1988.
19. M. R. Garey and D. S. Johnson, Computers and intractability: a guide to the theory of NP-completeness. San Francisco, CA: Freeman, 1979.
20. R. Linn and W. Zhang, Hybrid flow shop scheduling: a survey. Computers & Industrial Engineering, 37, 57–61, 1999.
21. W. Kubiak, C. Sriskandarajah and K. Zaras, A Note on the complexity of open shop scheduling problems. INFOR, 29, 284–294, 1991.
22. C. Y. Liu and R. L. Bulfin, Scheduling ordered open shops. Computers & Operations Research, 14, 257 – 264, 1987.
23. C. Prins, An overview of scheduling problems arising in satellite communications. Journal of the Operationl Research Society, 40, 611 – 623, 1994.
24. H. Brasel, T. Tautenhahn and F. Werner, Constructive heuristic algorithms for the open-shop problem. Computing, 51, 95–110, 1993.
25. C. Gueret, and C. Prins, Classical and new heuristics for the open-shop problem: A computational evaluation. European Journal of Operational Research, 107, 306–314, 1998.
26. D. Alcaide, J. Sicilia and D. Vigo, A tabu search algorithm for the open shop problem. Top, 5(2), 283–286, 1997.
27. C. F Liaw, A hybrid genetic algorithm for the open shop scheduling problem, European Journal of Operational Research, 124, 28 – 42, 2000.
28. P. Brucker, J. Hurink, B. Jurisch and B. Wostmann, A branch-and-bound algorithm for the open-shop problem. Discrete Applied Mathematics, 76, 43–59, 1997.
29. N. V. Shakhlevich, Y. N. Sotskov and F. Werner, Complexity of mixed shop scheduling problems: a survey. European Journal of Operational Research, 120, 343–351, 2000.
30. T. Masuda, H. Ishii and T. Nishida, The mixed shop scheduling problem. Discrete Applied Mathematics, 11 (2), 175–186, 1985.
31. T. Gonzalez and S. Sahni, Open shop scheduling to minimize finish time. Journal of the Association for Computing Machinery, 23 (4), 665–679, 1976.
32. C. Sriskandarajah and P. Ladet, Scheduling algorithms for flexible flowshops: worst and average case performance. European Journal of Operational Research, 43, 424–445, 1989.
33. A. Guint, M. M. Solomon, P. K. Kedia and A. Dussauchoy, A computational study of heuristics for two-stage flexible flowshops. International Journal of Production Research, 34, 1399–1416, 1996.
34. J. N. D. Gupta, A. M. A. Hariri and C. N. Potts, Scheduling a two-stage hybrid flow shop with parallel machines at the first stage. Annals of Operations Research, 69, 171–191, 1997.
35. C. Oğuz, M. Ercan, T. C. Edwin Cheng and Y. F. Fung, Heuristic algorithms for multiprocessor task scheduling in a two-stage hybrid flow-shop. European Journal of Operational Research, 149, 390–403, 2003.
36. G. J. Kyparisis and C. Koulamas, A note on the two-stage assembly flow shop scheduling problem with uniform parallel machines. European Journal of Operational Research, 182, 945–951, 2007.
37. A. Tozkapan, O. Kırca and C. S. Chung, A branch and bound algorithm to minimize the total weighted flowtime for the two-stage assembly scheduling problem. Computers and Operations Research, 30(2), 309–320, 2003.
38. O. Moursli and Y. Pochet, A branch-and-bound algorithm for the hybrid flow shop. International Journal of Production Economics, 64, 113–125, 2000.
39. C. Oğuz, E. Fikret, T. C. Edwin Cheng and Y. F. Fung, Heuristic algorithms for multiprocessor task scheduling in a two-stage hybrid flow-shop. European Journal of Operational Research, 149, 390–403, 2003.
40. G. Kyparisis and C. Koulamas, A note on makespan minimization in two-stage flexible flow shops with uniform machines. European Journal of Operational Research, In Press, 2005.
41. J. N. D. Gupta, K. Kruger, V. Lauff, F. Werner and Y. N. Sotskov, Heuristics for hybrid flow shops with controllable processing times and assignable due dates. Computers and Operations Research, 29(10), 1417–1439, 2002.
42. Y. Yang, S. Kreipl and M. Pinedo, Heuristics for minimizing total weighted tardiness in flexible flow shops. Journal of Scheduling, 3, 71–88, 2000.
43. L. X. Tang, H. Xuan and J. Liu, A new Lagrangian relaxation algorithm for hybrid flowshop scheduling to minimize total weighted completion time. Computer Operations Reserach ,33, 3344–3359, 2006.
44. H. Wang, Flexible flow shop scheduling: optimum, heuristics and artificial intelligence solutions. Expert Systems, 22(2), 78–85, 2005.
45. J. H. Holland, Adaptation in natural and artificial systems. 1st edn, Massachusetts: MIT press, 1992.
46. Z. Michalewicz, Genetic Algorithms + Data structures = Evolution Programs. Third Edition, Springer, 13–44, 1999.
47. S. K. Iyer and B. Saxena, Improved genetic algorithm for the permutation flowshop scheduling problem. Computers and Operations Research, 31, 593–606, 2004.
48. I. Lee, R. Sikora and M. J. Shaw, A genetic algorithm based approach to flexible flow-line scheduling with variable lot sizes, IEEE Transactions on Systems, Man and Cybernetics, 27 (1), 36–54, 1997.
49. F. S. Şerifoğlu and G. Ulusoy, Multiprocessor task scheduling in multistage hybrid flow-shops: a genetic algorithm approach. Journal of the Operational Research Society, 55(5), 504–512, 2004.
50. C. Oğuz and M. Ercan, A genetic algorithm for hybrid flow-shop scheduling with multiprocessor tasks. Journal of Scheduling, 8(4), 323–351, 2005.
51. F. Glover, Tabu search – Part I. ORSA Journal of Computing, 1,190–206, 1989.
52. J. W. Barnes, M. Laguna, Solving the multiple-machine weighted flow time problem using tabu search. IIE Trans, 25,121–128, 1993.
53. U. Bilge, F. Kirac, M. Kurtulan and P. Pekgun, A tabu search algorithm for parallel machine total tardiness problem. Computers and Operations Research, 31, 397–414, 2004.
54. C. O.Kim, H. J. Shin, Scheduling jobs on parallel machines: a restricted tabu search approach. International Journal of Advanced Manufacturing Technology, 22, 278–287, 2003.
55. J. Dorn, M. Girsh, G. Skele and W. Slany, Comparison of iterative improvement techniques for schedule optimization. European Journal of Operational Research, 94, 349–361, 1996.
56. M. Ben-Daya, M. Al-Fawzan, A tabu search approach for the flow shop scheduling problem. European Journal of Operational Research, 109, 88–95, 1998.
57. E. Nowicki, The permutation with flow shop buffers: a tabu search approach. European Journal of Operational Research, 116, 205–219, 1999.
58. E. Taillard, Some efficient heuristic methods for flow-shop sequencing. European Journal of Operational Research, 47, 65–74, 1990.
59. E. Taillard, Benchmarks for basic scheduling problems. European Journal of Operational Research, 64, 278–285, 1993.
60. E. Nowicki and C. Smutnicki, The flow shop with parallel machines: a tabu search approach. European Journal of Operational Research, 106, 226–253, 1998.
61. E. G. Negenman, Local search algorithms for the multiprocessor flow shop scheduling problem. European Journal of Operational Research, 128, 147–158, 1999.
62. B. Wardono and Y. Fathi, A tabu search algorithm for the multi-stage parallel machine problem with limited buffer capacities. European Journal of Operational Research, 155, 380–401, 2004.
63. N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller and E. Teller, Equation of State Calculations by Fast Computing Machines, J. of Chem. Phys., 21(6), 1087-1092, 1953.
64. P. J. M. Van Laarhoven and E. H. L. Aarts, Simulated Annealing: Theory and Practice, Kluwer, 1987.
65. J. Teghem, D. Tuyttens and E. L. Ulungu, An interactive heuristic method for multi-objective combinatorial optimization, Computers and Operations Research, 27, 621–634, 2000.
66. D. T. Pham and D. Karaboga, Intelligent optimisation techniques: genetic algorithms, tabu search, simulated annealing and neural networks. London: Springer, 2000.
67. K. Steinhofel, A. Albrecht and C. K. Wong, Two simulated annealing-based heuristics for the job shop scheduling problem, European Journal of Operational Research, 118(3), 524–548, 1999.
68. J. H. Osman and C. N. Potts, Simulated annealing for permutation flow-shop scheduling. OMEGA, 17(6), 551–557, 1989.
69. F. A. Ogbu and D. K. Smith, The application of the simulated annealing algorithm to the solution of n/m/Cmax flowshop problem. Computers and Operations Research, 17(3), 243–253, 1990.
70. F. A. Ogbu and D. K. Smith, Simulated annealing for permutation flowshop scheduling. OMEGA, 19(1), 64–67, 1990.
71. I. Hisao, M. Shinta and T. Hideo, Modified Simulated annealing algorithms for the flow shop sequencing problem. European Journal of Operational Research, 81, 388–398, 1995.
72. C. Low, Simulated annealing heuristic for flow shop scheduling problems with unrelated parallel machines. Computers & Operations Research, 32, 2013–2025, 2005.
73. V. Maniezzo and A. Carbonaro, Ant Colony Optimization: an Overview. Proceedings of MIC’99, III Metaheuristics International Conference, Brazil, 1999.
74. M. Dorigo and L. M. Gambardella, Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1(1), 53–66, 1997.
75. M. D.Besten, T. Stutzle and M. Dorigo, Ant Colony Optimization for the Total Weighted Tardiness Problem. Lecture Notes in Computer Science, 1917, 611-620, 2000.
76. V. T'kindt, N. Monmarché, F. Tercinet and D. Laügt, An Ant Colony Optimization algorithm to solve a 2-machine bicriteria flowshop scheduling problem. European Journal of Operational Research, 142(2), 250–257, 2002.
77. S. J. Shyu, B. M. T. Lin and P. Y. Yin, Application of ant colony optimization for no-wait flowshop scheduling problem to minimize the total completion time. Computers & Industrial Engineering, 47, 181–193, 2004.
78. Y. Gajpal, C. Rajendran and H. Ziegler, An ant colony algorithm for scheduling in flowshops with sequence-dependent setup times of jobs. European Journal of Operational Research, 155(2), 426–438, 2004.
79. C. Rajendran and H. Ziegler, Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs. European Journal of Operational Research, 155(2), 426–438, 2004.
80. K. Alaykýran, O. Engin and A. Döyen, Using ant colony optimization to solve hybrid flow shop scheduling problems. International Journal of Advanced Manufacturing Technology, In press. DOI 10.1007/s00170-007-1048-2, 2007.
81. K. C. Ying and S. W. Lin, Multiprocessor task scheduling in multistage hybrid flow-shops: an ant colony system approach. International Journal of Production Research, 44(16), 3161–3177, 2006.
82. T. Stützle and H. H. Hoos, MAX-MIN Ant system. Future Generation Computer Systems, 16(9), 889–914, 2000.
83. P. C. Gilmore and R. E. Gomory, A linear programming approach to cutting-stock problem. Operations Research, 9, 849-859, 1961.
84. P. H. Vance, C. Barnhart, E. L. Johnson and G. L. Nemhauser, Solving binary cutting stock problems by column generation and branch-and-bound. Computational Optimization and Applications, 3, 111-130, 1994.
85. M. Desrochers, J. Desrosiers and M. Solomon, A new optimization algorithm for the vehicle routing problem with time windows. Operations Research, 40, 342-354, 1992.
86. S. Lavoie, M. Minoux and E. Odier, A new approach for crew pairing problems by column generation with an application to air transport. European Journal of Operational Research. 35, 45-58, 1988.
87. A. Mehrotra and M. A. Trick, A column generation approach to graph coloring. Technical Report, Graduate school of Industrial Administration, Carnegie Mellon University, Pittsburgh, PA, 1993.
88. J. M. Van den Akker, J. A. Hoogeveen and S. L. Van De Velde, Parallel machine scheduling by column generation. Operations Research, 47, 862–872, 1999.
89. Z. L. Chen and W. B. Powell, Solving parallel machine scheduling problems by column generation. INFORMS Journal on Computing, 11(1), 78–94, 1999.
90. C. Y. Lee and Z. L. Chen, Scheduling jobs and maintenance activities on parallel machines. Nav Res Log, 47(2), 145–165, 2000.
91. J. M. Van den Akker, J. A. Hoogeveen and S. L. Van De Velde, Combining column generation and lagrangean relaxation to solve a single-machine common due date problem. INFORMS Journal on Computing, 14(1), 37–51, 2002.
92. P. S. Ow, Focused scheduling in proportionate flow shops. Management Science, 31, 852–869, 1985.
93. M. L. Pinedo, A note on stochastic shop models in which jobs have the same processing requirements on each machine. Management Science, 31, 840–845, (1985).
94. T. C. E. Cheng and N. Shakhlevich, Proportionate flow shop with controllable processing times. Journal of Scheduling, 2, 253–265, 1999.
95. S. S. Panwalkar, R. A. Dudek and M. L. Smith, Sequence research and the industrial scheduling problem. In S. E. Elmaghraby (ed.), Proc. Symp. on the theory of scheduling and its applications (pp. 29–37). Berlin/New York: Springer, 1973.
96. S. Hou and H. Hoogeveen, The three-machine proportionate flow shop problem with unequal machine speeds. Operations Research Letters, 31(3), 225–231, 2003.
97. A. Estevez-Fernandez, M. A. Mosquera, P. Borm and H. Hamers, Proportionate flow shop games. Tilburg University, Center for Economic Research, 2006.
98. N. V. Shakhlevich, H. Hoogeveen and M. L. Pinedo, Minimizing total weighted completion time in a proportionate flow shop. Journal of Scheduling, 1, 157–168, 1998.
99. A. Allahverdi, Two-machine proportionate flowshop scheduling with breakdowns to minimize maximum lateness. Computers and Operations Research, 23(10), 909–916, 1996.
100. A. Allahverdi and M. Savsar, Stochastic proportionate flowshop scheduling with setups. Computers & Industrial Engineering, 39(3), 357–369, 2001.
101. B. C. Choi, S. H. Yoon and S. J. Chung, Minimizing the total weighted completion time in a two-machne proportionate flow shop with different machine speeds. International Journal of Production Research, 44(4), 715–728, 2006.
102. B. C. Choi, S. H. Yoon and S. J. Chung, Minimizing maximum completion time in a proportionate flow shop with one machine of different speed. European Journal of Operational Research, 176(2), 964–974, 2007.
103. Y. P. Pan and L. Y. Shi, Dual constrained single machine sequencing to minimize total weighted completion Time. IEEE Transactions on Automation Science and Engineering, 2(4), 344–357, 2005.
104. W. E. Smith, Various optimizers for single-stage production. Nav Res Log Quart, 3, 59–66, 1956.
105. M. E. Lübbecke and J. Desrosiers, Selected topics in column generation. Operations Research, 53(6), 1007–1023, (2005).
106. John H. Holland, Building blocks, Cohort Genetic Algorithms, and Hyperplane-Defined Functions. Evolutionary Computation, 8(4), 373–391, 2000.
107. D. E. Goldberg, B. Korb and K. Deb, Messy genetic algorithm: Motivation, analysis, and first results. Complex Systems, 3, 493–530, 1989.
108. D. E. Goldberg, K. Deb, H. Kargupta and G. Harik, Rapid, accurate optimization of difficult problems using fast messy genetic algorithm. IlliGAL Rpt No. 93004, Illinois Genetic Algorithm Lab., Dept of General Engineering, University of Illinois, Urbana, 1993.
109. A. C. M. de Oliveira and L. A. N. Lorena, A constructive genetic algorithm for gate matrix layout problems. IEEE T Comput Aid, 21, 969–974, 2002.
110. L. A. N. Lorena and J. C. Furtado, Constructive genetic algorithm for clustering problems. Evolutionary Computation, 9(3), 309–327, 2001.
111. G. Ribeiro and L. A. N. Lorena, A constructive evolutionary approach to school timetabling. Lecture Notes in Computer Science, 2037, 130 –139, 2001.

------------------------------------------------------------------------ 第 8 筆 ---------------------------------------------------------------------
系統識別號 U0026-0812200915080143
論文名稱(中文) 建構半導體封裝廠銲線製程機台排程系統
論文名稱(英文) Construction of Machine Allocation Program for Semi-conductor Assembly Wire Bond Process
校院名稱 成功大學
系所名稱(中) 工學院工程管理碩士在職專班
系所名稱(英) Institute of Engineering Management
學年度 97
學期 2
出版年 98
研究生(中文) 張冠姿
學號 N0795121
學位類別 碩士
語文別 中文
口試日期 2009-05-15
論文頁數 67頁
口試委員 指導教授-陳家榮
口試委員-顏榮祥
口試委員-劉春初
關鍵字(中) VBA
生產排程
銲線製程
封裝
半導體
關鍵字(英) VBA
Process Scheduling
Wire Bond Process
Assembly
Semiconductor
學科別分類
中文摘要 台灣半導體產業一直是推升我國經濟發展的核心產業,我國半導體產業隨著全球市場成長而蓬勃發展,至今產業結構已相當完整,展現受國際矚目之亮眼成績。台灣半導體產業經二十年辛苦耕耘與不斷研發創新,現今已在全球半導體市場佔有一席之地。

現今半導體封裝面臨產品生命週期縮短,客戶新產品不斷地推陳出新,以及客戶訂單之不確定性等原因下,為了持續提昇競爭優勢,對外,提供客戶在品質與交期方面更快更好的服務,配合客戶出貨需求;對內,生產線在有限的生產規模下,如何機動地調派以因應訂單需求做出適當生產排程,進一步使得機台生產利用率提昇並減少人力成本浪費,成為當前刻不容緩的一項課題。

本研究根據相關文獻及半導體封裝廠實際生產排程的瞭解,針對半導體封裝製程之瓶頸站-銲線製程,探討引腳型塑膠封裝產品之生產排程,應用Excel巨集和VBA程式,建構銲線機台生產排程系統於公司內部網路平台,以替代原來耗時良久的人工計算方式,並提供管理階層相關報表以掌握即時狀況。爾後藉由資料的蒐集與回饋,分析是否達到預期效益並做修正。希望藉此一排程系統產出最適切的排程安排,期以節省公司內部成本並且符合客戶出貨需求。

將本研究方法實際運用於個案公司,結果顯示此銲線機台排程系統除了可替代人工計算方式及提供相關管理報表參照,更可降低產品換貨頻率並提昇機台平均產量。這些顯著之成效表示本研究所建構之排程系統能有助於半導體封裝廠銲線機台之排程問題。
英文摘要 The semiconductor industry has helped advanced the economic development growth in Taiwan. With the rising demand of semiconductors in the world market, Taiwan’s semiconductor products have been accepted globally and its industry has gained world attention. After twenty years of extensive and continuous research on the industry, Taiwan has achieved a small space in the global semiconductor market.

With the present situation of shorter production time, new products entering the market and unstable orders, Taiwan semiconductor producers need to provide customers a higher product quality and quick delivery time to compete with other producers. Internally, companies should establish how to cope up with an efficient delivery schedule and enhance the maximum production of machines to reduce labor cost.

This research is based on related data and production process of semiconductor assembly plants. The data focuses on, bottleneck wire bond station to the scheduling of the lead type plastic packaging, applying EXCEL and VBA program to establish wire bond machine connected to the intranet of the company to establish an automated calculation data from the production and provide management on time reports. Not only is this process time saving but it also provides accurate calculations and lowers internal cost, it also gives management more time to analyze different situations on the production.

This proposed approach is applicable for semiconductor assembly plants. Wire bond machine scheduling can replace manual calculation and provide related reports and increase the production efficiency. This significant result shows that wire bond machine process scheduling has a strong effect in this research.
論文目次 摘 要 I
ABSTRACT II
誌 謝 III
目 錄 IV
表目錄 VII
圖目錄 IX
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 4
1.3 研究範圍與假設 4
1.4研究內容與流程 5
第二章 文獻探討 6
2.1生產排程 6
2.2排程理論 6
第三章 半導體封裝作業簡介 15
3.1 塑膠封裝之目的 15
3.2 半導體封裝作業流程 15
3.3 半導體封裝產業特性 23
3.3.1 半導體封裝產業特性 23
3.3.2 封裝廠生產系統 24
3.3.3 封裝廠生產流程 25
第四章 銲線機台作業分析與排程系統建構 27
4.1接單模式與生產管理 27
4.1.1 接單模式 27
4.1.2 訂單與產能管理 28
4.2 作業現場描述 29
4.3 銲線製程與排程 31
4.3.1 銲線製程說明 31
4.3.2 現行排程方式 32
4.4 排程方法比較 34
4.4.1 先進先出法(FIFO) 35
4.4.2 最短加工時間法(SPT) 35
4.4.3 最長加工時間法(LPT) 36
4.4.4 最早到期日法(EDD) 36
4.4.5 線性規劃 37
4.5 排程系統建構 39
4.5.1 Visual Basic Application 39
4.5.2 管理階層報表 39
4.5.3 建構排程系統 42
第五章 排程系統應用結果分析 46
5.1 現況說明 46
5.2 差異分析 46
5.2.1 整體機台效益 46
5.2.2 機台數量 50
5.2.3 操作機台人員數量 52
第六章 結論與建議 53
6.1結論 53
6.2 建議 54
參考文獻 55
附 錄 58
參考文獻 中文部份
1.中山清孝,直傳豐田方式,財團法人中衛發展中心,台北,2006。
2.王國銉,液晶面板驅動IC內引腳接合製程生產排程支援系統建構,成功大學工程管理碩士在職專班碩士論文,2007。
3.佘溪水,生產管理,中興管理顧問公司,台北,1989。
4.宋身元,淺談排程系統設計之相關要素,機械工業雜誌,台北,1993。
5.李嘉柱,半導體後段廠之現場生產流程與作業管制條件分析辦法探討,機械工業雜誌,台北,1999。
6.李英明,半導體封裝廠交期即時協調和生產排程模式研究,中華大學工業工程與管理研究所碩士論文,2000。
7.阮永漢,系統模擬與基因演算法於完全相同機台排程之應用,元智大學工業工程與管理學系碩士論文,2002。
8.邱俊斌,半導體廠設備綜合效力之探討-以半導體測試廠為例,成功大學工業與資訊管理學系碩士班碩士論文,2006。
9.林安祥,開放工廠總加權延遲最小化排程問題之研究,朝陽大學工業工程與管理系碩士論文,2000。
10.洪文章,晶圓廠之限制驅導式兩階段生產排程的應用─求最適當週期時間,中華大學工業工程與管理研究所碩士論文,2000。
11.桂思強,Visual Basic 6 資料庫開發聖經,學貫行銷股份有限公司,台北,2004。
12.許浚鳴,封裝廠植球區之雙機台排程模式,成功大學工程管理碩士在職專班碩士論文,2005。
13.黃信榮,記憶體IC最終測試廠主生產規劃系統之建構,交通大學工業工程與管理系碩士論文,2003。
14.曾信傑,應用模糊類神經派工法於晶圓製造廠之研究,國立台北科技大學生產系統工程與管理研究所碩士論文,2000。
15.傅和彥,生產與作業管理,前程企業管理有限公司,台北,1999。
16.莊達人,基礎IC技術 - 應用、設計與製造,全威圖書有限公司,台北,2006。
17.莊文化,應用基因演算法於彈性流程型工廠排程之研究,成功大學工業與資訊管理學系碩士班碩士論文,2006。
18.楊士賢,半導體封裝之排程支援系統,逢甲大學工業工程學系碩士論文,2001。
19.楊橙坤,具時間限制之穩定性專案基線排程研究,成功大學資訊管理學研究所碩士論文,2008。
20.熊鴻鈞,螞蟻族群演算法於生產排程之應用,暨南國際大學資訊管理學系碩士論文,2003。
21.潘俊明,生產與作業管理,三民書局股份有限公司,台北,1995。
22.蔡瑜明,半導體後段IC封裝最適排程之研究─禁忌搜尋法之應用,中山大學企業管理學系研究所碩士論文,2003。
23.鍾文仁,IC封裝製程與CAE應用,全華科技圖書股份限公司,台北,2005。
24.顧志文譯,生產與作業管理,台灣西書出版社,台北,1997。


英文部份
1.Baker, K.R. (1974), 'Introduction to Sequencing and Scheduling', Johen Wiley & Sons, Inc..
2.Conway, R.W., et al. (1967), 'Theory of Scheduling', Dover Publications.
3.Frederick S. Hiller and Gerald J. Lieberman (2005), ' Introduction to Operations Research', McGraw-Hill Companies, Inc.
4.Graves, S.C. (1983), 'Scheduling of Re-Entrant Flow Shops', Journal of Operations Management, Vol. 3, No. 4, pp. 197-207.
5.Lenstra, J. K. and A. H. G. Rinnooy Kan (1976), 'On General Routing Problem', Network, Vol. 6, pp. 273-280.
6.Lou, S. X. C. and Kager, P.W. (1989), 'A Robust Production Control Policy for VLSI Wafer Fabrication', IEEE Transaction on Semiconductor Manufacturing, Vol. 2, No. 4, pp.159-164.
7.Pinedo, M. (1995), 'Scheduling Theory', Algorithm, and Systems, Prentice Hall.
8.Pillutla, S. N. and Nag. B.N. (1996), 'Object-oriented modle construction in production scheduling decisions', Decision Support System, Vol. 18, pp. 357-375.

 


如您有疑問,請聯絡圖書館
聯絡電話:(06)2757575#65773
聯絡E-mail:etds@email.ncku.edu.tw