本研究考慮了一個並行批量處理機器的問題，以在任意批量、不兼容系列、開始時間窗口的約束和適度決定下達到最小化製造時間。本研究首先通過混合整數程序化模型來格式化問題，並且也提供了所研究問題的下界。但因爲研究問題為NP-Hard且因應實務上須能解決大的問題，本研究亦將發展了一種基於分解的啟發式算法和進化算法，以便在計算時間作為一個側重點時獲得大規模問題的近似最優解。二維節約函數被引入來量化時間和容量空間被浪費的值。對於遺傳算法，我們提出了用於編碼的二維矩陣和一維表示，以及適當的二維交叉和突變以產生後代。此外，此遺傳算法旨在改善基於已開發分解的啟發式算法的解決方案品質，該啟發式被用作已開發遺傳算法的初始解。計算實驗表明，所提出的啟發式算法對於小規模問題的執行表現良好，並且可以在合理的計算時間內有效地處理大規模問題。此外，計算結果還表明，本研究提出的啟發式算法在答案品質 (Solution quality) 方面優於文獻中現有的啟發式算法。;This study considers a parallel batch processing machines problem to minimize the makespan under constraints of arbitrary lot sizes, incompatible families, start time windows, and machine eligibility determination. We first formulate the problem by a mixed-integer programming model and a lower bound for the studied problem is also provided. Due to the NP-hardness of the problem, we then develop a decomposition-based heuristic and an evolutionary algorithm to obtain a near-optimal solution for large-scale problems when computational time is a concern. A two-dimensional saving function is introduced to quantify the value of time and capacity space wasted. For the genetic algorithm, we propose a two-dimensional matrix and one-dimensional representation for encoding, and appropriate two-dimensional crossovers as well as mutations to generate offspring. In addition, the genetic algorithm aims to improve the quality of the solution found by the developed decomposition-based heuristic which is used as an initial solution for the developed genetic algorithm. Computational experiments show that the proposed heuristic algorithms perform well for small-size problems and can deal with large-scale problems efficiently within a reasonable computational time. Moreover, computational results also indicate that our proposed heuristics outperform an existing heuristic from the literature in terms of solution quality.
