Title: A hybrid ant colony optimisation algorithm for job shop problems and its convergence analysis

Authors: Yang Cao; Haibo Shi

Addresses: College of Information Science and Engineering, Northeastern University, Shenyang 110819, China; Department of Digital Factory, Shenyang Institute of Automation, CAS, Shenyang, 110016, China; University of Chinese Academy of Sciences, Beijing, 100049, China; Key Laboratory of Networked Control, CAS, Shenyang, 110016, China; Faculty of Information and Control Engineering, Shenyang Jianzhu University, Shenyang, 110168, China ' Department of Digital Factory, Shenyang Institute of Automation, CAS, Shenyang, 110016, China

Abstract: This paper presents a hybrid ant colony optimisation (HACO) algorithm for solving job shop problems. The criterion considered is the maximum completion time, the so-called makespan. The HACO algorithm improves the performance of intelligence optimisation algorithm, which adopts ant colony optimisation (ACO) algorithm to search in the global solution space, and tabu search (TS) algorithm is utilised as the local algorithm in each generation. The global asymptotic convergence of the hybrid algorithm is proved by Markov chain theory in the paper. By testing 13 hard benchmarks instance, the results demonstrate that the HACO algorithm is effective.

Keywords: ant colony optimisation; hybrid ACO; tabu search; convergence analysis; job shop problems; JSP; Markov chain theory; job shops.

DOI: 10.1504/IJMIC.2015.069944

International Journal of Modelling, Identification and Control, 2015 Vol.23 No.3, pp.230 - 237

Published online: 16 Jun 2015 *

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