臺灣博碩士論文加值系統

非等效平行機台在製造現場是常見的一個情形，工廠為了加快產品的生產速度或是解決瓶頸機台的問題，常會添購具有相同處理功能的新機台，由於機台間製程能力相仿但加工效率不同，在排程上便產生了許多的問題，因為效能的不同，適當的機台生產組合可有效地減少產品加工時間、機台整備次數、提升生產力並能符合交期。
工件分割的用意在於利用不同的機台加工同一筆工件，使其得以在交期內準時完工。因此，若工件分割的太少就會造成工件的延遲，使得成本上升；若工件分割的適當時，則可有效的在交期內完成加工作業，使排程總成本得以最小化。
本研究以PCB製程中的鑽孔作業為例，探討非等效平行機台在排程時面對工件分割、優先權與整備時間的限制下如何使延遲損失與加工機台成本最小化。本研究提出工件分割準則，使得排程求解時間與LINGO求取最佳解相比得以大幅降低，透過塔布搜尋法改善後可達到穩定且不錯的解。

Unrelated parallel machines are often seen in the shop floor. For accelerating production rate or to ease the workload of bottleneck machine, new similar machines are acquired. The production capabilities of the parallel machines are similar but production rates are not totally equivalent. Owing to the differences, how to sequence the parallel machines are important not only to effectively reduce the cycle times, numbers of changeovers but also to promote the utility and meet the due-dates.
The purpose of dividing the part is to distribute the divided parts onto the parallel machines for meeting the due-date. Therefore few numbers of divided parts leads to tardiness and high penal cost. If the numbers of divided parts is appropriate, the part will be processed with the minimized total cost.
In this research, we investigate the unrelated parallel machine scheduling problem of drilling operations in PCB factory. Tabu search is applied to minimize the tardiness and production costs of machines under the considerations of part-dividing, priorities, and setup times. It finally leads to satisfactory and stable results.

第一章 緒論………………………………………………………… 1
1.1 研究背景……………………………………………………… 1
1.2 研究動機……………………………………………………… 2
1.3 研究範圍與目的……………………………………………… 2
1.4 研究方法……………………………………………………… 2
1.5 論文架構與流程……………………………………………… 3
第二章 文獻探討…………………………………………………… 5
2.1 鑽孔製程介紹………………………………………………… 5
2.1.1 上插梢作業……………………………………………… 6
2.1.2 鑽孔……………………………………………………… 6
2.1.3 下插梢檢查及品質檢查重點…………………………… 7
2.2 PCB 產業相關文獻…………………………………………… 8
2.3 非等效平行機台相關文獻…………………………………… 9
2.3.1 塔布搜尋法(Tabu Search) …………………………… 10
2.3.2 模擬退火法(Simulated Annealing) ………………… 10
2.3.3 基因演算法(Genetic Algorithm) …………………… 11
2.4 塔布搜尋法求解其他排程問題相關文獻…………………… 14
第三章 問題定義…………………………………………………… 15
3.1 前言…………………………………………………………… 15
3.2 鑽孔作業現況………………………………………………… 15
3.3 問題描述……………………………………………………… 16
3.4 研究範圍……………………………………………………… 19
3.5 問題限制與假設……………………………………………… 19
3.6 問題架構與模式……………………………………………… 20
3.6.1 模式彙總………………………………………………… 22
3.6.2 模式驗証………………………………………………… 24
第四章 研究方法…………………………………………………… 28
4.1 塔布搜尋法簡介……………………………………………… 28
4.1.1 塔布搜尋法的組成要素………………………………… 28
4.1.2 塔步搜尋法的演算步驟………………………………… 30
4.1.3 塔布搜尋法演算範例…………………………………… 33
4.2 塔布搜尋法參數設定………………………………………… 35
4.3 排程限制規範………………………………………………… 37
4.3.1 解集合的探討…………………………………………… 37
4.3.2 機台指派………………………………………………… 38
4.3.3 料號延遲之排程準則…………………………………… 40
4.3.4 料號分割與指派流程…………………………………… 40
第五章 排程系統設計……………………………………………… 50
5.1 資訊需求……………………………………………………… 50
5.2 系統設計……………………………………………………… 52
第六章 實例驗証分析……………………………………………… 54
6.1 與最佳解比較…………………………………………………… 54
6.1.1 待排料號與排程求解之關係…………………………… 57
6.1.2 機台數量與排程求解之關係…………………………… 60
6.1.3 料號最大分割數與排程求解之關係…………………… 63
6.2 與實際排程比較………………………………………………… 65
6.2.1 實際排程數據1 ………………………………………… 65
6.2.2 實際排程數據2 ………………………………………… 67
6.2.3 實際排程數據3 ………………………………………… 69
6.2.4 實際排程數據4 ………………………………………… 72
6.2.5 實際排程數據5 ………………………………………… 74
6.2.6 實際排程數據6 ………………………………………… 76
6.2.7 實際改善成果…………………………………………… 79
第七章 結論………………………………………………………… 80
7.1 分割之重要性………………………………………………… 80
7.2 本研究方法特性與貢獻……………………………………… 80
7.3 後續發展與建議……………………………………………… 81
參考文獻……………………………………………………………… 82
圖 目 錄
圖1.1 全球印刷電路板應用領域分配圖…………………………… 1
圖1.2 研究架構流程圖……………………………………………… 4
圖2.1 鑽孔物料示意圖……………………………………………… 6
圖3.1 現行鑽孔排程流程圖………………………………………… 18
圖3.2 範例1 最佳排程圖…………………………………………… 25
圖3.3 範例2 最佳排程圖…………………………………………… 26
圖4.1 塔布搜尋法流程圖…………………………………………… 32
圖4.2 料號分割位置選擇圖………………………………………… 38
圖4.3(A) 範例3依據機台閒置時間前後的排程結果……………… 39
圖4.3(B) 範例3依據交期內產能大小的排程結果………………… 40
圖4.4 料號分割指派流程圖………………………………………… 45
圖4.5 範例4 料號分割與機台指派結果…………………………… 47
圖4.6 範例5 料號分割與機台指派結果…………………………… 49
圖5.1 排程系統資料表關聯圖……………………………………… 51
圖5.2 排程起始設定參數輸入畫面………………………………… 53
圖5.3 初始排程優先準則設定……………………………………… 53
圖5.4 塔布搜尋法參數設定………………………………………… 53
圖6.1(A) 範例6料號數與求解時間關係圖………………………… 57
圖6.1(B) 範例6料號數與本研究塔布解之求解時間關係圖……… 57
圖6.1(C) 範例6料號數與排程總成本關係圖……………………… 58
圖6.2(A) 範例6機台數與求解時間關係圖………………………… 60
圖6.2(B) 範例6機台數與本研究塔布解之求解時間關係圖……… 60
圖6.2(C) 範例6機台數與排程總成本關係圖……………………… 60
圖6.3(A) 範例6料號分割數與求解時間關係圖…………………… 63
圖6.3(B) 範例6料號分割數與本研究塔布解之求解時間關係圖… 63
圖6.3(C) 範例6料號分割數與排程總成本關係圖………………… 63
圖6.4 實際排程數據1 塔布搜尋成本收斂圖……………………… 66
圖6.5 實際排程數據2 塔布搜尋成本收斂圖……………………… 68
圖6.6 實際排程數據3 塔布搜尋成本收斂圖……………………… 70
圖6.7 建榮廠實際排程改善效益圖………………………………… 71
圖6.8 實際排程數據4 塔布搜尋成本收斂圖……………………… 73
圖6.9 實際排程數據5 塔布搜尋成本收斂圖……………………… 75
圖6.10 實際排程數據6塔布搜尋成本收斂圖……………………… 77
圖6.11 中壢2廠實際排程改善效益圖……………………………… 78
圖6.12 實際排程改善效益圖 ……………………………………… 79
表 目 錄
表2.1 非等效平行機台相關文獻整理……………………………… 12
表3.1 範例1 料號規格資料表……………………………………… 24
表3.2 範例1 機台規格資料表……………………………………… 25
表3.3 範例2 料號規格資料表……………………………………… 26
表3.4 範例2 機台規格資料表……………………………………… 26
表3.5 最佳解求解時間表…………………………………………… 27
表4.1 範例3 機台產能及閒置時間表……………………………… 39
表4.2 範例4、5機台規格資料表…………………………………… 46
表6.1 範例6 預計排程資料表……………………………………… 54
表6.2 範例6 料號規格資料表……………………………………… 54
表6.3 範例6 權重成本資料表……………………………………… 54
表6.4 範例6 現場機台資料回饋資料表…………………………… 55
表6.5 範例6 機台資料表…………………………………………… 55
表6.6 範例6 排程起始設定表……………………………………… 55
表6.7 範例6 本研究塔布搜尋法參數設定表……………………… 55
表6.8 範例6 最佳解與塔布解之求解時間與總成本表…………… 56
表6.9 範例6 整體解集合數目表…………………………………… 58
表6.10 範例6本研究塔布搜尋法解集合數目表…………………… 59
表6.11 實際排程數據1結果比較表………………………………… 66
表6.12 實際排程數據1排程改善空間表…………………………… 66
表6.13 實際排程數據2結果比較表………………………………… 68
表6.14 實際排程數據2排程改善空間表…………………………… 68
表6.15 實際排程數據3結果比較表………………………………… 70
表6.16 實際排程數據3排程改善空間表…………………………… 70
表6.17 實際排程數據4結果比較表………………………………… 73
表6.18 實際排程數據4排程改善空間表…………………………… 73
表6.19 實際排程數據5結果比較表………………………………… 75
表6.20 實際排程數據5排程改善空間表…………………………… 75
表6.21 實際排程數據6結果比較表………………………………… 77
表6.22 實際排程數據6排程改善空間表…………………………… 77

[1] Adamopoulos, G.I. and Pappis, P.C., “Scheduling under a common due-date on parallel unrelated machines,” European Journal of Operation Research, Vol.105, pp.494-501, 1998.
[2] Aoyama, E. et al., “Study an small diameter drilling in GFRP,” Composite Structures, Vol.32, pp.567-573, 1995.
[3] Arementano, V.A. and Ronconi, D.P., “Tabu search for total tardiness minimization in flowshop scheduling problems,” Computers & Operations Research, Vol.26, No.3, pp.219-235, 1999.
[4] Armentano, V.A. and Scrich, C.R., “Tabu search for minimizing total tardiness in a job shop,” International Journal Of Production Economics, Vol.63, No.2, pp.131-140, 2000.
[5] Azizoglu, M. and Kirca, O., “Tardiness minimization on parallel machines,” International Journal of Production Economics , Vol.55, pp.163-168, 1998.
[6] Ben-Daya, M. and Al-Fawzan, M.,“A tabu search approach for the flow shop scheduling problem,” European journal of operational research, Vol.109, pp.88-95, 1998.
[7] Cheng, R. and Gen, M.,“Parallel machine scheduling problems using memetic algorithms”, Computers & Industrial Engineering, Vol.33, No. 3-4, pp.761-764, 1997.
[8] Cheong, M. S. et al., “Identification and control for micro-drilling productivity enhancement,” International Journal of Machine Tools and Manufacture, Vol.39, pp.1539-1561, 1999
[9] Cole, J. E., “Design-to-manufacture-an integrated information system,” Computer-Aided Engineering Journal, Vol.65, pp.159-65, 1989.
[10] Figielska, E., “Preemptive scheduling with changeovers: using column generation technique and genetic algorithm,” Computers & Industrial Engineering, Vol.37, pp.81-84, 1999.
[11] Ghedjati, F.,“Genetic algorithms for the job-shop scheduling problem with unrelated parallel constraints: heuristic mixing method machines and precedence,” Computers & Industrial Engineering, Vol.37, pp.39-42, 1999.
[12] Glass, C. A. et al., “Unrelated parallel machines scheduling using local search,” Mathematical Computing Modeling, Vol.20, pp.41-52, 1994.
[13] Glover, F. and Laguna, M., Tabu Search, Blackwell Scientific Publications, Oxford, 1993.
[14] Glover, F., “Future paths for integer programming and links to artificial intelligence,” Computers and Operation Research, Vol.13, No.5, pp.533-549, 1986.
[15] Glover, F., “Tabu Search — Part I,” ORSA Journal Computing, 1, pp.190-206, 1989.
[16] Hariri, A. and Potts, C., “Heuristics for scheduling unrelated parallel machines ,” Computers Ops Res, Vol.18, No.3, pp.323-331, 1991.
[17] Inoue, H. et al., “Influence of tool wear on internal damage in small diameter drilling in GFRP,” Composite Structures, Vol.39, pp.55-62, 1997.
[18] Kim, Y. et al., “Search heuristics for a flowshop scheduling problem in a printed circuit board assembly process,” European Journal of Operational Research, Vol. 91, pp.124-143, 1996.
[19] Kolahan, F. and Liang, M., “A tabu search approach to optimization of drilling operations,” Computers & Industrial Engineering, Vol.31, pp.371-374, 1996.
[20] Koulamas, C., “The total tardiness problem: review and extensions,” Operations resaerch, Vol.42, pp.1025-1041, 1994.
[21] Lancia, G., “Scheduling jobs with release dates and tails on two unrelated parallel machines to minimize the makespan,” European Journal of Operational Research, Vol.120, pp.277-288,
2000.
[22] Lee, Y. H. and Pinedo, M., “Scheduling jobs on parallel machines with sequence-dependent setup times,” European Journal of Operational Research, Vol.100, 464-474, 1997.
[23] Liaw C.F., “A tabu search algorithm for the open shop scheduling problem,” Computers & Operations Research, Vol.26, No.2, pp.109-126, 1999.
[24] Lim, J. M, “A genetic algorithm for a single hoist scheduling in the printed-circuit-board electroplating line,” Computers & Industrial Engineering, Vol.33, pp.789-792, 1997.
[25] Lin, f. and Shaw, M. J., “Scheduling printed circuit board production systems using the two-level scheduling approach,” Jpurnal of Manufacturing Systems, Vol.16, pp.129-149, 1997.
[26] Martello, S. et al., “Exact and approximation algorithms for makespan minimization on unrelated parallel machines,” Discrete Applied Mathematics, Vol.75, pp.169-188, 1997.
[27] Nowicki, E. and Smutnicki, C., “A fast taboo search algorithm for the job shop problem,” Management Science, 42(6), pp.797-813, 1996.
[28] Nowicki, E. and Smutnicki, C., “The flow shop with parallel machines: A tabu search approach,” European Journal of Operational Research, Vol.106, pp.226-253, 1998.
[29] Ogawa, K. et al., “Investigation on cutting mechanism in small diameter drilling for GFRP,” Composite Structures, Vol.38, pp.343-350, 1997.
[30] Park, M.W. and Kim, Y.D., “Search heuristics for a parallel machine scheduling problem with ready times and due dates,” Computers Industrial Engineering, Vol.33, No.3-4, pp.793-796, 1997.
[31] Park, Y. et al., “Scheduling jobs on parallel machines applying neural network and heuristic rules,” Computers and Industrial Engineering, Vol.38, pp.189-202, 2000.
[32] Piersam, N. and Dijk, W.V., “A local search heuristic for unrelated parallel machine scheduling with efficient neighborhood search,” Mathematical computing modeling, Vol.242, pp.11-19, 1996.
[33] Reeves, C. R., “Improving the efficiency of tabu search for machine sequencing problems,” Journal of the Operational Research Society, 44(4), pp.375-383, 1993.
[34] Ruiz-Torres, et al, “Simulated annealing heuristics for the average flow-time and the number of tardy jobs bi-criteria identical parallel machine problem,” Computers Industrial Engineering, Vol.33, No.1-2, pp.257-260, 1997.
[35] Serifoglu, F. S. and Ulusoy, G., “Parallel machine scheduling with earliness and tardiness penalties,” Computers and Operations Research , Vol.26, pp.773-787, 1999.
[36] Suresh, V. and Chaudhuri, D., “Bicriteria scheduling problem For unrelated parallel machines, ” Computers Industrial Engineering, Vol. 30, No. 1, pp. 77-82, 1995.
[37] Suresh, V. and Chaudhuri, D., “Minimizing maximum tardiness for unrelated parallel machines ,” international journal of production economics, Vol.34, pp.223 — 229, 1994.
[38] Vaessens, R.J.M. et al.,“Job shop scheduling by local search,” INFORMS Journal on Computing, 8(3), pp.302-317, 1995.
[39] Valls, V. et al., “A tabu search approach to machine scheduling,” European Journal of Operational Research, Vol.106, pp.277-300, 1998.
[40] Webster, S. and Azizoglu, M., “Dynamic programming algorithms for scheduling parallel machines with family setup times,” Computers and Operations Research, Vol.28, pp.127-137, 2001.
[41] Weng, M. et al., “Unrelated parallel machine scheduling with setup consideration and a total weighted completion time objective,” International Journal of Production Economics, Vol. 70, pp.215-226, 2001.
[42] 白蓉生，電路板解困及規範手冊，初版，台北，電路板資訊雜誌社，民國八十九年。
[43] 李威亭，「邏輯IC最終測試廠之測試機台排程研究」，國立清華大學，碩士論文，民國89年。
[44] 林正偉，「訂單式生產雙向排程演算法之績效評估」，私立義守大學，碩士論文，民國88。
[45] 林玲妃 ，「全球PCB產業發展趨勢」，電子時報，民國八十九年十一月二十三日。http://www.digitimes.com.tw/NewsShow/PagesSpecial.asp.
[46] 邱竣鋒，「利用模擬退火法及塔布搜尋法求解工件非同時到達之單機排程問題」，私立元智大學，碩士論文，民國87年。
[47] 金京光，「半導體多頭測試機器之最小化延遲時間排程」，國立清華大學，碩士論文，民國89年。
[48] 劉志宏，「不確定加工時間之平行機台排程」，國立清華大學，碩士論文，民國89年。
[49] 劉郁廉，「晶圓廠黃光區製造系統派工法則之研究」，國立台灣大學，碩士論文，民國86年。
[50] 簡鐘富，PCB製程導覽（光碟書），PCB Net Inc.，1999。
[51] 蘇仁傑，「考慮再回流製程之派工法則」，國立交通大學，碩士論文，民國88年。