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

作者：Liao Ching Jong^*; Cheng Che Ching

来源：Computers & Industrial Engineering, 2007, 52(4): 404-413.

DOI：10.1016/j.cie.2007.01.004

• scheduling
• variable neighborhood search
• tabu search
• common due date
• weighted earliness/tardiness

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.

• 出版日期2007-5