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

摘要

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.