VNS approach for total tardiness minimization in a single machine scheduling problem with periodic resource constraints

Abstract

In this paper, we consider a recently introduced variant of a single machine scheduling problem with periodical resource constraints. The goal is to minimize the total tardiness of all jobs that need to be scheduled on a single machine, taking into account the time and resource consumption constraints per production period. Since the considered problem is NP-hard, we propose a metaheuristic approach using the Variable neighborhood search (VNS). The performance of the VNS method is evaluated on a set of test instances from the literature with up to 1000 jobs. The obtained results are compared with the results of other methods from the literature and show the efficiency of the proposed VNS approach over the other algorithms.