Scheduling identical parallel batch processing machines involving incompatible families with different job sizes and capacity constraints

This paper investigates the problem of scheduling jobs on parallel batch processing machines with incompatible job families, non-identical job sizes, arbitrary job release times, and machine capacity constraints. A mixedinteger linear programming (MILP) model is established to minimize makespan. A lower bound is proposed to test the solution quality obtained from heuristic and metaheuristic algorithms. Since the problem is strongly NPhard, we propose five constructive and polynomially bounded heuristic algorithms. To improve the solutions obtained by these constructive algorithms, we describe a job family constraint-guided artificial immune system (CGAIS) based algorithm. In the proposed CGAIS algorithm, only jobs in the same family can be executed by the secondary immune response. The longest batch processing time rule is used to form the batches. The effectiveness of the proposed constructive and the CGAIS algorithms is empirically tested on the randomly generated problem instances. These computational results show that the proposed CGAIS algorithm can obtain better nearoptimal solutions than the existing algorithms.

Automated summary

This paper investigates the problem of scheduling jobs on parallel batch processing machines with incompatible job families, non-identical job sizes, arbitrary job release times, and machine capacity constraints. It proposes a new algorithm that can obtain better solutions than existing algorithms.