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

2020-08-13曹圣武陈再良

机械制造与自动化 2020年4期

曹圣武，陈再良

(苏州大学机电工程学院，江苏苏州 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的数量。