天車排程問題的研究 –以印刷電路板自動電鍍線為例

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：27

、訪客IP：18.188.18.32

姓名

簡煜國(Yu-kuo Chien) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

天車排程問題的研究 –以印刷電路板自動電鍍線為例
(hoist scheduling problem-HSP)

相關論文

★ 佈置變更專案工程的執行研究－以H公司研發單位為例	★ MIL-STD-1916、MIL-STD-105E與結合製程能力指標之抽樣檢驗計畫
★ 建構客戶導向的製造品質資訊系統--以某筆記型電腦專業代工廠商為例	★ GMP藥廠設施佈置規劃的探討--以E公司為研究對象
★ 應用Fuzzy c-Means演算法之物流中心位址決策模式研究	★ 品質資訊系統之規劃與建構 -- 以某光碟製造公司為研究對象
★ 從製程特性的觀點探討生產過程中SPC管制圖監控運用的適切性 -- 以Wafer Level 封裝公司為例	★ 六標準差之應用個案研究-以光學薄膜包裝流程改善為例
★ 利用六標準差管理提昇中小企業之製程品質-以錦絲線添加防銹蠟改善為例	★ 專業半導體測試廠MES 系統導入狀況、成果及問題之探討-以A 公司為例
★ 以RFID技術為基礎進行安全管理導入－以A公司為例	★ 如何提昇產品品質及降低成本—以光碟壓片廠A公司為例
★ ERP導入專案個案分析—以半導體封裝廠A公司為例	★ 石英元件製造業之延遲策略應用— 以T公司為研究對象
★ 十二吋晶圓廠自動化搬運系統規劃與導入—以A公司為例	★ 半導體封裝產業之生產革新改善活動-A半導體股份有限公司導入經驗探討-

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

全自動化生產單元 ( Fully Automatic Manufacturing Cells， Crama et al 2000 ) 由自動化加工設備及自動化搬運系統(機器手臂、天車….)所構成，已經成為製造系統中常見的生產設備，生產單元內自動搬運系統的效率與整個系統的效率息息相關，而加工設備與搬運設備間密不可分的關係及其複雜的交互作用更導致除了硬體設計外，自動化程式在設計上的困難性。
在眾多考慮到自動搬運系統的問題 ( 包括Robotic Cell Scheduling 、Scheduling of AGV ) 中，天車排程問題 ( Hoist Scheduling Problem-HSP， Phillips and Unger 1976) 或吊車排程問題( Crane Scheduling Problem， Lieberman and Turksen 1981 ) 是受限最多的問題 ( Crama 1997 ) 。這個問題已經由Lei證明其NP hardness ( Lei and Wang 1989 ) 。尤其在絕大多數實際上運用的系統均是採用〝非正式〞的方法，依經驗以嘗試錯誤法來獲得解決。通常需要花上數日的嘗試並配合實際硬體加以測試，才能獲得可接受的結果。
目前多數對於自動化表面處理線『天車排程問題』的研究均集中於在單一天車、單一產品的環境下，以事前規劃的方式，求得產能最佳化的天車行程。但實際系統通常運用多部天車同時運作，而且這種針對單一產品所規劃的行程會遭遇到以下三種主要的問題：(1)單一生產線只能生產單一規格的產品; (2)在某些無法完全避免的機械故障的情況下(如某一天車或某處理槽故障)，形成原規劃天車行程無法應變，而造成大量產品報廢的情形。(洪瑞炫 2002) (3) 先前的研究(Mak et al 2002)指出多部天車間部份搬運區的重疊(overlapping)可能可以提昇天車的搬運效率，但未有進一步的結論。故此研究的目的在討論能彈性反應系統動態，在上述情境發生的狀況下，能作為靜態天車行程規劃外可供切換的「天車指派法則」。
至於控制結果的分析方式，對於單一天車系統，Phillips and Unger (1976)，Shapiro and Nuttle (1988) 等提出之實例已經成為過去許多研究的標準測試例題(Benchmarks)，但對於多部天車的研究或實例卻相當少，本研究所討論的即時控制方法，將以Mak et al.(2002)所提出的案例加以研究分析。

摘要(英)

There are a lot of researches which consider scheduling and control of automated material handling systems, including robotic cell scheduling、scheduling of automated guided vehicle and so on. Among these problems, the hoist scheduling problem-HSP or crane scheduling problem is the most restricted one (Crama 1999). And it was proved to be NP-hardness in the class of this problem by Lei and Wang (1989). Most of the systems installed are designed by experienced experts using trail-and-error based techniques. The fixed schedule derived by trial-and error must be validated with an actual system and usually it takes several days to correct some unexpected errors in the original design.
The previous study about the HSP in automated surface treatment lines mainly focus on single hoist、single product type environment. A fixed hoist schedule for maximum through-put was considered before the operation. The difference between previous case studied and actual systems is: real systems are usually composed by several hoists, and it will encounter three difficulties with a fixed schedule design: (1)the system could only operate with one product type at one time (2)it will not work if one of the hoist fails. Therefore there will be lots of scrap products if only one hoists fails(3)a previous study (Mak 2002) suggest that adding overlapping zones between hoists movement could be beneficial to material handling efficiency but no further conclusion.
The purpose of this study is to develop an efficient hoist dispatching rule that deal with above scenarios in a automated electroplating line. To analyze the performance of different approaches, some of the single hoist cases are discussed extensively by many researchers. For example, the cases provided by Phillips and Unger(1976)、Shapiro and Nuttle(1988). And these cases already become benchmark problems in this field. But it is rare to study a multi-hoist system. We will use the multi-hoist case provided by Mak(2002) to study the performance of our rule.

關鍵字(中)

★ 天車

關鍵字(英)

★ HSP

論文目次

第一章緒論 1
1.1 研究動機與目的 1
1.2 研究內容與範圍 12
1.3 論文架構 17
第二章相關資料及文獻回顧 19
2.1 緒論 19
2.2 Time-Way 圖 19
2.3 『天車排程問題』相關文獻回顧 28
2.4 自動無人搬運車派車法則相關文獻 35
2.5 模擬分析 38
2.5.1 模擬的理論基礎及適用範圍 38
2.5.2 模擬的分類 41
2.5.3 離散事件模擬系統的分類與演進 42
2.5.4 SIMAN/ARENA模擬語言簡介 44
第三章系統分析與研究方法 46
3.1 前言 46
3.2 天車派送法則 46
3.3 模擬輸出資料分析理論(Law and Kelton，2000) 60
第四章實驗設計與分析 65
4.1 實驗環境 65
4.2 模擬實驗分析 69
4.3 統計分析與實驗結果 74
4.3.1 平均工件完成數之統計分析 78
4.3.2 平均工件流程時間之統計分析 81
4.3.3 天車利用率之統計分析 84
4.3.4 延遲工件數之統計分析 85
第五章結論與建議 88
5.1 結論 89
5.2 後續研究建議 90
圖目錄
圖1-1 機械手臂排程問題(Hall，1998) 2
圖1-2 半導體廠之無人搬運車(http://www.daifuku.com) 2
圖1-3 FMS無人搬運車軌道系統(Montazeri，1990) 3
圖1-4 多載量無人搬運車軌道系統(洪碧涓，2000) 3
圖1-5 自動電鍍線控制面板 4
圖1-6 自動表面處理線示意圖 I 5
圖1-7 自動表面處理線示意圖 II 5
圖1-8. 實際自動電鍍生產線 6
圖1-9 印刷電路板製程(經濟部2002電子工業年鑑，2002) 9
圖1-11 半導體製程示意圖 11
圖1-12 電鍍掛架循環示意圖 14
圖1-13 天車排程問題分類圖1 (Bloch，1999) 15
圖1-14 天車排程問題分類圖2(Bloch，1999) 15
圖1-15 天車排程問題分類圖3(Bloch，1999) 16
圖1-16 天車排程問題分類圖4(Bloch，1999) 16
圖1-17 研究流程 18
圖2-1 一簡單Time-Way圖 19
圖2-2 包含上下工件時間的Time-Way 圖 20
圖2-3 如何以天車運行軌跡產生Time-Way圖(Lei，1991) 21
圖2-4 原始Time-Way圖線段(Heselton，1986) 22
圖2-5 錯誤的Time-Way圖(Heselton，1986) 23
圖2-6 重新調整後的Time-Way圖線段(Heselton，1986) 23
圖2-7 正確的Time-Way圖(Heselton，1986) 24
圖2-8 行程過長的Time-Way 圖(Matile，1999) 25
圖2-9 不符合時限規定的Time-Way 圖(Matile，1999) 26
圖2-10 符合時限規定且行程短的Time-Way 圖(Matile，1999) 26
圖2-11 一典型的Time-Way圖(Mak，2002) 27
圖2-12 複雜的Time-Way 圖(Matile，1999) 27
圖2-13 n-Cycle排程規劃(Kats，1999) 29
圖2-14 One(Simple) Cycle排程規劃(Kats，1999) 29
圖2-15 周期循環式的行程規劃(Che，2002) 31
圖2-16 Thesen and Lei (1986)所建立之模擬系統1 32
圖2-17 Thesen and Lei (1986)所建立之模擬系統2 32
圖2-18 模擬的基本架構 39
圖2-19 回饋式評估模式 40
圖3-1 工件流程圖 47
圖3-2 無合作區域(上)與(下)具有合作區域的系統(Varnier，1997) 50
圖3-3 天車控制系統圖(鍾含智，2000) 53
圖3-4 工件處理時限示意圖 54
圖3-5 天車運行中可能產生衝突的情況(Manier，2000) 57
圖3-6 以時間差的方式避免天車間的衝突(Manier，2000) 58
圖3-7 MTLSD派車法則流程圖 59
圖3-8 移動平均說明圖(重覆n次，實驗長度為m) 62
圖3-9 平均每小時工件生產量圖 63
圖3-10 w=20之移動平均圖 63
圖3-11 w=30之移動平均圖 64
圖4-1 工件的製程順序 68
圖4-2 模擬程式畫面 69
圖4-3 常態機率圖 75
圖4-4 殘差圖 76
圖4-7 派車方式與車速對平均流程時間影響圖 83
圖4-8 派車方式與合作槽數對平均流程時間影響圖 83
表目錄
表1-1 印刷電路板製程設備(經濟部2002電子工業年鑑，2002) 7
表2-1 七個處理槽的處理順序及時限(Matile，1999) 25
表3-1 常見之無人搬運車派車法則(王志宏，1993) 52
表3-2 Duplicate Tanks之範例 (林世堂，2000) 56
表4-1 處理槽佈置順序及處理時限 66
表4-2 各因子的水準(Level)表 70
表4-3平均完成工件數 70
表4-4工件平均流程時間 71
表4-5天車平均利用率實驗結果 72
表4-6平均延遲工件數實驗結果 73
表4-7 單一樣本K-S檢定 74
表4-8 Hartley變異數齊一性檢定法 75
表4-9工件完成數之ANOVA表 78
表4-10 三個因子之Duncan檢定（工件完成數） 79
表4-11平均流程時間之ANOVA表 81
表4-12 三個因子之Duncan檢定（工件平均流程時間） 82
表4-13 天車利用率之ANOVA表 84
表4-14 三個因子之Duncan檢定（天車利用率） 85
表4-15 延遲工件數之ANOVA表 86
表4-16 三個因子之Duncan檢定（延遲工件數） 86

參考文獻

Armstrong, R., Gu, S., and Lei, L., 1996, “A greedy algorithm to determine the number of transporters in a cyclic electroplating process”, IIE Transactions, 28, 347-355.
Armstrong, R., Lei, L., and Gu, S., 1994, "Abounding scheme for deriving the minimal cycle time of a single-transporter N-stage process with time-window constraints", European journal of Operational research, 78, 130-140.
Banks, J., Carson, J. S., Nelson, B. L., and Nicol, D. M., 2000, Discrete Event System Simulation, 3rd Ed., Upper Saddle River, New Jersey, Prentice-Hall.
Baptiste, P., Legeard, B., and Varnier, C., 1992, "Hoist scheduling problem: An approach based on constraint logic programming", Proceedings of the 1992 IEEE International Conference on Robotics and Automation, 2, Nice, France, 1139-1144.
Bloch, C., and Manier, M.-A., 1999, “Notation and typology for the hoist scheduling problem”, IEEE International Conference on Systems, Man, and Cybernetics, 6, 475-480.
Che, A., Chu, C., and Chu, F., 2002, “Multicyclic hoist scheduling with constant processing times”, IEEE Transactions on Robotics and Automation, 18(1), 69-80.
Chen, H., Chu, C., and Proth, J. M., 1998, "Cyclic scheduling of a hoist with time window constraints", IEEE Transactions on Robotics and Automation, 14(1), 144-152.
Chen, H., Chu, C., and Proth, J.-M., 1995, “Cyclic hoist scheduling based on graph theory”, INRIA/IEEE Symposium on Emerging Technologies and Factory Automation, 1, 451-459.
Cheng, T. C. E. , 1987, ”A Simulation Study of Automated Guided Vehicle Dispatching”, Robotics and Computer-Integrated Manufacturing, 3(3), 335-338.
Crama, Y., 1997, “Combinatorial optimization models for production scheduling in automated manufacturing systems”, European Journal of operational research, 99, 136-153.
Crama, Y., Kats, V., van de Klundert, J., and Levner, E., 2000, “Cyclic scheduling in robotic flowshops”, Annals of Operations Research, 96, 97-124.
Egbelu, P. J. , 1987, ” Pull Versus Push Strategy for Automated Guided Vehicle Load Movement in a Batch Manufacturing System”, Journal of Manufacturing System, 6(3), 271-280.
Egbelu, P. J. and Tanchoco, 1984, J. M. A., ” Characterization of Automated Guided Vehicle Dispatching Rules”, International Journal of Production Research, 22(3),359-374.
Egbelu, P. J., and Roy, N.,1988, “Material flow control in AGV/unit load based production lines”, International Journal of Production Research, 26, 81-94.
Fleury, G., Gourgand, M., and Lacomme, P., 2001, “Metaheuristics for the stochastic hoist scheduling problem (SHSP)”, International Journal of Production Research, 39(15), 3419-3457.
Ganesharajah, T., Hall, N. G., and Sriskandarajah, C., 1998, “Design and operational issues in AGV-served manufacturing systems”, Annals of Operations Research, 76, 109-154.
Grasso, V., 1990, “AGV-served assembly lines: influence of sequencing and launch policies on system performances”, International Journal of Production Research, 28, 157-166.
Hall, N. G., Kamoun, H., and Sriskandarajah, C., 1998, "Scheduling in robotic cells: Complexity and steady state analysis", European Journal of Operational Research, 109, 43-65.
Heselton, M.O., 1984, “Movement sequence of automated plating plant and transporters with computer-aided design”, Workstudy, Feb-Mar
Hwang, H. and Kim, 1998, S. H., ” Development of Dispatching Rules for Automated Guided Vehicle Systems”, Journal of Manufacturing System, 17(2), 137-143.
Hwang, H. and Kim, 1999, S. H., ”An Adaptive Dispatching Algorithm for Automated Guided Vehicles Based on an Evolutionary Process”, International Journal of Production Economics, 60, 465-472.
Kats, V., Levner, E., and Meyzin, L., 1999, “Multiple-part cyclic hoist scheduling using a Sieve method”, IEEE Transactions on Robotics and Automation, 15(4), 704-713.
Klein, C. M. and Kim, 1996, J., ”AGV Dispatching”, International Journal of Production Research, 34(1), 95-110.
Law, A M., and Kelton, W. D., 2000. Simulation Modeling and Analysis, 3rd Ed., New York, McGraw Hill.
Lei, L., and Wang, T.-J., 1989, "A proof: The cyclic hoist scheduling problem is NP-complete", Working paper, No.89-16. Rutgers University.
Lei, L., and Wang, T.-J., 1991, "The minimum common-cycle algorithm for cyclic scheduling of two material handling hoists with time windows constraints", Management Science, 37(12), 1629-1639.
Lei, L., and Wang, T.-J., 1994, "Determining the optimal cyclic hoist schedules in a single-hoist electroplating line", IIE Transactions, 26(2), 25-33.
Liang, T. P., Moskowitz, H., and Yih, Y., 1992, "Integrating neural networks and semi-Markov processes for automated knowledge acquisition: An application to real-time scheduling", Decision Science, 23, 1297-1314.
Lieberman, R. W. and Turksen, I. B., 1981, “Crane scheduling problem”, IIE Transactions, 13(4), 304-311.
Liu, C. M., and Duh, S. H., 1992, ”Study of AGVS Design and Dispatching Rules by Analytical and Simulation Methods”, International Journal of Computer Intergrated Manufacturing, 5(4), 290-299.
Mak, R. W., Gupta, M. A., and Lam, K., 2002, “Modeling of material handling hoist operations in a PCB manufacturing facility”, Journal of Electronics Manufacturing, 11(1), 33-50.
Manier, M. A., Varnier, C., and Baptiste, P., 2000, "Constraint-based model for the cyclic multi-hoists scheduling problems", Production Planning and Control, 11(3), 244-257.
Matile, G. E., Tettamanzi, A. G. B., and Tomassini, M., 1999, “Evolution design of Time-Way chart for Plating machines”, Proceedings of the 1999 Congress on Evolutionary Computation, 2, 1178-1185.
Matsuo, H., Shang, J. S., and Sullivan, R. S., 1991, "A crane scheduling problem in a computer-integrated manufacturing environment", Management Science, 37(5), 587-606.
Montazeri, M. and Van Wassenhove, L. N., 1990, "Analysis of Scheduling rules for an FMS", International Journal of Production Research, 28(4), 785-802.
Ng, W. C., and Leung, J., 1997, “Determing the optimal move times for a given cyclic schedule of a material handling hoist”, Computers in Industrial Engineering, 32(3), 595-606.
Pedgen, C. D., Shannon, R. E. and Sadowski, R. P., 1995, Introduction to Simulation Using SIMAN, 2nd Ed., New York, Mcgraw Hill.
Phillips, L. W., and Unger, P. S., 1976, "Mathematical programming solution of a hoist scheduling progam", IIE Transactions, 8(2), 219-225.
Shapiro, G. W., and Nuttle, H. L. W., 1988, "Hoist scheduling for a PCB electroplating facility", IIE Transactions, 20(2), 157-167.
Song, W., Storch, R. L., and Zabinsky, Z. B., 1995, “An example for scheduling a chemical processing tank line”, Production Planning and Control, 475-482.
Sun, T. C., Lai, K. K., and So, K. P., 1994, "A study of heuristics for bi-directional multi-hoist production scheduling system", International Journal of Production Economics, 33, 207-214.
Thesen, A., and Lei, L., 1986, "An expert system for scheduling robots in a flexible electronic system with dynamically changing workloads", Proceedings of the Second ORSA/TIMS Conference on Flexible Manufacturing Systems: Operations Research Models and Applications, 555-566.
Thesen, A., and Lei, L., 1990, "An expert scheduling system for material handling hoists", Journal of Manufacturing Systems, 9(3), 247-252.
Thesen, A., Yih, Y., and Lei, L., 1987, "Knowledge acquisition methods for expert scheduling systems", 1987 Winter Simulation Conference Proceedings, 709-714.
Varnier, C., Bachelu, A., and Baptiste, P., 1997, “Resolution cyclic multi-hoists scheduling problem with overlapping partitions”, INFOR, 35(4), 309-324.
Yih, Y., 1990, "Trace-driven knowledge acquisition (TDKA) for rule based real time scheduling systems", Journal of Intelligent Manufacturing, 217-230.
Yih, Y., 1992, “Learning real-time scheduling rules from optimal policy of semi-Markov decision process”, International Journal of Computer Integrated Manufacturing, 5(3), 171-181.
Yih, Y., 1994, “An algorithm for hoist scheduling problem”, International Journal of Production Research, 32(3), 501-516.
Yih, Y., and Thesen, A., 1991, "Semi-Markov decision models for real-time scheduling", International Journal of Production Research, 29(11), 2331-2346.
Yim,D. S. and Linn, R. J. , 1993, ” Push and Pull Rules for Dispatching Automated Guided Vehicles in a Flexible Manufacturing System”, Internal Journal of Production Research, 31(1), 43-57.
王志宏，1993，”無人搬運車系統之智慧型派車機構之研究”，清華大學工業工程研究所碩士論文。
林世堂，2000，”印刷電路板現場監控系統之物件導向分析與設計”，交通大學機械工程研究所碩士論文。
洪瑞炫，2002，”溼式清洗機台不延遲作業排程”，清華大學工業工程研究所碩士論文
洪碧涓，2002，"多負載無人搬運車之控制策略", 交通大學工業工程與管理研究所博士論文.
鍾含智，2000，”電路板一次銅電鍍生產線吊車控制模擬系統”，元智大學機械工程研究所碩士論文。

指導教授

何應欽(Y-C Ho)

審核日期

2003-7-16

推文