A no-delay single machine scheduling problem to minimize total weighted early and late work

Abstract

This paper investigates the no-delay single machine scheduling problem to minimize the total weighted early and late work. This criterion is one of the most important objectives in practice but has not been studied so far in the literature. First, we formulate the problem as a 0–1 integer programming formulation. Since the complexity of the problem is proven to be NP-hard, we propose two metaheuristics, namely General Variable Neighborhood Search and hybrid GRASP-VND, based on new neighborhood structures. The results demonstrate that all proposed methods can solve optimally instances up to 30 jobs. However, extensive computational experimentation, on large-sized instances, show that the quality of the solutions given by GVNS is better than that obtained by hybrid GRASP-VND algorithm.