A filter-and-fan based heuristic for the scheduling problem of parallel batch-processing machines with deterioration consideration and non-identical job release times

We investigate a scheduling problem for the parallel batch-processing machines with deterioration consideration and non-identical job release times. The objective is to minimize the makespan. A linear programming model is formulated. Considering the complexity of the problem, a filter-and-fan based heuristic is proposed. Three neighborhoods based on the characteristics of the problem are designed and used in the filter-and-fan method. To probably avoid the search being trapped in a local optimum, a reconstructive strategy is proposed to strengthen the dispersity of solutions in the search process. A speedup strategy is also proposed to shorten the run time of the proposed method. The computational results show that for most of instances with small scale the heuristic can obtain optimal solutions. For all instances with large scale, the heuristic significantly outperform the standard commercial solver both on run time and quality of solution.