Bee colony optimisation algorithm with big valley landscape exploitation for job shop scheduling problems. (11th March 2010)

• Record Type: Journal Article
• Authors: Wong, Li-Pei; Puan, Chi Yung; Low, Malcolm Yoke Hean; Wong, Yi Wen; , Chin Soon Chong
• Is Part Of: International journal of bio-inspired computation. Volume 2:Number 2(2010)
• Page Start: 85
• Page End: 99
• Publication Date: 2010-03-11
• Subjects: job shop scheduling -- JSSP -- bee colony optimisation -- BCO -- big valley landscape exploitation -- combinatorial optimisation -- bee foraging behaviour -- bio-inspired computation -- multiple clusters; Biologically-inspired computing -- Periodicals; Computational biology -- Periodicals; 572.0285
• Languages: English
• ISSNs: 1758-0366

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.