Heuristic methods for the single-machine scheduling problem with periodical resource constraints

Abstract

In the last years, researchers have been paying special attention to scheduling problems with scarce resource consumption and periodic maintenance activities with a view to the adoption of more realistic assumptions. This paper aims at presenting heuristics to a single-machine scheduling environment with periodical resource constraints. In this new variant of the single-machine scheduling problem, in each production period, there are resource consumption constraints. To the best of our knowledge, the proposed variant has not been addressed in the revised literature. An integer linear programming model is presented based on a bin packing formulation taking two packing constraints into consideration. The objective function adopted is makespan minimization, and relative deviation is used as a performance criterion. Since the problem under study is NP-hard, heuristic algorithms are proposed to obtain high-quality solutions in acceptable computational times. Eighteen constructive heuristics, two local search heuristics, and a hybrid matheuristics, based on the size reduction and simulated annealing algorithms, have been presented. The extensive computational experience carried out shows that the proposed local search algorithms, as well as the proposed matheuristics, are promising tools to solve large-sized instances.