具機台合適度決定與時間窗口限制之平行批次處理問題

本提案書將探討平行批次處理問題。研究議題來自於半導體生產的實際條件要求，每一工件有特定配方的需求且具有不同的晶圓數量，同一批次處理可以同時處理數工件的晶圓，但批次有總上下限晶圓數量的限制；工件發放至平行機台後的某一段時間內必須進行處理，否則將成為瑕疵品；機台因為化學藥劑的使用不同，且化學藥劑於期間內耗用完後，會另外安裝不同藥劑，所以同一機台在不同期間有不同機台合適度的現象。本研究將以極小化Makespan為目標。我們首先將提出一混合整數規劃模型，以求取其最佳解。但因爲研究問題為NP Hard且因應實務上須能解決大的問題，本研究亦將發展以分解法為基礎的啟發式解法，這發展方向也常見於有工件家族(Job family)要求的批次處理問題。本研究最後將評估啟發式解法之求解運算時間(Computational time)與答案品質(Solution quality)。