Abstract: An approach based on swarm intelligence is presented to solve the problem of scheduling tasks on flow-shop with batch processing machines. According to the characteristics of the problem under study, a method based on Palmer and Best Fit heuristic algorithm is developed to form batches. Moreover, an improved Particle Swarm Optimization（PSO） algorithm is presented to sequence the obtained batches. In PSO, the NEH heuristic is employed to improve the quality of the initial population. In order to enhance the search capabilities of the proposed algorithm, a variable neighborhood searching is performed for each iteration before the global best position is updated. The experimental results show that the proposed algorithm has a better effectiveness than the standard PSO algorithm and the NEH heuristic.

Key words: flow-shop, batch processing machines, Particle Swarm Optimization（PSO）, variable neighborhood search

摘要： 针对流水车间批调度问题，提出一种基于群智能算法的求解思路。结合问题具体特点，给出工件集合的分批策略，设计了将Palmer和Best Fit（BF）分批规则相结合的分批方法；在批排序阶段，提出了一种改进的微粒群算法；在粒子初始生成阶段，通过引入NEH启发式算法改进了粒子的初始化质量；在全局最佳位置更新前，通过变邻域搜索优化了算法的局部搜索能力，避免了算法陷入局部最优。仿真实验表明，改进后的算法优于传统的微粒群算法和NEH启发式算法。

关键词: 流水车间, 批处理机, 微粒群算法, 变邻域搜索