以模擬退火演算法 進行化鍍製程無關聯平行機台之排程

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：22

、訪客IP：3.21.248.119

姓名

楊雅婷(Ya-Ting Yang) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

以模擬退火演算法進行化鍍製程無關聯平行機台之排程
(Using Simulated Annealing to Schedule Electroless Plating Jobs on a Number of Unrelated Parallel Machines)

相關論文

★ 以混合整數規劃安插電鍍銅平行機台之緊急訂單	★ 以混合整數規劃進行非相關平行機台之批次製造排程
★ 考量最大利潤之再生能源發電業最佳能源分配	★ 工業用電考量時間電價之太陽能發電系統最佳配置規劃

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

至系統瀏覽論文 ( 永不開放)

摘要(中)

隨著醫療產業、汽車航太科技的進步，其耐熱半導體元件－LED散熱基板的市場也不斷擴張。目前市面上的LED散熱基板以薄膜陶瓷基板為主。由於陶瓷材料其高電阻、高頻特性突出，且具有高熱導率、高度化學穩定性、高熱穩定性和高熔點等優點，讓陶瓷基板適用於各類電子元件，尤其在醫療、航太、汽車、太陽能產業的產品內扮演重要角色，這也促進LED陶瓷基板在需求市場的成長。
　　然而在LED散熱基板的製程中，工廠的產能是有限制的，亦即每生產一批產品皆會瓜分數個機台設備資源。工廠內同作業的製程有數條生產線，而這些生產線中，各機台設備有不同的設置時間、使用年份，各產品的特性等，這些條件皆會影響製程時間，除此之外在生產過程中，臨時調機的狀況亦是影響製程時間的因素之一。
　　在工廠內部作業中，生產排程主要是由生管單位做安排，但是在實務上，生管單位因為不了解機台狀況及產品特性，無法針對各產品做出最妥當的生產順序。因此日生產排程往往到了現場製造單位，又會經過一次調整。這導致生管單位無法如一開始生產規劃的順序去追蹤生產現況，當若有緊急工件需要即時追蹤時，往往需要派額外的人力去做現場產品追蹤，不僅浪費人力，同時因為該動作增加各部門間的摩擦。
　　因此，本論文的主軸將會考慮到上述實際生產情形，進行無關聯平行機台生產排程問題的求解。挑選具有材料汙染性問題的化鍍製程之特性做為本論文的研究範圍，在加入因材料需臨時調機的考量後，又新增工件時窗限制，以增加生管單位可以針對緊急工件做出相應的優先安排加工順序之彈性。最後本研究使用模擬退火演算法來進行求解，透過該方法，避免陷入區域最佳解之困境，同時也能在短時間內獲得有效的排程解。

摘要(英)

With the advancement of the medical industry and automotive aerospace technology, the market of the LED heat-dissipation substrate has expanded continually. Currently, the LED heat-dissipation substrates are mainly thin-film ceramic substrates. Due to the advantages of high electrical resistance, high-frequency characteristics, high thermal conductivity, high chemical stability, high thermal stability and high melting point, ceramic substrates are suitable for various electronic components, especially in medical, aerospace, and automotive industry, which also promotes the growth demand of LED ceramic substrates.
However, the production of a batch of products will use several machine equipment resources in the manufacturing process. There are several production lines in the same manufacturing process in the factory. Each machine has different product characteristics, such as different setup time, year of use. These conditions will affect the process time. Besides, the temporary adjustment is also one of the factors affecting the process time.
In the internal operation of the factory, the production schedule is mainly arranged by the production department. However, in practice, because the production department does not understand the machine conditions and the product characteristics, it cannot make the most proper production order for each product. The production schedule is often adjusted in the on-site manufacturing unit, it causes the problem for the production department cannot track the current production status according to the initial production order. Therefore, if there is a need for immediate tracking of the emergency component, it is often necessary to send extra manpower to on-site. It not only wastes human resources but also increases the frictions between departments.
Therefore, the research will consider the above-mentioned actual production situation, carrying out the production scheduling problem of the unrelated parallel machine. The research considers the factors of temporary adjustment due to materials and the limit of component time window so that increasing the flexibility of prioritizing the processing sequence of the emergency component. The research scope is based on the electroless plating process with material contamination problems. Finally, the research adopts the simulated annealing algorithm to solve the problem. By using the simulated annealing algorithm, it avoids the dilemma of getting into the optimal solution of the region and can also obtain an effective scheduling solution in a short time.

關鍵字(中)

★ LED散熱基板
★ 排程問題
★ 無關聯平行機台
★ 時間窗格
★ 模擬退火演算法

關鍵字(英)

★ LED heat-dissipation substrate
★ scheduling problem
★ unrelated parallel machines
★ time window
★ simulated annealing algorithm

論文目次

摘要 i
英文摘要 ii
目錄 iv
圖目錄 vi
表目錄 vii
第一章緒論 1
1.1　研究背景與動機 1
1.2　研究目的 2
1.3　研究架構與流程 2
第二章半導體產業與研究問題 4
2.1　半導體產業與散熱基板 4
2.2　陶瓷基板特色及製程介紹 9
2.3　表面處理及實務情況 13
2.3.1　表面處理 13
2.3.2　實務情況 15
2.4　研究問題 16
第三章文獻探討 19
3.1　排程問題 19
3.2　無關聯平行機台 23
3.3　時間窗格 25
3.4　模擬退火演算法 26
第四章研究方法 28
4.1　研究題目基本假設 28
4.2　初始解演算法流程 29
4.3　模擬退火演算法架構及流程 31
4.3.1　模擬退火演算法架構 31
4.3.2　模擬退火演算法流程 33
第五章實驗測試與參數分析 37
5.1　實驗硬體設備與驗證 37
5.2　模擬情境實驗測試 40
第六章結論與建議 44
6.1　結論 44
6.2　未來研究方向 45
參考文獻 46
附件表格 51

參考文獻

中文文獻
1.丁志華（2018）。矽晶・電子：矽說台灣–台灣半導體產業發展與全球地位。科學發展，541期：21-29。科技部：臺北市，臺灣。
2.台灣陶瓷學會（2017）。LED電子領域用陶瓷基板現狀與發展簡要分析，http://www.tcers.org.tw/news-tw/ceramic-technology/204-led，台灣陶瓷學會：臺南市，臺灣。（上網日期：2018年10月3日）。
3.江志宏（2018）。陶瓷基板（Ceramic PCB，Ceramic Substrate），http://www.kson.com.tw/chinese/study_15-18.htm，（上網日期：2018年10月2日）。
4.產業價值鏈資訊平台（2018）。半導體產業鏈簡介，https://ic.tpex.org.tw/introduce.php?ic=D000&stk_code=1410，證劵櫃台買賣中心：臺北市，臺灣。（上網日期：2018年12月23日）。
5.莊凱翔、張宇廷、李冠儀與邱國創（2016）。ITRI直接覆銅陶瓷基板技術之探討。工業材料雜誌，359期：127-133。工業技術研究院：新竹縣，臺灣。
6.游慧茹（2009）。2010年新瓷器時代-LED陶瓷散熱方案，http://www.icprotect.com.tw/articles-9.html，（上網日期：2018年11月23日）。
7.游慧茹（2009）。目前LED散熱基板的趨勢，http://www.icprotect.com.tw/articles-8.html，（上網日期：2018年10月2日）。
8.LED inside（2012）。LED封裝領域用陶瓷基板現狀與發展簡要分析，https://www.ledinside.com.tw/knowledge/20120514-21055.html，集邦科技股份有限公司：臺北市，臺灣（上網日期：2018年10月2日）。
英文文獻
9.Anagnostopoulos G-C and Rabadi G (2002). A simulated annealing algorithm for the unrelated parallel machine scheduling problem. IEEE. In Proceedings of the 5th Biannual world automation congress 14:115-120.
10.Blocher J-D and Chhajed D (1996). The customer order lead-time problem on parallel machines. Naval Research Logistics 43 (5):629-654.
11.Bozer Y-A and Wang C-T (2012). A graph-pair representation and MIP-model-based heuristic for the unequal-area facility layout problem. European Journal of Operational Research 218 (2):382-391.
12.Brucker P and Kravchenko S-A (2008). Scheduling jobs with equal processing times and time windows on identical parallel machines. Journal of Scheduling 11 (4): 229-237.
13.Conway R-W, Maxwell W-L and Miller L-W (1967). Theory of Scheduling. Cornell University: New York, USA.
14.Davis E and Jaffe J (1981). Algorithms for Scheduling Tasks on Unrelated Processors. Journal of the Association for Computing Machinery 28: 721-736.
15.De P and Morton T (1980). Scheduling to Minimize Makespan on Unrelated Processors. Decision Sciences 11: 586-602.
16.Elmaghraby S-E and Park S-H (1974). Scheduling jobs on a number of identical machines. AIIE Transactions 6 (1): 1-13.
17.Gabrel V (1995). Scheduling jobs within time windows on identical parallel machines: New model and algorithms. European Journal of Operational Research 83:320-329
18.Garey M-R and Johnson D-S (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company: New York, USA.
19.Hariri A-M-A and Potts C-N (1991). Heuristics for Scheduling Unrelated Parallel Machines. Computers and Operations Research 18: 313-321.
20.Hastings N-A-J, Marshall P and Willis R-J (1982). Scheduling based MRP: An integrated approach to production scheduling and material requirements planning. Journal of Operational Research Society 33 (11):1021-1029.
21.Hastings N-A-J and Yeh C-H (1990). Job oriented production scheduling. European Journal of Operational Research 47:35-48.
22.He R-J (2005). Parallel machine scheduling problem with time windows: a constraint programming and tabu search hybrid approach. Proceedings of the Fourth International Conference on Machine Learning and Cybernetics :18-21. National University of Defense Technology: Guangzhou, China.
23.Horowitz E and Sahni S (1976). Exact and Approximation Algorithms for Scheduling Nonidentical Processors. Journal of the Association for Computing machinery 23: 317- 327.
24.Ibarra O-H and Kim C-E (1977). Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical Processors. Journal of the Association for Computing machinery 24: 280-289.
25.IC insight (2019). The McClean Report 2019. http://www.icinsights.com/services/mcclean-report/report-contents/ , IC insight: Arizona, USA,(accessed 15 March 2019).
26.Kim D-W, Na D-G and Chen F-F (2003). Unrelated parallel machine scheduling with setup times and a total weighted tardiness objective. Robotics and Computer Integrated Manufacturing 19 (1-2):173-181.
27.Kim Y-D (1995). A backward approach in list scheduling algorithms for multi-machine tardiness problems. Computers and Operations Research 22 (3):307-319.
28.Kim Y-D, Shim S-O, Kim S-B, Choi Y-C and Yoon H-M (2004). Parallel machine scheduling considering a job splitting property. International Journal of Production Research 42 (21):4531-4546.
29.Lee Y-H, Pinedo M (1997). Scheduling jobs on parallel machines with sequence-dependent setup times. European Journal of Operational Research 100 (3):464-474.
30.Lin S-W (2013). Solving the Team Orienteering Problem Using Effective Multi-start Simulated Annealing. Applied Soft Computing 13:1064-1073.
31.Lin S-W and Ying K-C (2013). Minimizing Makespan and Total Flowtime in Permutation Flowshops by a Bi-objective Multi-start Simulated-annealing Algorithm. Computers and Operations Research 40:1625-1647.
32.Logendran R and Subur F (2004). Unrelated parallel machine scheduling with job splitting. IIE Transactions 36 (4):359-372.
33.Martello S, Soumis F and Toth P (1997). Exact and Approximation Algorithm for Makespan Minimization on Unrelated Parallel Machines. Discrete Applied Mathematics 75: 169-188.
34.Martí R, Resende M-G-C and Ribeiro C-C (2013). Multi-start Methods for Combinatorial Optimization. European Journal of Operational Research 226:1-8.
35.Park M-W (2000). A genetic algorithm for the parallel-machine total weighted tardiness problem. Journal of the Korean Institute of Industrial Engineers 26 (2):183-192.
36.Pinedo M-L (2008). Scheduling: Theory, Algorithms, and Systems. New York University: New York, USA.
37.Potts C (1985). Analysis of A Linear Programming Heuristic for Scheduling Unrelated Parallel Machines. Discrete Applied Mathematics 10: 155-164.
38.Rocha P-L、Ravettia M-G、Mateusa G-R and Pardalosb P-M (2008). Exact algorithms for a scheduling problem with unrelated parallel machines and sequence and machine-dependent setup times. Computers & Operations Research 35:1250-1264.
39.Rodrigues M-T-M, Latre L-G and Rodrigues L-C-A (2000). Production planning using time windows for short-term multipurpose batch plants scheduling problems. Industrial & engineering chemistry research 39(10):3823-3834.
40.Salcedo-Sanz S (2016). Modern meta-heuristics based on nonlinear physics processes: A review of models and design procedures. Physics Reports 655:1-70.
41.Serafini P (1996). Scheduling jobs on several machines with the job splitting property. Operations Research 44 (4):617-628.
42.Sheikh S (2007). Multi-Stage Scheduling Problem With Time Windows. Conference Paper. Azad University: Manhattan, USA.
43.Ven de Velde S-L (1993). Duality-Based Algorithm for Scheduling Unrelated Parallel Machines. ORSA Journal of Computing 5: 192-205.
44.White C (1986). Capacity Constrained Load Sequencing Techniques for Production Management. PhD Thesis. Monash University: Melbourne, Australia.
45.White C and Hastings N-A-J (1983). Scheduling techniques for medium scale industry. Australian Society for Operations Research Bullen 3:1-4.
46.Xing W and Zhang J (2000). Parallel machine scheduling with splitting jobs. Discrete Applied Mathematics 103(1-3):259-269.
47.Yang J and Posner M-E (2005). Scheduling parallel machines for the customer order problem. Journal of Scheduling 8 (1):49-74.

指導教授

王啓泰(Chi-Tai Wang)

審核日期

2019-7-19

推文