制造业和服务业的调度问题必须很好地解决, 以确保高效生产率和资源利用率. 置换流水车间调度问题(Permutation Flow-shop Scheduling Problem, PFSP)就是其中之一, 而且已经被证明3台及以上机器的PFSP属于NP-hard问题. PFSP在化学、食品、制药和半导体制造等领域有着广泛的工业应用. 其研究背景和意义主要体现在以下几个方面：

提高生产效率: 在现代制造业中,生产效率是企业竞争力的重要体现之一. 通过对置换流水车间进行合理的调度安排,可以减少作业任务之间的等待时间, 最大限度地减少生产过程中的空闲时间,从而提高生产效率.

降低生产成本: 优化置换流水车间的调度方案可以有效降低生产成本.通过合理安排生产任务,可以减少设备闲置时间和人力资源的浪费,从而降低生产过程中的人力成本和设备能耗,提高资源利用效率.

推动制造业智能化发展:随着信息技术和人工智能的发展,智能制造已经成为制造业发展的重要趋势.研究置换流水车间调度问题可以促进制造业智能化发展,推动生产过程的自动化和智能化水平,提高生产系统的智能调度能力和自主决策能力.

综上所述,研究置换流水车间调度问题不仅具有重要的理论意义,而且对于提高生产效率、降低生产成本和推动制造业智能化发展都具有重要的实践意义.通过深入研究和解决这一问题,可以为制造业的发展和提升提供有力的支撑和保障.

二、主要内容

鉴于PFSP的工程价值和FOA的优越性, 提出一种LDFOA算法用于求解以最大完工时间为优化目标的PFSP. 

首先, 为提高种群的多样性,本文结合2种初始化策略: NEH和随机初始化原则用以初始化果蝇在解空间的位置.

其次, 在嗅觉阶段, 嗅觉搜索阶段为邻域搜索阶段, 所以邻域解的生成方式对算法的影响至关重要。根据已有文献表明, 目前还没有一种邻域结构, 适用于解决所有的问题, 所以我们提出了四种类型的邻域扰动算子分别为交换、双交换、绑定插入和插入-反向块插入, 以进一步扩大果蝇个体的搜索范围.

然后, 在视觉阶段, 所有的果蝇都将会飞向中心果蝇所处的位置, 种群中心是一个单个个体, 由于各自并不清楚自己的飞向位置是否为最优, 从而采用此方式很大概率导致算法性能欠佳. 因此, 将种群中心拓展为了部分精英个体, 通过收集精英果蝇的特征信息建立概率模型, 个体通过向概率模型的不断学习, 实现果蝇进化.

此外, 引入迭代贪婪算法对最优个体进行局部搜索, 从而使果蝇导向更有希望的区域. 

最后, 采用Rec和Taillard测试集对算法性能进行测试, 结果显示LDFOA算法具有更强的寻优能力.

三、主要结论及政策建议

本文提出一种学习驱动果蝇优化算法用于求解以最大完工时间为优化目标的PFSP. 首先, 为提高种群的多样性, 采用混合策略初始化果蝇在解空间中的位置; 其次, 在嗅觉阶段, 构造4种邻域扰动算子, 进一步扩大解的搜索范围; 在视觉阶段, 收集精英果蝇的特征信息建立概率模型, 个体通过向概率模型的不断学习, 实现果蝇的进化. 此外, 借鉴迭代贪婪算法的思想对最优个体进行局部搜索, 从而使果蝇导向更有希望的区域. 最后, 采用Rec和Taillard测试集测试算法性能, 结果显示LDFOA算法具有更强的寻优能力和更好的稳定性.

四、边际贡献与未来拓展

尽管通过大量的实验测试LDFOA算法的先进性, 但LDFOA算法在设计进化算子时是基于问题的性质设计的, 因此它具有一定的局限性, 但是设计算子的思想可以被借鉴，对于解决其他调度问题有一定的指导意义.

对于未来的工作, 我们可以以果蝇算法为基础结合问题性质开发出性能更高的算法解决其他复杂工程优化问题, 例如车辆调度, 物流调度, 分布式调度和柔性作业调度等, 这都是我们未来所努力的方向.

本文摘编自《系统工程理论与实践》2025年,第45卷,第8期论文《改进果蝇优化算法求解置换流水车间调度问题》（点击题目链接全文）；

作者：赵才¹，博士研究生, 研究方向: 车间调度； 吴亮红²(通信作者)，博士, 教授, 博士生导师, 研究方向: 智能优化与调度, 多目标优化

      1. 湖南科技大学 机电工程学院, 湘潭 411100

      2. 湖南科技大学 信息与电气工程学院, 湘潭 411100