Compatibility graphs in scheduling for batch processing machines with setup times

In this paper, we address the problem of minimizing the makespan on batch processing with identical machines, subject to compatibility constraints. Two jobs are considered compatible if they can be processed simultaneously in the same batch. These compatibility constraints are represented by an undirected graph [Formula: see text], where compatible jobs correspond to adjacent vertices, and the batch capacity is limited to 2. We demonstrate that several sub-problems are solvable in polynomial time. Additionally, we propose exact polynomial algorithms to tackle these sub-problems. For the general case, we present a mixed-integer linear programming (MILP) formulation along with heuristic approaches. To evaluate the effectiveness of the proposed methods, we conduct computational experiments.