求解零等待流水线调度问题的离散磷虾群算法

针对最小化最大完工时间零等待流水车间调度问题,设计了一种离散磷虾群优化算法进行求解。根据优化问题特性,定义了算法中虚拟食物的计算方法,规定了虚拟食物影响下磷虾个体之间的交叉规则;提出了个体间的距离计算方式,从而可以界定邻域范围实现个体信息交流;进一步采用交换、逆序、插入等策略来提高算法的局部搜索能力,同时借助多种初始化策略来提高初始种群的质量和多样性。通过典型算例的仿真测试和对比,验证了所设计算法的有效性和鲁棒性。

A Discrete Krill Herd Algorithm for the No-wait Flow Shop Scheduling Problem

A discrete krill herd algorithm (DKH) is proposed to solve the no-wait flow shop scheduling problem (NWFSP) with the makespan criterion. Based on the characteristics of the optimization mechanism, the notion of “virtual food” in krill herd algorithm and the influenced crossover rules between krill individuals are defined. The concept and calculation method of the individual distance are redefined to measure the neighborhood range to realize the information exchange. The local search strategies of random swap, inverse and insert operator are employed to enhance the local search ability of DKH, and the multiple initialization strategies are redesigned to promote the qualities and diversities of the initial populations. Simulation results on the benchmark instances shows the effectiveness and robustness of the DKH.