動態批次機台排程問題之探討

A study on dynamic batch processor scheduling problem

王惠梅(Hui-Mei Wang)

指導教授 ： 張百棧

元智大學/工程學院/工業工程與管理學系/博士(2004年)

摘要

此論文主要探討半導體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.

並列關鍵字

Batch processor ； Makespan ； Total completion time ； Heuristic algorithm

參考文獻

[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.

[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.

[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.