Neighborhood search procedures for single machine tardiness scheduling with sequence-dependent setups

In this paper we address the 1/sij/∑wjTj problem, for which we improve the time complexities of searching the interchange, insertion and twist neighborhoods from to . Further, we improve the time complexity of searching the insertion and twist neighborhoods in which a candidate job is selected from among k jobs nearest to the selected job from to .