Optimising batch scheduling on non-identical parallel machines: lower bounds, MIP, branch-and-price, and heuristics

This paper addresses a scheduling problem involving a set of diverse jobs processed in batches. Each job has its own processing time and size. Notably, the processing time of any batch is determined by the longest processing time among the jobs it contains. These batches are scheduled on parallel machines with non-identical capacities, ensuring that the total size of the jobs in any batch does not exceed the capacity of the assigned machine. The objective is to minimise the maximum makespan across all machines, where the makespan is defined as the sum of the processing times of all batches on a machine. To tackle this problem, the paper proposes lower bounds, a mixed-integer programming formulation, and a branch-and-price algorithm. Additionally, five rule-based heuristics and a beam search algorithm are introduced. An extensive computational study demonstrates that the proposed solution methods outperform existing approaches in the literature in terms of both solution quality and computational efficiency. Furthermore, the proposed methods achieve best-known solutions for the first time in the literature, demonstrating their significant improvement over existing approaches.