应用改进混合进化算法求解零空闲置换流水车间调度问题

裴小兵，李依臻

（天津理工大学 管理学院，天津 300384）

0 引言

置换流水车间调度问题（Permutation Flowshop Scheduling Problem，PFSP）是典型的NP难问题，已经成为学术界研究的热点。在该问题的几个不同的评价指标中，最大完工时间最小化是文献中最常用的评价指标［1］，总拖期时间最小化也是常用指标，在现实生产中具有重要的意义。在约束条件方面，零空闲约束已经成为置换流水车间调度问题的重要约束条件，在实际生产过程中，对于节约成本、降低能耗具有重要的研究意义。基于此，本文以总拖期时间最小化为目标来研究零空闲约束条件下的置换流水车间调度问题。

零空闲置换流水车间调度问题（No-idle Permutation Flow-shop Scheduling Problem，NIPFSP）是经典置换流水车年调度问题的扩展。零空闲约束是指在实际生产过程中使用高耗能、贵重机器的情况下，空载运行通常会造成巨大的资源浪费。

目前，国内外对零空闲约束置换流水车间调度问题的研究相对较少。Tasgetiren M F等［2］以总流程时间最小为目标，提出了一种变量迭代贪婪算法求解零空闲置换流水车间调度问题，实例验证结果显示该算法具有较好的求解效果。武磊等［3］以总流经时间和最大完工时间为目标求解NIPFSP问题，提出了和声搜索调度算法，由于采用局部搜索算法，难以保证解的多样性。Shao W 等［4］运用混合节点和边缘直方图的随机样本交叉方式，提出了文化基因算法求解NIPFSP问题，该算法采用随机样本交叉操作，难以保证交叉结果的有效性。刘长平等［5］以完工时间最小化为目标求解零空闲置换流水车间调度问题，提出了离散萤火虫优化算法，并通过典型算例验证了算法的稳定性和高效性。……