Parallel-machine group scheduling with inclusive processing set restrictions, outsourcing option and serial-batching under the effect of step-deterioration

This paper investigates a parallel-machine group scheduling problem where non-identical jobs with arbitrary sizes and inclusive processing set restrictions can be either processed on in-house parallel machines in the form of serial batch or outsourced with cost. The objective of our study is aimed at minimizing the weighted sum of the in-house makespan and the total outsourcing cost for a platform manufacturing enterprise. Some structural properties are identified for the optimal solution in some special cases of the studied problem, which contribute to the optimal solution for the studied problem. Further, based on these properties, a novel hybrid algorithm VNS–NKEA is proposed to solve the studied problem, which integrates neighborhood knowledge-based evolutionary algorithm (NKEA) and variable neighborhood search (VNS). To demonstrate the better performance including solution quality and the convergence speed of the proposed algorithm, computational experiments are conducted to evaluate its performance by comparing with other proposed algorithms. The experiment results show that the hybrid algorithm performs quite better than other compared algorithms for each instance, which reflect that the hybrid algorithm can solve the studied problem effectively.