A Dual-List Feature-Driven Heuristic for the Batch Processing Machine Scheduling Problem

This paper addresses the multi-objective scheduling problem for unrelated parallel batch processing machines under different job arrival times. We propose a dual-list feature-driven (DLFD) heuristic algorithm to simultaneously minimize the completion time, total delay time, and total energy consumption. Firstly, the heuristic selects a machine based on the machine’s capacity and energy consumption characteristics. Secondly, a job is selected from two candidate job lists governed by machine capacity and batch processing time constraints, thereby reducing the search space and improving solution quality. To validate the effectiveness of the DLFD heuristic, experiments of three different scales were designed to compare its performance against classic composite dispatching rules. The results demonstrate that the proposed heuristic achieves a significantly superior Pareto front compared to the traditional rules and exhibits strong robustness in solving problems of various scales.