Skip Navigation



IMA Journal of Management Mathematics Advance Access published online on March 14, 2007
IMA Journal of Management Mathematics, doi:10.1093/imaman/dpm009
This Article
Right arrow Full Text (PDF)
Right arrow All Versions of this Article:
18/2/117    most recent
dpm009v1
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Sevkli, M.
Right arrow Articles by Aydin, M. E.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The authors 2007. Published by Oxford University Press on behalf of the Institute of Mathematics and its Applications. All rights reserved.

Parallel variable neighbourhood search algorithms for job shop scheduling problems

Mehmet Sevkli{dagger}

Department of Industrial Engineering, Fatih University, Buyukcekmece, Istanbul, Turkey

M. Emin Aydin{ddagger}

Department of Computing and Information Systems, University of Bedfordshire, Luton, UK

{dagger} Email: msevkli{at}fatih.edu.tr

{ddagger} Corresponding author. Email: mehmetaydin{at}acm.org, mehmet.aydin{at}beds.ac.uk

Received on 1 April 2006. Accepted on 2 February 2007.


  Abstract

Variable neighbourhood search (VNS) is one of the most recent metaheuristics used for solving combinatorial optimization problems in which a systematic change of neighbourhood with a local search is carried out. However, as happens with other metaheuristics, it takes a long time to reach some useful solutions while solving some sort of hard combinatorial problems such as job shop scheduling (JSS). Parallelization is one of the most considerable policies to overcome this matter. In this paper, firstly, a number of VNS algorithms are examined for JSS problems and then four different parallelization policies are taken into account to determine efficient parallelization for VNS algorithms. The experimentation reveals the performance of various VNS algorithms and the efficiency of policies to follow in parallelization. In the end, the unilateral-ring topology, a noncentral parallelization method, is found as the most efficient policy.

Keywords: variable neighbourhood search; parallel neighbourhood search; job shop scheduling


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer:
Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.