基于布谷鸟算法的压缩机装配调度项目优化方法

曹圣武，陈再良

(苏州大学 机电工程学院，江苏 苏州 215000)

0 引言

随着工业全球化的推行和日益加剧的市场竞争，多品种、小批量、定制化加工已经成为制造业发展的新趋势，订单式生产成为制造型企业的主要运作模式，订单式项目管理应运而生。

生产项目调度本质上属于资源受限项目调度问题(resource-constrained project scheduling problem，RCPSP)，即项目的各活动间需要满足两种约束关系，一是前后活动的逻辑约束，二是资源约束。RCPSP是近年来项目调度的热点问题，众多智能算法被引入到求解该问题中来，LI H等[1]改进了遗传算法并重新设计编码方案，提高了该算法求解RCPSP的性能； ZHENG X, WANG L[2]提出了一种MAOA智能算法，通过自主学习来强化搜索能力；DENG L等[3]引入混合蚁群算法，应用活动拆分来预测时间表，有效提高了调度质量；王凌和郑环宇[4]将教学算法用于多目标资源受限项目，仿真结果验证了算法的有效性。

1 问题描述

实际生产项目由n个活动构成V={1,…,n,n+1,n+2}，活动1和n+2是虚任务。项目各活动共用R种有限的可更新资源，并受到两类约束，一是紧前约束，即活动i∈V必须在其所有紧前活动全部完工之后才能开始；二是资源约束，即任意时刻活动对第k种资源的需求量不得超过其上限Rk。已知活动i的执行时间为di(i=1,2,…,n+2)，对第k种资源的需求为rik，在满足两类约束的前提下调度各活动的开始时间S={S1,S2,…,Sn+2}，目标函数是项目工期Sn+2最短。数学模型如下：

minSn+2

(1)

s.t.Sj+dj≤Si，j∈P(i)

(2)

(3)

Si≥0，i=1,2,…,n+2

(4)

其中：P(i)是活动i的所有紧前任务；At是t时刻正在进行的所有活动；rik是t时刻活动i所需资源k的数量。

2 算法描述

2.1 布谷鸟算法基本原理

布谷鸟通过寄生育雏的方式将自己的蛋偷偷下在其他鸟类的巢穴中，甚至可以模仿宿主的蛋而不被发现。剑桥大学的YANG X S和DEB S[5]从布谷鸟这种繁殖行为中得到启示，提出布谷鸟算法(cuckoo search，CS)。该算法具有涉及参数少、全局寻优能力强、随机搜索路径优等特点，首先设定如下3种理想状态：

1) 每只布谷鸟每次下1个蛋，并将其放入随机选择的巢中；

2) 具有优质蛋的最佳巢会被带到下一代；

3) 可用的寄主巢数量是固定的，且寄主以Pa∈(0,1)的概率发现布谷鸟放的蛋。

该算法还可以通过莱维飞行(Lévy flight)来增强全局搜索能力，搜索路径和更新位置公式如下：

(5)

(6)

(7)

2.2 算法改进

布谷鸟算法在运算后期会产生搜索性能下降、搜索速度变慢的现象[6]。因此针对算法重要影响参数——步长控制因子加入自适应策略，提出一种自适应的布谷鸟算法(ICS)。根据提出的自适应策略，在运算的前期，步长控制因子取较大值以增强莱维飞行的跳跃能力，提升全局搜索性能[7]；当种群的最佳个体靠近当代最优解时，自适应策略使控制因子取较小值以收缩步长变动幅度，使其能够更快收敛到全局最优解或次优解。自适应步长公式如下：

(8)

自适应的更新位置公式就变成：

(9)

3 自适应布谷鸟算法生产项目调度

3.1 编码方案

采用基于优先权的实数编码，生成串型调度方案。一条链代表生成的调度方案，基因为整数，如X=[0,1,2,…,n+1]，其中0和n+1是虚任务；另一条链代表任务的优先权，基因是随机分配的实数。表1为优先权分配示意图。

表1 随机优先权列表

3.2 调度流程

Step1：初始化参数，随机产生n个鸟巢；

Step2：计算初始种群适应度；

Step3：保留上代最优值，利用式(5)和式(6)更新出一组新解并计算适应度；

Step4：新解与上代解进行比较，用较优新解替换旧解；

Step5：利用式(7)丢弃部分解并产生新解；

Step6：部分较优解保留到下一代；

Step7：是否满足终止条件，若满足则停止迭代输出最优解，若不满足转Step3。

4 实验与分析

4.1 项目描述

S企业是一家专业从事中大型压缩机制造的跨国企业，以该企业一典型压缩机装配项目为例。该项目原计划工期160天，涉及项目工程师3人、采购工程师2人、机械工程师4人、装配工程师4人。简化的项目BOM和活动资源需求如表2，要求在满足活动约束和人员限制的情况下找到工期最短的调度方案。

表2 压缩机装配项目信息

续表2

4.2 调度方案

使用Matlab_R2018B版本编写算法程序，参考文献[8]的参数寻优方法，经多次运算的结果表明，自适应式步长影响因子上、下界取0.01和0.9时算法性能较好。初始种群数设定25，最大迭代数设定为50，发现概率设定为0.25。

该算法计算出的最短工期为141天，比原计划的完工时间提前了19天，工期缩短率为11.87%，验证了算法在处理生产项目调度问题的有效性。图1为运算过程中最短工期与平均工期收敛图，可以看到工期随迭代数稳步降低，在第16代时收敛到最优值；图2为最短工期与平均工期偏差，在第4代到37代间种群较为活跃，38代后趋于稳定；图3为人力资源利用率图，以资源利用率超过80%为风险点，该调度方案下资源利用率平衡且未超风险点；图4是人员配置甘特图，直观、清晰地呈现了各工程师在项目全期的工作安排；表3给出了具体的项目调度顺序和各活动的开始-完成时间；表4将自适应布谷鸟算法与布谷鸟算法相比较，结果验证了自适应布谷鸟算法具有更高的运算精度和收敛速度。

图1 最短工期与平均工期收敛图

图2 最短工期与平均工期偏差

图3 人力资源利用率

表3 优化调度方案

图4 人员配置甘特图

表4 布谷鸟算法与自适应布谷鸟算法比较

可以看到在当前的人力配置下，该方案已经达到了最优化，但是在项目的某些时段还存在着大量的人力浪费。项目经理可以通过观察人员配置甘特图来提前对具体的工程师做资源补偿安排，比如在项目第72天～129天的这个时间段把采购工程师调配到其他项目中；在项目前20天和第38～89天这两个时间段也可把装配工程师调到其他项目中。

5 结语

本文提出了一种新的基于自适应步长因子的布谷鸟算法(ICS)。以S公司生产调度项目实例为基础，验证了该算法在处理此类问题的有效性。还将改进算法与原算法对比，验证了改进算法拥有更好的精度和收敛速度。此外，通过观测软件自动生成的资源利用率图和资源配置甘特图，项目经理能够准确地监控资源配置情况，动态调整人员安排。ICS算法需求参数少，适用性强，经过简单的参数调整，就可以运用到其他制造型企业的实际生产调度中，为项目经理制订项目计划提供参考。