臺灣博碩士論文加值系統

一般的生產排程模式只考慮加工的先後順序，只要在目標時間內完成所有訂單的製程即可。但是在一些的特定產業卻要考慮加工程序迴流（re-entrant）的情形，典型的例子就是IC測試業。不同於常見固定的、重複的迴流特性，IC測試業的迴流情況是以時間做為迴流發生的基準，亦即當前製程加工完成後，一定要在一定的時間內執行下一個製程，否則就要回到前製程再加工一次的一個迴流特性。
由於IC測試業有這樣的產業特性，因此本研究針對IC測試業的迴流型零工式生產環境，建立一個相對應的數學模式，並代入小規模的問題來測試該模式的正確性。由於迴流型零工式生產排程問題是一個 NP-Complete問題，如此一來就連最佳化軟體也難以找到最佳解，同時要花費的時間也難以估計。為能夠在有限的時間內、有效找到近似最佳解，本研究從啟發式演算法（meta-heuristics）著手。而常見的啟發式演算法又以模擬退火法為普遍使用的方法之一，並且也都有不錯的效果，因此本研究設計一個有效的模擬退火法進行求解。
因為目前沒有相似於以時間定義迴流的相關研究，所以難以驗證所提出演算法之效用，因此修改兩個過去文獻範例，加入迴流特性資料，做為測試依據。根據修改後範例，分別以數學規劃模型/LINGO與演算法加以求解並進行比較。最後結果顯示，本研究所提出的演算法不管是在求解品質（誤差在2%內）或在求解效率（時間減少非常多）都是非常出色。

General operation scheduling problems only consider the limitations of process sequences. However, re-entrant process has to be taken care of in some industries. IC assembly and test industry is one of them. The re-entrant process of this industry occurs when the time interval between two consecutive production stages exceeds some pre-defined time limit.
This study focuses on the development of a method to solve such a job shop scheduling problem (JSSP) with time-defined re-entrant processes. A mathematical programming model is constructed as basis. Two small- size JSSP instances are used to validate the correctness of the model. Since the job shop scheduling problem with time defined re-entrant process is an NP-Complete problem, it is almost impossible to solve a real-life size instance in reasonable time. A meta-heuristics algorithm based on simulated annealing concept is developed to solve the problem.
Since there isn’t any research similar to the problem discussed, two examples from past research are modified by adding hypothetical re-entrant process data. These two modified examples are solved by optimization method and by proposed algorithm, respectively. It can be shown that optimal values found by the algorithm are within 2% errors compared to that from optimization model. However, time required for the solution process from the algorithm is much shorter than that from the optimization. It can thus be concluded that proposed algorithm is a better choice to solve such problems efficiently.

摘要 I
Abstract II
致謝 III
目錄 IV
圖目錄 VI
表目錄 VII
第一章 緒論 1
1.1 研究動機 1
1.2 研究目的 2
1.3 研究流程 2
第二章 文獻回顧 4
2.1 零工式生產 4
2.2 迴流型生產排程 6
2.3 生產排程績效指標 8
2.4 模擬退火法 11
第三章 研究設計 13
3.1. 問題描述 13
3.2. 流程說明 13
3.3 研究假設 14
3.4 研究方法 15
3.5 演算法設計與驗證流程 17
3.5.1. 數學規劃模型 18
3.5.2 演算法的建構 22
第四章 結果分析 32
4.1. 最佳參數設定 32
4.1.1. 案例一ft06（6x6） 33
4.1.2. 案例二ft10（10x10） 33
4.1.3. 案例三ft20（20x5） 34
4.1.4. 案例四la26（20x10） 34
4.1.5. 小結 34
4.2. 演算法效果與效率的測試 35
4.2.1. 演算法例題測試結果 35
4.2.2. 簡化演算法（SA2_N）之案例測試結果 37
4.3. 迴流型生產排程的求解品質比較 38
4.3.1. 案例ft06 38
4.3.2. 案例la01 39
4.3.3. 小結 40
第五章 結論與未來展望 41
5.1. 結論 41
5.2. 未來研究方向 42
參考文獻 43
中文部分 43
英文部分 44
附錄一：測試範例 47
附錄二：參數設定測試結果-ft06 51
附錄三：參數設定測試結果-ft10 53
附錄四：參數設定測試結果-ft20 55
附錄五：參數設定測試結果-la26 57

中文部分
1.羅中育（2001）。田口品質工程應用於模擬退火法參數組合-以呂瀅推銷員問題(TSP)為例。未出版之碩士論文，國立雲林科技大學，雲林縣。
2.盧研伯（2003）。混合式模擬退火法應用於具迴流特性流程工廠之研究。未出版之碩士論文，國立台北科技大學，台北市。
3.李宜原（2004）。改良式遺傳演算法於零工式生產排程系統之應用。未出版之碩士論文，國立臺灣海洋大學，基隆市。
4.柯惠雯（2001）。結合模擬退火法與禁忌搜尋法在流程式生產排程之應用。未出版之碩士論文，大葉大學，彰化縣。
5.何惠雯（2001）。具等候時間窗口限制之零工式生產排程工作順序之決定。未出版之碩士論文，國立中央大學，桃園縣。
6.黃俊龍（2004）。應用模擬退火法規劃具有加工順序限制之非相關平行機台多目標排程。未出版之碩士論文，國立屏東科技大學，屏東縣。
7.周德華（2001）。多目標迴流環境下之限制驅導式排程系統。未出版之碩士論文，國立中央大學，桃園縣。
8.張皇文（2006）。液晶顯示器陣列製程之彈性零工式生產排程。未出版之碩士論文，國立清華大學，新竹市。
9.陳建良（1995）。排程概述。機械工業雜誌，153，122-137。
10.程偉哲（2010）。時窗限制之彈性零工式生產排程研究-以二費洛蒙蟻群演算法求解。未出版之碩士論文，天主教輔仁大學，新北市。
11.曾偉杰（2011）。以模擬退火法求解流線型製造單元排程。未出版之碩士論文，國立交通大學，新竹市。
12.游麗萍（2004）。應用蟻族最佳化規劃有倉儲限制的生產排程。未出版之碩士論文，國立屏東科技大學，屏東縣。
13.吳貴彬（1998）。以模擬退火法求解工單式生產系統之排程問題--最小化總延遲時間。未出版之碩士論文，國立成功大學，台南市。
14.魏文鍇（2003）。利用啟發式演算法求解工單式生產系統排程中時窗限制與釋放時間限制問題。未出版之碩士論文，國立成功大學，台南市。
15.吳秉威（2005）。以遺傳演算法求解PCB廠生產排程問題。未出版之碩士論文，南台科技大學，台南市。

英文部分
1.Chen, J., Pan, P., & Lin, C. (2006). A hybrid genetic algorithm for the re-entrant flow-shop scheduling problem. Expert Systems with Applications, 34(1), 570-577.
2.Garey, M.R., Johnson, D.S., & Sethi, R. (1976). The complexity of flowshop and job shop scheduling. Mathematics of Operations Research, 1(2), 117-129
3.Haupt, R. (1989). A survey of priority rule-based scheduling. Operations-Research-Spektrum, 11(1), 3-16.
4.Kaihara, T., Fujii, N., Tsujibe, A., & Nonaka, Y. (2010) Proactive maintenance scheduling in a re-entrant flow shop using Lagrangian decomposition coordination method. CIRP Annals-Manufacturing Technology, 59(1), 453-456.
5.Lenstra, J.K., & Rinnooy Kan, A.H.G. (1979). Computational complexity of discrete optimization problem. Annals of Discrete Mathematics, 4, 121-140.
6.Lin, D., Lee, C., & Ho, W. (2013). Multi-level genetic algorithm for the resource-constrained re-entrant scheduling problem in the flow shop. Engineering Applications of Artificial Intelligence, 26(4), 1282–1290.
7.Mahfoud, S.W., & Goldberg, D.E. (1995). Parallel recombinative simulated annealing: A genetic algorithm. Parallel Computing, 21(1), 1-28.
8.Mattfeld, D.C. & Vaessens, R.J.M. (2003). Job shop problem test instances set. Available: OR Library online, <http://people.brunel.ac.uk/~mastjjb/jeb/orlib/jobshopinfo.html>
9.Ohta, H., & Nakatani, H. (2006). A heuristic job-shop scheduling algorithm to minimize the total holding cost of completed and in-process products subject to no tardy jobs. International Journal of Production Economics, 101(1), 19-29.
10.Parthanadee, P., & Buddhakulsomsiri, J. (2010). Simulation modeling and analysis for production scheduling using real-time dispatching rules: A case study in canned fruit industry. Computers and Electronics in Agriculture, 70(1), 245-255.
11.Raaymakers, W.H.M., & Hoogeveen, J.A. (2000). Scheduling multipurpose batch process industries with no-wait restrictions by simulated annealing. European Journal of Operational Research, 126(1), 131-151.
12.Saraiva, J., Pereira, M., Mendes, V., & Sousa, J. (2011). A Simulated Annealing based approach to solve the generator maintenance scheduling problem. Electric Power Systems Research, 81(7), 1283–1291.
13.Satake. T., Morikawa, K., Takahashi, K., & Nakamura, N. (1999). Simulated annealing approach for minimizing the makespan of the general job-shop. International Journal of Production Economics, 60-61, 515-522.
14.Wiendahl, H.-P., & Scholtissek, P. (1994). Management and control of complexity in manufacturing. CIRP Annals - Manufacturing Technology, 43(2), 533-540.
15.Wu, C.-C., Hsu, P.-H., & Lai, K. (2011). Simulated-annealing heuristics for the single-machine scheduling problem with learning and unequal job release times. Journal of Manufacturing Systems, 30(1), 54–62.
16.Zhang, R., Song, S., & Wu, C. (2013). A hybrid artificial bee colony algorithm for the job shop scheduling problem. International Journal of Production Economics, 141(1), 167–178.
17.Zhou, H., Feng, Y., & Han, L. (2001). The hybrid heuristic genetic algorithm for job shop scheduling. Computers & Industrial Engineering, 40(3), 191-200.