Journal
COMPUTERS & OPERATIONS RESEARCH
Volume 36, Issue 6, Pages 2105-2110Publisher
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cor.2008.07.009
Keywords
Single machine scheduling; Total weighted tardiness; Variable neighborhood search
Categories
Funding
- National Natural Science Foundation for Distinguished Young Scholars of China [70425003]
- National 863 High-Tech Research and Development Program of China [2006AA04Z174]
- National Natural Science Foundation of China [60674084]
Ask authors/readers for more resources
This paper investigates the single machine total weighted tardiness problem, in which a set of independent jobs with distinct processing times,weights, and due dates are to be scheduled on a single machine to minimize the sum of weighted tardiness of all jobs. This problem is known to be strongly NP-hard, and thus provides a challenging area for metaheuristics. A population-based variable neighborhood search (PVNS) algorithm is developed to solve it. This algorithm differs from the basic variable neighborhood search (VNS). First, the PVNS consists of a number of iterations of the basic VNS, and in each iteration a population of solutions is used to simultaneously generate multiple trial solutions in a neighborhood so as to improve the search diversification. Second, the PVNS adopts a combination of path-relinking, variable depth search and tabu search to act as the local search procedure so as to improve the search intensification. Computational experiments show that the proposed PVNS algorithm can obtain the optimal or best known solutions within a reasonable computation time for all standard benchmark problem instances from the literature. (C) 2008 Elsevier Ltd. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available