- 期刊
應用模擬退火法於雙機批次流程型工廠之排程
Sa-Based Heuristic for a Two-Machine Flowshop with Batch Processing Machines
摘要
以半導體產業內最終測試的預燒製程爲研究主題，探討雙機流程型工廠，且機器具批次處理之特性。批次處理是可將數個工作合併爲一批同時處理，而工作批次處理時間等於該批中工作處理時間最長者。爲了提升兩部批次處理機器之流程型工廠的使用效率，提出以模擬退火法爲基的SAH演算法，使得最大完工時間最小化。對於10個工作數的問題，SAH演算結果與混合整數規畫模式所得的最佳解比較，30個執行例子中有27個爲最佳解。進一步評估SAH在較大工作數問題的績效，與下界值比較，是以相對誤差百分比(E(下標 L))爲指標；並與局部搜尋法爲基的演算法比較，衡量指標爲SAH對該演算法的改善百分比(PI)。實驗結果顯示，SAH演算法在效率與效果的績效上，皆有良好的表現。
並列摘要
The final test burn-in operation of the semiconductor industry is chosen as the topic for exploring a two-machine flowshop with batch processing machines. A batch processing machine is one that can simultaneously process several jobs in one batch. The processing time of a batch is equal to the largest processing time of any job in the batch. In order to improve efficiency of a flowshop with two batch processing machines, an effective simulated annealing based heuristic (SAH) is proposed to schedule the jobs to minimize the makespan. When used in 10-job problems, and the results of the SAH are compared with those of the mixed integer linear programming (MILP) model, in 27 out of 30 instances, the SAH results were optimum. Furthermore, in order to evaluate the performance of the SAH in larger batch problems, the results were compared with those using the lower bound and those using an existing local search based heuristic, respectively. Performance evaluation indexes used in the comparisons are the relative error percentage for the lower bound (E(subscript L)) and the percentage improvement (PI) for the local search based heuristic. The results show that the SAH algorithm is efficient and effective.