The Research On The Bacterial Foraging Optimization And Its Application In The Job Scheduling Problems

The shop scheduling problems is a series of complex NP-hard problems which can not be solved by traditional methods. To find novel and more optimal algorithms or methods is increasingly important. In this thesis, the researches mainly include the analysis of BFO and its application in scheduling problem. The biological and the mechanical basic of initial BFO have been described in detail. The fundamental and defect of chemotaxis in normal BFO has been thoroughly studied. A kind of improved BFO is proposed which introduces a differential evolution operator into the chemotactic operation to optimize the stationary bacterium in order to improve the effectiveness of chemotaxis. The evolution method and convergence of the algorithm have been proved theoretically.Typical example experiments show that the novel algorithm has great ability of avoiding the local optimum and performs a faster convergent speed and search accuracy in solving high dimensional problems. A series of Job Shop problems with the objective of minimizing the maximum processing time are used to test the performance of improved BFO in solving discrete problem. The continuous solution space is mapped into discrete jobs order through the rule of LOV. Then benchmark problems of job shop scheduling are used to test the AIBFO and the original BFO to show the outperformance of the novel algorithm. In order to enhance the local searching ability of novel BFO, a chaotic searching operator is introduced into the novel BFO. The SPV mechanism is used to change the variables in the continuous solution space to discrete variables. Typical instances are used to test the performance uf novel BFO with chaotic factor and compares with the solutions that obtained by others newly methods such as PSO, GA, DE, and NEH.