臺灣博碩士論文加值系統

半導體測試為整個半導體製程的最後階段，測試排程的良窳，將影響產出、機台利用率與作業效率。然而，測試需同時使用測試機與分類機，而且所要使用的機台成本相當昂貴且往往數量有限。因此，如何在有限的資源下，決定指派的機台與作業的順序，以有效滿足客戶需求是非常的重要。
本研究主要在解決半導體測試的排程問題，該問題是一個具有順序相依設置時間、作業順序性限制（precedence constraint）、相容性機器組合、多資源限制（multi-resource constraint）（包括測試機、分類幾、配件等）的彈性零工式生產排程問題。此問題可被證明是一個NP-hard問題。求解此類排程問題非常耗時，特別是面對實務問題，往往無法在有限時間內獲得滿意的排程解。
本研究以基因演算法為架構，設計一啟發式演算法，並以最小化完工時間（minimize makespan）為排程目標。演算法設計與程式撰寫完成後，首先，使用三組案例進行參數實驗，以找出最佳的參數組合，並以該參數組合進行效果與效率的驗證。為了驗證演算法的求解能力，分別以小型案例與大型案例進行比較，小型案例方面，與數學規劃模型的最佳解進行比較，並以最佳解誤差率衡量演算法的績效；大型案例方面，則與個案公司的排程方法進行比較，並以改善幅度衡量演算法的求解效果。
結果顯示，演算法在小型案例的最佳解誤差率約在1%以內；大型案例求解的改善幅度可達12.68%。在效率的部分，在兩組不同類型的案例，皆可在相當短或可接受的時間內找到良好的解。經此驗證可以顯示，本演算法在求解半導體測試作業排程問題上，非但在小型問題可以獲得幾近最佳的排程解，在實務問題上，也可以在合理快速的時間裡獲得令人滿意的排程解。

Semiconductor testing process is the final procedure in the semiconductor manufacturing. The performance of the process scheduling will affect its throughput, machine utilization and operating efficiency, thus its profit. It becomes critical to effectively schedule job sequence and machine assignment with sequence dependent setup time, operation precedence constraint, and under multiple and limited resources, such as tester, handler, and accessories, etc.
The study focuses on solving scheduling problems of semiconductor functional testing. This problem can be classified as a flexible job shop scheduling problem and be proved to be an NP-hard problem, which implies that solving the problem will take considerable computing time when the problem size is large. A meta-heuristics algorithm based on Genetic Algorithm is proposed to solve this problem with makespan minimization as the goal.
After conceptual design and program development of the heuristics, best parameter setting are decided though the experimental design using three different-size data sets. A series of experiments and comparative analysis are carried out to evaluate the performance of proposed algorithm. With small-size test problems, the algorithm can generate the optimal or near-optimal solution almost instantaneously. Under large or real-case size cases, the algorithm can reach 12.68% reduction in makespan performance within 10-20 minutes, compared with around 120 minutes scheduled by labor work. This demonstrates that the proposed algorithm can produce satisfactory testing schedule in a reasonable time.

摘要 i
Abstract ii
誌謝 iii
目錄 iv
表目錄 vi
圖目錄 viii
第一章 緒論 1
1.1 研究背景 1
1.2 研究動機 2
1.3 研究目的 2
1.4 研究流程 3
第二章 文獻探討 5
2.1 排程環境與問題特性 5
2.2 彈性零工式生產排程 8
2.3 多資源排程問題 11
2.4 基因演算法 14
2.5 小結 17
第三章 研究設計 19
3.1 問題描述 19
3.2 問題特性 21
3.3 研究假設 22
3.4 建立數學規劃模型 22
3.4.1 符號定義 22
3.4.2 數學模型 24
3.5 研究設計與驗證流程 26
3.6 案例數據建構 28
3.7 數學模型驗證 29
3.8 基因演算法建構 40
3.8.1 染色體編碼 40
3.8.2 染色體解碼 43
3.8.3 初始解產生 46
3.8.4 配適度衡量 47
3.8.5 染色體選擇 47
3.8.6 交配（crossover） 47
3.8.7 突變（mutation） 48
3.8.8 世代染色體選擇 49
3.8.9 停止條件 49
第四章 實驗結果與分析 50
4.1 案例分析設計與程式作業環境 50
4.2 演算法初始解調校 50
4.3 演算法參數設定 53
4.3.1 案例三（ft08_2） 53
4.3.2 案例四（ft23） 54
4.3.3 案例五（ft75） 54
4.3.4 小結 54
4.4 演算法成果驗證-案例 55
4.4.1 案例一（ft08_1） 56
4.4.2 案例二（ft11） 56
4.4.3 案例五（ft75） 56
4.5 演算法成果驗證 56
4.5.1 在小型案例上的成果 56
4.5.2 在實際案例上的成果 57
第五章 結論與建議 59
5.1 結論 59
5.2 未來研究建議 60
參考文獻 61
附錄一 演算法參數設定測試結果-案例三 64
附錄二 演算法參數設定測試結果-案例四 65
附錄三 演算法參數設定測試結果-案例五 66

1.Bean, J. C. (1994). Genetic algorithms and random keys for sequencing and optimization. ORSA journal on computing, 6(2), 154-160.
2.Cakici, E., & Mason, S. J. (2007). Parallel machine scheduling subject to auxiliary resource constraints. Production Planning and Control, 18(3), 217-225.
3.Chan, F. T. S., Wong, T. C., & Chan, L. Y. (2006). Flexible job-shop scheduling problem under resource constraints. International journal of production research, 44(11), 2071-2089.
4.Chen, T. R., Chang, T. S., Chen, C. W., & Kao, J. (1995). Scheduling for IC sort and test with preemptiveness via Lagrangian relaxation. IEEE Transactions on Systems, Man, and Cybernetics, 25(8), 1249-1256.
5.Chien, C. F., & Chen, C. H. (2007). Using genetic algorithms (GA) and a coloured timed Petri net (CTPN) for modelling the optimization-based schedule generator of a generic production scheduling system. International Journal of Production Research, 45(8), 1763-1789.
6.Dauzère-Pérès, S., & Paulli, J. (1997). An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search. Annals of Operations Research, 70, 281-306.
7.Demir, Y., & İşleyen, S. K. (2013). Evaluation of mathematical models for flexible job-shop scheduling problems. Applied Mathematical Modelling, 37(3), 977-988.
8.Demir, Y., & İşleyen, S. K. (2014). An effective genetic algorithm for flexible job-shop scheduling with overlapping in operations. International Journal of Production Research, 52(13), 3905-3921.
9.Gao, J., Gen, M., Sun, L., & Zhao, X. (2007). A hybrid of genetic algorithm and bottleneck shifting for multiobjective flexible job shop scheduling problems. Computers & Industrial Engineering, 53(1), 149-162.
10.Garey, M. R., Johnson, D. S., & Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. Mathematics of operations research, 1(2), 117-129.
11.Gen, M., Tsujimura, Y., & Kubota, E. (1994, October). Solving job-shop scheduling problems by genetic algorithm. In Proceedings of IEEE International Conference on Systems, Man and Cybernetics (Vol. 2, pp. 1577-1582). IEEE.
12.Ho, N. B., Tay, J. C., & Lai, E. M. K. (2007). An effective architecture for learning and evolving flexible job-shop schedules. European Journal of Operational Research, 179(2), 316-333.
13.Holland, J. H. (1992). Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. MIT press.
14.Hong, T. Y., Chien, C. F., Wang, H. K., & Guo, H. Z. (2018). A two-phase decoding genetic algorithm for TFT-LCD array photolithography stage scheduling problem with constrained waiting time. Computers & Industrial Engineering, 125, 200-211.
15.Hur, Y., Bard, J. F., & Chacon, R. (2019). Hierarchy machine set-up for multi-pass lot scheduling at semiconductor assembly and test facilities. International Journal of Production Research, 57(14), 4351-4370.
16.Li, X., & Gao, L. (2016). An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem. International Journal of Production Economics, 174, 93-110.
17.Mousakhani, M. (2013). Sequence-dependent setup time flexible job shop scheduling problem to minimise total tardiness. International Journal of Production Research, 51(12), 3476-3487.
18.Müller, D., & Kress, D. (2022). Filter-and-fan approaches for scheduling flexible job shops under workforce constraints. International Journal of Production Research, 60(15), 4743-4765.
19.Norman, B. A., & Bean, J. C. (1999). A genetic algorithm methodology for complex scheduling problems. Naval Research Logistics (NRL), 46(2), 199-211.
20.Osman, I. H., & Kelly, J. P. (1996). Meta-heuristics: an overview. Meta-heuristics, 1-21.
21.Pinedo, M. (2012). Scheduling: Theory, Algorithms, and Systems. New York: Springer.
22.Shen, L., Dauzère-Pérès, S., & Neufeld, J. S. (2018). Solving the flexible job shop scheduling problem with sequence-dependent setup times. European Journal of Operational Research, 265(2), 503-516.
23.Tavakkoli-Moghaddam, R., Taheri, F., Bazzazi, M., Izadi, M., & Sassani, F. (2009). Design of a genetic algorithm for bi-objective unrelated parallel machines scheduling with sequence-dependent setup times and precedence constraints. Computers & Operations Research, 36(12), 3224-3230.
24.Tay, J. C., & Ho, N. B. (2008). Evolving dispatching rules using genetic programming for solving multi-objective flexible job-shop problems. Computers & Industrial Engineering, 54(3), 453-473.
25.Uzsoy, R., Martin-Vega, L. A., Lee, C. Y., & Leonard, P. A. (1991). Production scheduling algorithms for a semiconductor test facility. IEEE transactions on semiconductor manufacturing, 4(4), 270-280.
26.Wu, J. Z., & Chien, C. F. (2008). Modeling semiconductor testing job scheduling and dynamic testing machine configuration. Expert Systems with Applications, 35(1-2), 485-496.
27.Wu, R., Li, Y., Guo, S., & Xu, W. (2018). Solving the dual-resource constrained flexible job shop scheduling problem with learning effect by a hybrid genetic algorithm. Advances in Mechanical Engineering, 10(10), 1-14.