應用模擬退火法於半導體批次作業製程之雙目標排程

Application of Simulated Annealing for Semiconductor Batch Process Scheduling With Bicriteria

李建鳴(Jian-Ming Li)

指導教授 ： 張玉鈍

國立臺北科技大學/管理學院/工業工程與管理系所/碩士(2006年)

https://doi.org/10.6841/NTUT.2006.00021

摘要

半導體成品測試製程中，需要經過一道預燒(burn-in)作業以提昇產品可靠度。然而預燒作業所需要的處理時間遠大於其它製程的加工時間，使得預燒作業成為整個成品測試流程中最關鍵之製程。
因此本研究針對具有成批處理特性的預燒作業，考量工作非同時抵達、不同工作大小(non-identical job size)、批次處理時間為同批工作中加工時間最長者、批次容量有限與每件工作皆有到期日限制之生產環境，運用模擬退火法探討以「總完工時間」最小化與「總延遲時間」最小化為績效指標的單一批次機台排程問題。並將同樣求解單一批次機台排程問題但未考慮工作大小之GRLPT、R1與R2等三種啟發式演算法加入工作大小限制，修改成GRLPT_S、R1_S與R2_S等三種啟發式演算法。以一系列的模擬實驗，分析探討各種排程方法在不同生產環境求解品質之優劣。由實驗結果顯示模擬退火法平均求解結果，於總完工時間指標會與GRLPT_S、R1_S、R2_S等三種啟發式演算法平均求解結果差異不大，但於總延遲時間指標卻能有效改善5.2%。

關鍵字

排程 ； 預燒爐 ； 批次生產 ； 模擬退火法

並列摘要

To improve the reliability of semiconductor products, burn-in operations is essential in the final testing processes. While the time needed at burn-in operation is much more than the other ones, it makes burn-in operations the bottleneck of the procedure in final test.
This study is aimed at burn-in operations characterized batch processing. Dynamic arrival of jobs with due date, non-identical job size, batch processing time as the longest processing among all jobs in a batch, and limitation on the sum of job sizes in a batch are considered. Procedure of simulated annealing to minimize makespan and total tardiness of jobs on a single batch-processing machine is proposed in the study. GRLPT, R1, and R2 heuristic algorithms in literature, in which jobs size is assumed identical, are modified as GRLPT_S, R1_S and R2_S in this study to accommodate job sizes in a batch. Various experiments were conducted to compare the proposed method with those modified algorithms. The computational results show that the proposed algorithm performs quite well as GRLPT_S, R1_S and R2_S on the criterion of makespan, while the proposed algorithm improves the criterion of total tardiness by 5.2 percent average.

並列關鍵字

Scheduling ； Batch processing ； Burn-in oven ； Simulated annealing

參考文獻

[7] Ahmadi, J.H., Ahmadi, R.H., Dasu, S., and Tang, C.S., “Batching and scheduling jobs on batch and discrete processors,” Operations Research, 40, 750-763. 1992.

[9] Brucker, P.,and Kovalyov, M.Y., “Single machine batch scheduling to minimize the weighted number of late jobs,” Mathematical Methods of Operations Research 43, pp.1-8, 1996.

[10] Chang, P.Y., Melouk, S.,and Domodaran, P., “Minimizing makespan for single machine batch process with non-identical job sizes using simulated annealing,” International of production economics, pp.141-147, 2004.

[11] Heragu, S.S., and Alfa, A.S., “Experimental analysis of simulated annealing based algorithms for the layout problem,” European Journal of Operational Research, 57, 190-202, 1992.

[12] Ho, Y.-C., and Moodie, C.L., “A hybrid approach for concurrent layout design of cells and their flow paths in a tree configuration,” International Journal of Production Research, 38(4), 895-928, 2000.