A variable neighborhood search for minimizing single machine weighted earliness and tardiness with common due date

Although the concept of just-in-time (JIT) production systems has been proposed for over two decades, it is still important in real-world production systems. In this paper, we consider minimizing the total weighted earliness and tardiness with a restrictive common due date in a single machine environment, which has been proved as an NP-hard problem. Due to the complexity of the problem, metaheuristics, including simulated annealing, genetic algorithm, tabu search, among others, have been proposed for searching good solutions in reasonable computation times. In this paper, we propose a hybrid metaheuristic that uses tabu search within variable neighborhood search (VNS/TS). There are several distinctive features in the VNS/TS algorithm, including different ratio of the two neighborhoods, generating five points simultaneously in a neighborhood, implementation of the B/F local search, and combination of TS with VNS. By examining the 280 benchmark problem instances, the algorithm shows an excellent performance in not only the solution quality but also the computation time. The results obtained are better than those reported previously in the literature. (c) 2007 Flsevier Ltd. All rights reserved.