Abstract
在半導體產業□，光罩（mask）為晶圓製造不可或缺的曝光基準，所以良好的光罩生產管理，才能有好的晶圓的製造管理。滿足交期為晶圓製造的主要目標，而要滿足晶圓製造的交期必先滿足光罩的交期。所以，本論文的目的即在研究如何盡量滿足光罩生產的交期，亦即讓其總延遲時間最小。在光罩的加工流程中，電子光束機其價值昂貴且為主要的瓶頸機台，其加工特性有三，分別為：1. 批次處理（batch processing）；每次多片同時加工。2. 除整備時間（抽真空）外，批量加工時間為產品加工時間的總和。3. 不同類別產品不能在同一批量加工。因為批量加工機台、單一類別或兩類別產品的最小總延遲時間排程研究，藉由瓶頸機台的排程法則研究，來降低光罩生產時延遲交貨情形，以達到其生產時的主要目標。由於此最小總延遲時間的排程問題為 NP-hard的問題，所以本論文的重點在探討有效的啟發式演算法。本論文所研究的問題有兩種，第一種問題假設產品有加工順序的限制，在此假設下，利用分支界限法求出問題最佳解，並根據批量加工特性提出數個啟發式演算法，再針對各種產品到期日的延遲情形及產品比例將啟發式排程方法和最佳解做比較，以分析各個近似解的優劣及可行性。在第二種問題則無此假設，稱為一般批量生產問題，由於問題以分支界限法求解時間過長，因此僅針對啟發式演算法做實驗比較，找出較佳的排程方法。