Scheduling for a Single Semiconductor Batch-Processing Machine to Minimize Total Weighted Tardiness

單機批次加工機台以總加權延遲時間爲目標之排程問題

周富得(Fuh-Der Chou) ； 王惠梅(Hui-Mei Wang)

《工業工程學刊》 25卷2期 (2008/03) Pp. 136-147

https://doi.org/10.29977/JCIIE.200803.0005

摘要

本文係針對單一批次加工機台的排程問題進行探討，此排程問題中工作具有尺寸大小、釋放時間、加工時間、交期以及工作權重等相關屬性。除此之外，批次加工機台在其最大容量的限制下可以同時加工數個工作，並以同一批次內工作最大加工時間爲其機台加工的作業時間。針對此排程問題係以總加權延遲時間作爲衡量排程結果的基準，並提出數學規劃法以及兩種不同混合啟發式演算法－法則爲基的演算法(rule-based algorithm)與基因演算爲基的演算法(GA-based algorithm)。混合啟發式演算法的架構主要分爲二部份：形成工作順序以及形成加工批次。其中在形成加工批次的階段不論是法則爲基的演算法或基因演算爲基的演算法均使用動態規劃法來負責組批工作，而在形成工作順序的階段中，法則爲基的演算法則應用各種不同簡單指派法則來求得工作順序，而基因演算爲基的演算法乃應用基因運算子來產生不同的工作順序。透過本研究的實驗結果得知，最後的排程結果會受到不同工作順序的結果而有明顯的差異，以及基因演算爲基的演算法在工作數小的問題幾乎均可以在極短的時間內得到最佳解，而針對工作數較大的問題此方法亦可以在合理的求解時間內獲得穩定且不錯的近似最佳解。

關鍵字

總加權延遲時間 ； 動態規劃法 ； 批次加工機台 ； 基因演算法

並列摘要

This paper considers the scheduling problem of a single semiconductor batch-processing machine with job release times, non-identical job sizes, distinct due dates, and weights to minimize the total weighted tardiness. A batch-processing machine can process several jobs simultaneously as a batch, and the processing time of a batch is equal to the longest processing time among all jobs in the batch. According to the literature review of Mathirajan and Sivakumar and the studies of Perez et al., the problem dealt with in this paper has not been studied so far. Therefore, we proposed a mathematical modeling approach and two kinds of hybrid heuristics, including a rule-based algorithm and a genetic algorithm based (GA-based) algorithm in which a dynamic programming (DP) algorithm is integrated to obtain an optimal batching solution for a given job sequence. The experimental results indicated that job sequence is an important factor for the problem. Particularly, the GA-based algorithm significantly outperformed the rule-based algorithm in terms of the quality of solutions for small-job problems. Likewise, the solutions were obviously considerably improved compared with the mathematical modeling approach for large-job problems.

並列關鍵字

total weighted tardiness ； dynamic programming ； batch-processing machine scheduling ； genetic algorithm

參考文獻

Balasubramanian, H.,L. Monch,J. Fowler,M. Pfund(2004).Genetic algorithm based scheduling of parallel batch machines with incompatible job families to minimize total weighted tardiness.International Journal of Production Research.42,1621-1638.

Chandru, V.,C. Y. Lee,R. Uzsoy(1993).Minimizing total completion time on batch processing machines.International Journal of Production Research.31,2097-2121.

Chang, P. C.,J. C. Hsieh,C. H. Liu(2006).A case-injected genetic algorithm for single machine scheduling problems with release time.International Journal of Production Economics.103,551-564.

Chang, P. C.,H. M. Wang(2004).A heuristic for a batch processing machine scheduled to minimize total completion time with non-identical job sizes.International Journal of Advanced Manufacturing Technology.24,615-620.

Chou, F. D.,P. C. Chang,H. M. Wang(2005).A hybrid genetic algorithm to minimize makespan for the single batch machine dynamic scheduling problem.International Journal of Advanced Manufacturing Technology.31,350-359.