A new parallel-batch scheduling problem with non-identical jobs, compatible families, and setup times

This paper addresses a new parallel-batch scheduling problem on a single batch-processing machine, inspired by an industrial heat treatment process. The goal is forming and sequencing batches with non-identical jobs belonging to compatible families while minimizing the makespan. The longest job in each batch determines the batch processing time, and setup times depend on the sequence of dominant families. We propose a mixed-integer linear programming (MILP) formulation for the problem and some valid inequalities. Computational experiments demonstrate the formulation’s effectiveness and compare the performance of Cplex and Gurobi solvers.