應用模擬退火法於雙機批次流程型工廠之排程

Sa-Based Heuristic for a Two-Machine Flowshop with Batch Processing Machines

以半導體產業內最終測試的預燒製程為研究主題，探討雙機流程型工廠，且機器具批次處理之特性。批次處理是可將數個工作合併為一批同時處理，而工作批次處理時間等於該批中工作處理時間最長者。為了提升兩部批次處理機器之流程型工廠的使用效率，提出以模擬退火法為基的SAH 演算法，使得最大完工時間最小化。對於10 個工作數的問題，SAH 演算結果與混合整數規畫模式所得的最佳解比較，30 個執行例子中有27 個為最佳解。進一步評估SAH在較大工作數問題的績效，與下界值比較，是以相對誤差百分比 （EL） 為指標；並與局部搜尋法為基的演算法比較，衡量指標為SAH 對該演算法的改善百分比 （PI）。實驗結果顯示，SAH 演算法在效率與效果的績效上，皆有良好的表現。

The final test burn-in operation of the semiconductor industry ischosen as the topic for exploring a two-machine flowshop with batchprocessing machines. A batch processing machine is one that cansimultaneously process several jobs in one batch. The processing time ofa batch is equal to the largest processing time of any job in the batch. Inorder to improve efficiency of a flowshop with two batch processingmachines, an effective simulated annealing based heuristic (SAH) isproposed to schedule the jobs to minimize the makespan. When used in10-job problems, and the results of the SAH are compared with those of themixed integer linear programming (MILP) model, in 27 out of 30 instances,the SAH results were optimum. Furthermore, in order to evaluate theperformance of the SAH in larger batch problems, the results werecompared with those using the lower bound and those using an existinglocal search based heuristic, respectively. Performance evaluation indexesused in the comparisons are the relative error percentage for the lower bound (EL) and the percentage improvement (PI) for the local search basedheuristic. The results show that the SAH algorithm is efficient andeffective.