Abstract
This study addresses the problem of minimizing the makespan for scheduling parallel batch machines, where jobs are processed in batches and each machine has the same capacity. The processing time for each batch includes setup, preheating, and heat preservation stages, introducing both serial and parallel batching characteristics. Jobs differ in size, weight, and ready time. A mixed-integer linear programming model is formulated and its correctness is verified using small-scale instances. As the problem is NP-hard, a novel heuristic algorithm is proposed, which utilizes a dynamic scheduling strategy to effectively reduce machine idle waiting time between batches. The time complexities of the algorithm are analyzed, and the worst-case performance of the new constructive heuristic is also evaluated. For small-scale problems, the performance of the heuristics is compared with the optimal solutions obtained from the MILP model, while for large-scale problems, comparisons are made with lower bounds. Three heuristic algorithms and two improved genetic algorithms are used as benchmark algorithms. The experimental results demonstrate that the new constructive heuristic outperforms these five algorithms in terms of scheduling performance.