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.
