Title: Variable neighbourhood search algorithms applied to job-shop scheduling problems

Authors: Pisut Pongchairerks

Addresses: Faculty of Engineering, Production Engineering Program, Thai-Nichi Institute of Technology, 1771/1 Pattanakarn Rd., Suanluang, Bangkok, 10250, Thailand

Abstract: This research attempts to find the neighbourhood structures of the variable neighbourhood search (VNS) algorithm well fitting to job-shop scheduling problem (JSP). So as to achieve this objective, this research adapts the seven neighbourhood structures given by the travelling salesman problem's literature to create the seven VNS algorithms for JSP. The performances of these proposed VNS algorithms are then compared to the performances of several existing algorithms, i.e., ACO, PSO and VNS algorithms taken from previously published literature. The comparison indicates that all proposed VNS algorithms perform better than the ACO and PSO algorithms with the significance level of 0.05. This paper finally reveals the neighbourhood structures performing well to JSP.

Keywords: variable neighbourhood search; VNS; job shop scheduling; ant colony optimisation; particle swarm optimisation; ACO; PSO.

DOI: 10.1504/IJMOR.2014.065421

International Journal of Mathematics in Operational Research, 2014 Vol.6 No.6, pp.752 - 774

Received: 04 Apr 2013
Accepted: 10 Jul 2013
Published online: 31 Oct 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article