A New Bi-Objective Batch Scheduling Problem: NSGA-II-and-Local-Search-Based Memetic Algorithms

Batch scheduling problems deal with jobs to be processed in batches in many industrial production systems. They are hard to solve. This work proposes a novel bi-objective batch scheduling problem with the constraints of release time and sequence-dependent setup time. As an important characteristic of the concerned problem, the number of late jobs within a batch varies with its start time. A mixed-integer linear program is proposed to describe this problem. Two objectives, i.e., minimizing the total number of late jobs and setup time, are considered. Two memetic algorithms by integrating a non-dominated sorting genetic algorithm II (NSGA-II) and 2-opt local search are designed to solve the concerned problem. They adopt different crossover operators, i.e., partially mapped one and precedence preserved one. By comparing the results of the proposed algorithms with their peers on extensive experiments, we conclude that the proposed algorithms get much better Pareto fronts than their peers at the expense of more execution time. Yet, their speeds are fast enough to solve the problems with industrial scales and thus prove the readiness to put them in industrial use.