Title: Bee colony optimisation algorithm with big valley landscape exploitation for job shop scheduling problems

Authors: Li-Pei Wong, Chi Yung Puan, Malcolm Yoke Hean Low, Yi Wen Wong, Chin Soon Chong

Addresses: School of Computer Engineering, Nanyang Technological University, Nanyang Avenue, 639798, Singapore; School of Computer Sciences, Universiti Sains Malaysia, 11800 USM, Pulau Pinang, Malaysia. ' School of Computer Engineering, Nanyang Technological University, Nanyang Avenue, 639798, Singapore. ' School of Computer Engineering, Nanyang Technological University, Nanyang Avenue, 639798, Singapore. ' School of Computer Engineering, Nanyang Technological University, Nanyang Avenue, 639798, Singapore. ' Singapore Institute of Manufacturing Technology, 71 Nanyang Drive, 638075, Singapore

Abstract: Job shop scheduling problem (JSSP) is an NP-hard problem that is closely related to scheduling activities in manufacturing industry. This paper presents an improved bee colony optimisation algorithm with Big Valley landscape exploitation (BCBV) as a biologically inspired algorithm to solve the JSSP problem. The BCBV algorithm mimics the bee foraging behaviour where information of newly discovered food source is communicated via waggle dances. In the algorithm, the dances are treated as clusters of solutions to the JSSP. These clusters of solutions are distributed as a Big Valley landscape structure. Via a dance accumulation strategy as well as an effective search in multiple clusters in the entire landscape, the proposed algorithm is able to generate relatively good solutions for the JSSP. Experimental results comparing our proposed algorithm with the shifting bottleneck heuristic (SBP), the tabu search algorithm (TS) and the parameter-free genetic algorithm (PfGA) on the Taillard JSSP benchmark show that it is comparable to these approaches.

Keywords: job shop scheduling; JSSP; bee colony optimisation; BCO; big valley landscape exploitation; combinatorial optimisation; bee foraging behaviour; bio-inspired computation; multiple clusters.

DOI: 10.1504/IJBIC.2010.032125

International Journal of Bio-Inspired Computation, 2010 Vol.2 No.2, pp.85 - 99

Published online: 10 Mar 2010 *

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