求解作业车间调度的变邻域细菌觅食优化算法

针对最小化最大完工时间的作业车间调度问题,提出一种基于变邻域趋化操作的细菌觅食优化算法。邻域搜索是一类改进型局部搜索算法,在每一步迭代过程中通过搜索当前解的邻域得到一个改进的解,利用邻域搜索可大大提高局部最优解的精确度。本算法采用基于操作的编码,使得细菌觅食优化算法适用于作业车间调度求解;将3种不同的邻域结构引入趋化操作中,以便扩大可行解的搜索空间,细菌个体按照自适应学习策略根据邻域的各自贡献率选择搜索方式,减少陷入局部极小的机会;同时使用自适应步长更新各邻域内趋化操作的位置,根据适应度值动态调整搜索精度,避免早熟收敛。典型算例试验表明,该算法具有一定的鲁棒性,并有效地提高了搜索精度和收敛性。

Bacterial Foraging Optimization Algorithm Based on Variable Neighborhood for Job-shop Scheduling Problem

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.