A binary multiple knapsack model for single machine scheduling with machine unavailability

This paper addresses the single machine weighted number of on-time jobs scheduling problem where the machine is unavailable during one or more maintenance periods and the jobs share a common due date. It models the problem as a binary multiple knapsack (MKP), and offers an alternative proof that the problem is NP-Complete in the strong sense. Subsequently, it shows that some large-sized instances can be solved exactly within less than a second using an off-the-shelf solver. For difficult instances, the paper proposes a variable neighborhood search based heuristic V that explores the MKP nature of the problem to determine near-optima. V is dotted with two mechanisms that speed its convergence toward near-global optima: a linked list data structure and a dynamic threshold acceptance criterion. Experimental results provide computational evidence of the efficiency and efficacy of V for benchmark MKP instances and for scheduling problems alike. It further discusses the robustness of V with respect to the initial solution and problem׳s parameters.