Abstract: The flexible job-shop scheduling problem is one of important constrained optimization issues in production?scheduling field. In this paper, a flexible job-shop scheduling method based on improved bird swarm algorithm with objective of minimum completion time is proposed according to its solution characteristics. To improve the population diversity and accelerate the convergence rate of algorithm, a random black-hole strategy is adopted to the foraging method of the bird flock, and the migration step length of the bird flock is used by self-adapting dynamic adjusting strategy. The domain search of the working procedures on critical path is used to enhance the local search ability of the proposed algorithm. In additional, production and processing data of actual manufacturing enterprises and some benchmark test cases are utilized for simulation experiments. It is shown that the proposed algorithm has advantages in solving accuracy and convergence rate, which is proved to be an effective new approach to solve flexible job-shop scheduling problem.

Key words: flexible job-shop scheduling problem, bird swarm algorithm, random black-hole strategy, critical path

摘要： 柔性作业车间调度问题是生产调度领域中非常重要的一类带约束优化问题。根据其求解特性，提出一种基于改进的鸟群算法求解以最小化最大完工时间为目标的柔性作业车间调度问题的方法。该方法采用随机黑洞策略改进鸟群的觅食方式，自适应的动态调整策略改善鸟群的迁移步长，从而提高种群的多样性并加速算法的收敛速度；通过对关键路径上工序的领域搜索加强算法的局部搜索能力。最后利用实际制造企业的生产加工数据以及标准测试实例进行仿真实验，实验结果表明，该算法在问题的求解精度和收敛速度上具有一定的优势，是一种有效的求解柔性作业车间调度问题的新方法。

关键词: 柔性作业车间调度问题, 鸟群算法, 随机黑洞策略, 关键路径