A chaotic local search based bacterial foraging algorithm and its application to a permutation flow-shop scheduling problem

Abstract

The permutation flow-shop scheduling problem (PFSP) is a typical combinational and non-deterministic polynomial-hard problem, with discrete solution space. In this paper, a novel bacterial foraging optimisation algorithm (BFO) has been proposed to solve the PFSP. Difficulties such as slow convergent speeds and entrapment in the local optimum were incurred by the original BFO algorithm in solving a high-dimensional combinatorial optimisation problem. In order to deal with these difficulties, a differential evolution operator and a chaotic search operator were each introduced into the original BFO algorithm to enhance the activity levels of the individual bacterium and to extend the local searching space. Theoretical analysis showed that the improved algorithm obtained more motility in chemotaxis and could converge to the global optimum with a probability of 1. Simulation results and comparisons to both continuous and combinatorial benchmark problems were used to demonstrate the effectiveness of this novel optimisation algorithm.

Keywords:

• bacterial foraging
• chaotic sequence
• differential operator
• local search
• permutation flow-shop scheduling

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work was financially supported by the National Natural Science Foundation of China under [grant number 51365030]. It was also supported by scientific research funds from Gansu University, by both the General and the Special Programs of the Postdoctoral Science Foundation of China, and by the Science Foundation for Excellent Youth Scholars of Lanzhou University of Technology, under grant numbers 1114ZTC139, 2012M521802, 2013T60889 and 1014ZCX017, respectively.