A tabu-based adaptive large neighborhood search for scheduling unrelated parallel batch processing machines with non-identical job sizes and dynamic job arrivals

In this study, we investigate an unrelated parallel batch processing machines scheduling problem (UPBPMSP). A set of jobs with non-identical sizes and arbitrary ready times are scheduled on unrelated parallel batch processing machines with different capacities to minimize the makespan (i.e., the completion time of the last batch). Existing studies have either decomposed the scheduling problem into two sub-problems and employed population-based heuristic interaction for searching the best solutions or used neighborhood search algorithms to search the current solution’s neighborhood to find a better solution. However, the performances of these methods are not quite satisfactory due to the complicated interactions or oversimplified neighborhood search strategies, especially for large-scale UPBPMSPs. In this study, we propose a novel tabu-based adaptive large neighborhood search (TALNS) algorithm to obtain high-quality solutions for the UPBPMSP. To avoid complex interactions, we propose a new solution structure, and the proposed TALNS is applied to obtain the optimal solution structure of the UPBPMSP. Extensive experiments are conducted to evaluate the performance of the proposed algorithm on a total of 360 instances from the literature and 30 new instances. Numerical results demonstrate that the proposed TALNS outperforms the neighborhood search methods, which outperforms the population-based methods. With the proposed TALNS, 55 out of 360 instances’ best-known solutions are updated from this study.