Variable neighborhood search with memory for a single-machine scheduling problem with periodic maintenance and sequence-dependent set-up times

In this paper we study the problem of sequencing jobs in a single machine with programmed preventive maintenance and sequence-dependent set-up times. This is an NP-hard problem that has practical relevance because of its industrial applications (textile industry, chemical industry, manufacturing of printed circuit boards, etc.), in which machines need periodic preventive maintenance. An improved formulation of this problem is proposed. Using this new formulation computational experiments show that commercial software can solve exactly not only small-sized instances but also almost all medium-sized instances as well. For solving large-sized instances a heuristic method based on the Variable Neighborhood Search (VNS) is proposed. Specifically, a Skewed VNS with memory, that is, it allows, under certain conditions, the current solution to move to a worse solution and for the incorporation of memory in the search process. Computational experiments show the good performance of our proposed VNS-based method. For small- and medium-sized instances specifically, this method obtains very close-to-optimal solutions, finding the optimal solution in the almost every case. In larger instances our method performs better than previously published algorithms. Several statistical tests support these conclusions. All instances used in computational experiments have been taken from the literature.