本提案書將探討平行批次處理問題。研究議題來自於半導體生產的實際條件要求，每一工件有特定配方的需求且具有不同的晶圓數量，同一批次處理可以同時處理數工件的晶圓，但批次有總上下限晶圓數量的限制；工件發放至平行機台後的某一段時間內必須進行處理，否則將成為瑕疵品；機台因為化學藥劑的使用不同，且化學藥劑於期間內耗用完後，會另外安裝不同藥劑，所以同一機台在不同期間有不同機台合適度的現象。本研究將以極小化Makespan為目標。我們首先將提出一混合整數規劃模型，以求取其最佳解。但因爲研究問題為NP Hard且因應實務上須能解決大的問題，本研究亦將發展以分解法為基礎的啟發式解法，這發展方向也常見於有工件家族(Job family)要求的批次處理問題。本研究最後將評估啟發式解法之求解運算時間(Computational time)與答案品質(Solution quality)。 ;In this proposal, we consider a parallel batch processing problem when minimizing the makespan under constraints of arbitrary lot sizes, machine eligibility, time window, and incompatible job families. Different than the previous researches, the machine’s eligibility in our study is not known in advance and will be determined later after the set of materials is assigned to machines. To the best of our knowledge, there is no published papers which deal with the problem. We will formulate a mixed-integer programming model for solving the problem optimally. However, due to the NP-Hardness of our problem, decomposition approach has been successfully applied to solve a variety of batching problems, especially with incompatible job families. Here in this proposal, we will also propose a decomposition-based heuristic algorithm to obtain a near-optimal solution for large-scale instances when the computation time is a concern.
