臺灣博碩士論文加值系統

此論文主要探討半導體IC最終測試廠預燒製程之排程研究，其中預燒爐子(Oven)或稱批次機台可以在同一時間內加工數個工作，並以同一批次內之最大加工時間作為此批次的加工時間，除此之外，考量實務預燒作業的狀況，此論文將各工作具有不同批量以及工作在不同時間點進入生產系統兩項因素納入考慮。而此排程問題在靜態環境中已被證明是NP hard。
本論文主要探討單機批次機台以及平行批次機台的生產環境，其中在單機生產環境乃分別探討以「流程時間」最小化以及「所有工作完成時間」最小化為目標函數的排程問題，而在平行機台的生產環境則探討以「所有工作完成時間」最小化為目標函數的排程問題。在批次作業的環境下，不論是單機或是平行機台，其排程問題均牽涉到兩個層面：(1) 如何將欲加工的工作分為幾個工作群組，及(2) 安排各個已分派好的工作群組至加工機器上進行加工。本論文乃分根據此一特性提出相關性質，並以此發展出不同的啟發式演算法，同時並建立各別的限制規劃模式，以驗證各啟發式演算法的求解品質。

This thesis studies the dynamic scheduling problem of the burn-in operations in final testing process of semiconductor IC industry. A batch processor of the burn-in operation can process several jobs simultaneously, where jobs are compatible with different capacity consumption (job size), and the processing time of each batch is represented by the largest processing time of jobs within the batch. This problem, with static case and processing times of all jobs are the same, is proven to be NP hard by Uzsoy.
Two scheduling environments which include single batch processor and parallel batch processors are considered in this thesis. On single batch processor environment, we investigate the scheduling problems of minimizing total flow time and makespan, respectively. On parallel batch processors environment, minimizing makespan is considered. Batch processor scheduling problems basically involve assigning jobs into batches and determining the batch sequence on batch processors. According to the feature, some properties were proposed to develop heuristic algorithms, and constraint programming models are formulated to evaluate the performance of those heuristic algorithms. Computational experiments showed that those heuristic algorithms are capable of obtaining good-enough solutions in modest CPU time.

中文摘要 ………………………………………………………………… i
英文摘要 ………………………………………………………………… ii
誌謝 ……………………………………………………………………… iii
目錄 ……………………………………………………………………… v
表目錄 …………………………………………………………………… vi
圖目錄 …………………………………………………………………… vii
第一章 緒論 ………………………………………………………… 1
1.1 研究背景與動機 …………………………………………… 1
1.2 研究目的 …………………………………………… 2
1.3 研究範圍與問題基本定義 …………………………………… 3
1.4 論文架構 …………………………………………………… 4
第二章 文獻探討 …………………………………………………… 5
2.1 s-batching排程問題之文獻探討 ………………………… 5
2.2 p-batching排程問題之文獻探討 ………………………… 6
第三章 限制規劃模式 ……………………………………………… 15
3.1 已知變數 …………………………………………………… 16
3.2 輔助變數 …………………………………………………… 17
3.3 決策變數 …………………………………………………… 17
3.4 限制規劃模式一 …………………………………………… 18
3.5 限制規劃模式二 …………………………………………… 19
第四章 啟發式演算法 …………………………………………… 24
4.1 符號定義 ……………………………………………………… 24
4.2 動態單一預燒爐子以「總流程時間」或「總完工時間」
最小化為排程目標 ………………………………………… 25
4.2.1 性質說明 ………………………………………… 25
4.2.2 兩階段啟發式演算法 ……………………………… 31
4.2.3 多順序啟發式演算法 ……………………………… 35
4.3 動態單一預燒爐子以「所有工作完成的時間點 」為排
程目標 ………………………………………………………… 38
4.3.1 聚散演算法 ………………………………………… 38
第五章 結果分析 …………………………………………………… 44
5.1 以「流程時間」為排程目標 ……………………………… 44
5.1.1 兩階段啟發式演算法 ……………………………… 44
5.1.2 多順序啟發式演算法 ……………………………… 45
5.2 以「所有工作完成的時間點」為排程目標 ……………… 50
5.2.1 單機－聚散演算法 ………………………………… 50
5.2.2 平行機台－限制規劃模式2 ………………………… 54
第六章 結論與未來展望 …………………………………………… 57
6.1 結論 ………………………………………………………… 57
6.2 未來展望 …………………………………………………… 58
參考文獻 ………………………………………………………………… 60
附錄一 ………………………………………………………………… 63
附錄二 ………………………………………………………………… 69

[1] Ahmadi, J.H., Ahmadi, R.H., Dasu, S., and Tang, C.S., 1992. Batching and scheduling jobs on batch and discrete processors, Operations Research, 40, 750-763.
[2] Baker, K.R., 1974. Introduction to Sequencing and Scheduling, John Wiley & Sons Inc., New York.
[3] Chand, S., Tuaub, R., and Uzsoy, R., 1996. Single-machine scheduling with dynamic arrivals: Decomposition results and an improved algorithm, Naval Research Logistics, 43, 709-719.
[4] Chandru, V., Lee, C.-Y, and Uzsoy, R., 1993. Minimizing total completion time on a batch processing machines, International Journal of Production Research, 31, 2097-2121.
[5] Chandru, V., Lee, C.-Y, and Uzsoy, R., 1993. Minimizing total completion time on a batch processing machines with job families, Operations Research Letters, 13, 61-65.
[6] Coffman, E.G., Yannakakis, M., Magazine, M.J., and Santos C., 1990. Batch sizing and job sequencing on a single machine. Annals of Operations Research, 26, 135-147.
[7] Ng Daniel, C.T., Cheng, T.C.E. and Kovalyov, M.Y., 2004. Single machine batch scheduling with jointly compressible setup and processing times, European Journal of Operational Research, 153, 211-219.
[8] Dessouky, M.I. and Deogun, J.S., 1981. Sequencing jobs with unequal ready times to minimize mean flow time, SIAM J. Comput., 10, 192-202.
[9] DuPont, L. and Dhaenens-Flipo, C., 2002. Minimizing the makespan on a batch machine with non-identical jobs sizes: an exact procedure, Computers & Operations Research, 29, 807-819.
[10] DuPont, L. and Ghazvini, F.J., 1997. A branch and bound algorithm for minimizing mean flow time on a single batch processing machine, International Journal of Industrial Engineering, 4, 197-203.
[11] Ghazvini, F.J. and DuPont, L., 1998. Minimizing mean flow times criteria on a single batch processing machine with non-identical jobs sizes, International Journal of Production Economics, 55, 273-280.
[12] Hochbaum, D.S. and Landy, D., 1997. Scheduling semiconductor burn-in operations to minimize total flowtime, Operations Research, 45, 874-885.
[13] Kempf, K.G., Uzsoy, R., and Wang, C.-S., 1998. Scheduling a single batch processing machine with secondary resource constraints, Journal of Manufacturing System, 17, 37-51.
[14] Lee, C.Y., Uzsoy, R. and Martin-Vega, L.A., 1992. Efficient algorithms for scheduling semiconductor burn-in operations, Operations Research, 40, 764-774.
[15] Lee, C.Y. and Uzsoy, R., 1999. Minimizing makespan on a single batch processing machine with dynamic job arrivals, International Journal of Production Research, 37, 219-236.
[16] Li, C.L. and Lee, C.Y., 1997. Scheduling with agreeable release times and due dates on a batch processing machine, European Journal of Operational Research, 96, 564-569.
[17] Melouk, S., Damodaran, P. and Chang, P.Y., 2004. Minimizing makespan for single machine batch processing with non-identical job sizes using simulated annealing, International Journal of Production Economics, 87, 141-147.
[18] Sung, C.S. and Choung, Y.I., 2000. Minimizing makespan on a single burn-in oven in semiconductor manufacturing, European Journal of Operational Research, 120, 559-574.
[19] Sung, C.S., Choung, Y.I., Hong, J.M., and Kim, Y.H., 2002. Minimizing makespan on a single burn-in oven with job families and dynamic job arrivals, Computer & Operations Research, 29, 995-1007.
[20] Uzsoy, R., 1994. Scheduling a single batch processing machine with non-identical job sizes, International Journal of Production Research, 32, 1615-1635.
[21] Wang, C.S., and Uzsoy, R., 2002. A genetic algorithm to minimize maximum lateness on a batch processing machine, Computers & Operations Research, 29, 1621-1640.
[22] Zhang, G., Cai, X., Lee, C.-Y., and Wong, C.K., 2001. Minimizing makespan on a single batch processing machine with nonidentical job sizes, Naval Research Logistics, 48, 226-240.