A general variable neighborhood search algorithm for a parallel-machine scheduling problem considering machine health conditions and preventive maintenance

In this paper, a parallel-machine scheduling problem considering machine health conditions and preventive maintenance is studied with the objective to minimize total tardiness and quality risk. The problem stems from semiconductor manufacturing where machines can be identified with different health conditions by Advanced Process Control (APC) tools. We develop two mixed integer linear programming models to formulate the problem. A general variable neighborhood search heuristic is proposed in which an efficient branch-and-bound algorithm is embedded as one of the search operators. The algorithm is compared with a classic tabu search heuristic that was proved to be very efficient in parallel-machine scheduling. Computational experiments show that the proposed algorithm outperforms the tabu search heuristic by averagely 2.20% in terms of the solution quality. Managerial insights are also derived that considering health information allows us to achieve a good balance between quality risk and delivery requirement. • A parallel-machine scheduling problem considering equipment health index is studied. • Two mathematical models are formulated to describe and solve the problems. • A branch-and-bound algorithm to solve the single-machine counterpart of the problem. • A general variable neighborhood search algorithm is developed to solve the problem. • Managerial insights about equipment health index are obtained.