Abstract: A bacterial foraging optimization algorithm based on variable neighborhood is proposed to solve job-shop scheduling problem (JSP) with objective function of minimize the maximum completion time. The neighborhood search is a kind of improved local search algorithm, and it can greatly improve accuracy of the local optimal solution. By searching neighborhood of the current solution, an improved solution can be obtained. The operation-based encoding is firstly used to allow bacteria foraging optimization algorithm for JSP solving. Three different neighborhood structures are used for chemotaxis operation to expand the feasible solution space. In the proposed algorithm, each bacterial can select different search method in accordance with contribution of the neighborhood to reduce the chance of local minimum. The location of bacterial can be also updated using adaptive step size of chemotaxis operation in different neighborhoods. Therefore, search accuracy can be adjusted according to the fitness value of each bacterial to avoid premature convergence. Typical example experiments show that the algorithm has certainly robustness and effectively improve search accuracy and convergence.

Key words: Adaptive step size, Bacterial foraging optimization algorithm, Chemotaxis operation, Job-shop scheduling problem, Variable neighborhood search