Multiple-variable neighbourhood search for the single-machine total weighted tardiness problem. Issue 7 (3rd July 2017)

• Record Type: Journal Article
• Authors: Chung, Tsui-Ping; Fu, Qunjie; Liao, Ching-Jong; Liu, Yi-Ting
• Is Part Of: Engineering optimization. Volume 49:Issue 7(2017)
• Page Start: 1133
• Page End: 1147
• Publication Date: 2017-07-03
• Subjects: Metaheuristics -- variable neighbourhood search -- single-machine scheduling -- total weighted tardiness; Engineering design -- Periodicals; Mathematical optimization -- Periodicals; 620.0042
• DOI: 10.1080/0305215X.2016.1235707
• Languages: English
• ISSNs: 0305-215X

Abstract

ABSTRACT: The single-machine total weighted tardiness (SMTWT) problem is a typical discrete combinatorial optimization problem in the scheduling literature. This problem has been proved to be NP hard and thus provides a challenging area for metaheuristics, especially the variable neighbourhood search algorithm. In this article, a multiple variable neighbourhood search (m-VNS) algorithm with multiple neighbourhood structures is proposed to solve the problem. Special mechanisms named matching and strengthening operations are employed in the algorithm, which has an auto-revising local search procedure to explore the solution space beyond local optimality. Two aspects, searching direction and searching depth, are considered, and neighbourhood structures are systematically exchanged. Experimental results show that the proposed m-VNS algorithm outperforms all the compared algorithms in solving the SMTWT problem.