基于调度优先规则的海工项目并行进度计划编制

韩端锋，王学营，李敬花

（哈尔滨工程大学 船舶工程学院，哈尔滨 150001）

0 引言

目前，船舶及海工装备制造业在项目的进度计划管理中，基本都是由专门的项目计划人员来进行进度计划的编制和控制。随着造船技术的不断发展，模块化造船、壳舾涂一体化的应用越来越普遍，造船效率也有了稳步的提升[1]。项目进度管理是造船过程中不可或缺的一部分，是提高造船效率的关键环节，势必进一步发展才能适应现代的造船流程，为缩短船舶和海工装备制造周期更好的服务。海洋工程是复杂的多元化工程，其建造环节繁复，投资巨大，有效的进度计划不仅可以提高项目建造进程，而且在很大程度上还可降低由于准备不充分而产生错误的概率。事实证明，人工的计划编制不仅费时费力，在庞大的船舶计划系统下，人工编制计划还会有更大的机率出现失误，传统的进度计划编制机制在一定程度上已经表现出不适应性。因此，对海工项目进度计划编制问题的探讨有着一定的理论意义和现实意义。

1 海工项目进度四级计划编制

就海工企业目前的项目管理水平，一般将项目计划划分为三级，并由项目计划人员专门制定[2]。文章中的项目进度计划划分以企业的实际生产进程为依据，将海工项目的进度计划由上到下划分为四层，简称“四级进度计划”。

1）一级进度计划。即里程碑计划（图1），一般由船东提出重要事件节点，并以此为付款依据，而海工企业则据此来具体安排施工。里程碑计划一般包括项目开工、设计、采办、建造、海上安装调试、项目交付，采办中还包括关键设备到货日期、长线设备到货日期。里程碑计划是所有进度计划的指导及约束，必须严格按照里程碑计划完成预定工作。

2）二级进度计划（图2）。在里程碑计划的基础上，对里程碑计划的细化，划分依据以海工建造的不同阶段为依据。比如设计可划分为初步设计、详细设计、生产设计等，采办根据不同材料属性不同可分为钢材、油漆、机械设备、电气设备等，生产则依据海洋平台的模块划分为上层建筑、立柱、浮体结构、撑管、钻台等部分。

图1 一级进度计划

图2 二级进度计划

图3 三级进度计划

图4 三级进度计划

3）三级进度计划（图3）。在二级计划的基础上进一步细化，设计计划中把各分设计计划按照平台划分为比如上层建筑的初步设计、立柱的初步设计、浮体结构的初步设计等；上层建筑的详细设计、立柱的详细设计、浮体结构的详细设计等；上层建筑的生产设计、立柱的生产设计、浮体结构的生产设计等。采办在材料为依据的划分基础上，制定了不同材料的不同批次到货节点。生产则进一步将不同的模块划分成各个分段的项目进度计划，比如上层建筑分段一、上层建筑分段二等，立柱分段一、立柱分段二等，浮体结构分段一、浮体结构分段二。

4）四级进度计划（图4）。明确并详细划分三级进度计划下的各个子计划。设计将各分段的不同设计进行详细的划分，比如不同图纸的提交节点。四级生产计划把海洋平台不同模块的各分段划分到组立层次。

2 活动调度优先规则及并行进度方案

2.1 活动调度优先规则

多年来，研究者在工程实践和理论研究中，总结并积累了多种多样的优先规则，应用不同的调度优先规则所得的调度顺序也并不尽相同。调度的优先规则大致可分为以下几种类型：

1）基于关键路径

基于关键路径的调度规则是以关键路径为依据来进行活动的调度，最常用的调度方法是以项目活动的总浮动时间节点来进行优先活动的选择。典型的基于关键路径的调度优先规则有：最早开始时间优先、最晚开始时间优先、最早结束时间优先、最晚结束时间优先等。

2）基于网络图

基于网络图的调度规则考虑的是目标项目在网络图中所呈现的内容，比如：项目各活动间的紧前约束关系、紧后约束关系及活动后续任务的数目。典型的基于网络图的调度优先规则有：最小工时优先、最多紧前活动优先、最多紧后活动优先等。

3）基于资源优先

基于资源优先的项目调度规则主要是依据不同的项目活动对资源需求量的不同来进行活动安排。典型的基于资源的项目调度规则有：资源最大需求总量优先、最大资源利用率优先。

调度优先规则的选择对项目的活动安排会起到关键作用，所以要选择适当的优先规则，表1对一些规则进行了列举[4]。

在海工项目进度管理中，首要考虑的是时间问题，如何使项目在最短的时间内完成是问题的关键，所以文章选择以最大最早完成时间为首要规则，即对具有最大最早完成时间的活动优先调度。其次，资源需求量作为项目调度的约束条件，理应考虑在内，故选择资源需求总量作为优先调度规则。最后，海工项目的活动调度，并不能盲目的寻求最短工期，还要考虑到海工企业总体效益。因此，活动资源成本也作为优先调度规则。

表1 调度优先规则

2.2 并行进度方案

当前应用较广泛的进度生成方案主要有串行进度方案（Serial Scheduling Generation Scheme，SSGS）和并行进度方案（Parallel Scheduling Generation Scheme，PSGS）[5]。串行进度方案在每一个阶段只为项目进度安排一项活动，而并行进度方案不同于串行进度方案的地方在于其每一个阶段针对可行活动集En中的所有活动进行安排，每一阶段只受项目资源约束。

文章采用并行进度方案。设阶段m的完成时刻Fm，已完成的活动集合为Cm，在Fm时刻正在进行的活动集合为Am，此时可行工序集合为：

其中Pi为工序i的紧前工序集合，rikρ为活动i每天对资源k的资源需求量，Rikρ为资源k的每日可用量。并行方案与串行方案之间很大的区别在于串行方案未考虑资源的约束。应用并行进度方案步骤如下：

1）由阶段m的数据计算Fm+1，Cm+1和Am+1；

2）更新各种资源的剩余量Rk和Em+1；

3）按优先权从高到低顺序从Em中选择活动i，若当前资源剩余量大于活动i的需求量，则安排活动i；

4）更新各种资源剩余量和Em；

5）重复以上步骤可知Em为空。

具体过程可用图5进行描述[6]。

3 数学模型及算法设计

3.1 数学模型

为满足对初始进度计划的数学描述，定义初始进度计划满意率&，定义，Fn为项目最后一项活动的完成时间。项目最后一项活动的完成时间代表项目的工期，工期越短，对项目进度计划的满意度越高，对满意率的求解转化为最后一项活动的完成时间最早。

进行项目进度计划的编制，建立如下数学模型：

其中：式(2)为目标函数，表示项目工期最短；式(3)保证开始阶段的活动安排数为0；式(4)约束每项活动的资源使用量不多于资源总量；式(5)代表紧前约束关系；式(6)确保每项活动的安排不为空；式(7)保证资源的剩余量为有效；式(8)表示最后一项活动的完成时间满足最长工期要求。

对数学模型的求解应用并行调度方案，Em为空则完成一个循环，进入下一个循环。如果在并行调度的执行过程中存在某个被调度活动的开始时间小于0，则说明并行调度方案不能得到问题的解，此时停止并行调度操作。

表5 并行进度方案图例

3.2 编码机制

假设有n个项目活动，对其按持续时间长短顺序排列后各活动有整数编号i，Hn=[i1,i2,…,in]是这n的待安排活动的一个排列，在排列Hn中为每个活动定义属性活动时间ti，资源约束ri和紧前约束xi，则Z=[(i1,t1,r2,x3),(i2,t2,r2,x2),…,(in,tn,rn,xn)]就是遗传个体的染色体编码。其中：ij是排列中第j个活动的编号，tj是第j个活动的持续时间，rj是第j个活动的资源需求，xj是第j个活动的紧前约束关系。

假设进行活动安排时，各项目活动的时间固定，资源需求固定，对项目活动的安排仅限对活动顺序的调度。根据活动调度优先规则的定义，约束条件相似的活动间，具有更早LST的项目活动有较高的调度优先级，其次为活动的资源需求GRD。因此定义：

其中，令α+β=0，α＞β＞0，即认为优先考虑项目活动的最早完成时间。

由此定义个体适应度评价函数：

如果F(xi)＞F(xj)，则说明活动个体xi优先进行安排将获得更优的结果。

3.3 选择运算

为了将种群中的最优化个体保留在群体中，设定适应度值越高的个体被遗传到下一代的概率越大，定义个体Xi被选择的概率为，选择运算过程中，随机生成一个[0,1]的数G，如果有，则个体Xi被选择遗传到下一代。

3.4 变异运算

考虑到资源的平衡问题，文章算法只进行变异操作而不进行交叉。根据不同属性的类型不同，运算过程中会产生基因变异，由于各染色体的属性固定不变，因此仅考虑基因的排序变异。排序变异即染色体编码位置的变换，随机挑选两个位置不同的基因，并交换对应位置的基因编码[8]。变异实例如表2所示。

表2 排序变异实例

3.5 退火操作

由种群两个父代个体p1和p2经过变异运算后，生成两个子代c1和c2，父代个体和子代个体分别组成两个组p1，c1和p2，c2，进化过程中以一定概率P接受父代个体为下一代种群中的个体，以概率1-p接受子代个体为新种群个体。其中：

式中： Fp和Fc分别为父代和子代个体对应的个体适应度；T为温度参数，其大小根据问题规模选取。

3.6 终止条件

结合算法融合的特点给出以下三种终止准则：

1）迭代计算达到一定程度之后，适应度函数值在连续多次迭代中，无明显变化，终止计算。

2）最大迭代次数达到用户设定的要求时，停止计算。

3）按平均适应度终止原则。如果多次迭代后，群体之间的平均适应度差值小于用户设定的平均适应度差值常数，则认为算法已收敛，终止进化[9]。

3.7 求解步骤

初始种群的规模对算法的执行效率有一定的影响，过高的种群规模会较大的提高计算的复杂度，文章算法取N=30。变异概率的设置可以较好的控制优秀基因的流失，避免较优解在搜索过程中因变异而改变，取变异概率Pm=0.001。其他基本参数设置：Metropolis链长度为9000，初温2000，温度衰减参数取200，平均适应度差值常数为0.0001，最大迭代数为200。基本遗传算法步骤如下[10]：

表6 算法流程

1）设置编码长度、种群规模、Metropolis链长、初温、冷却参数、进化代数、平均适应差值常数等。

2）进行迭代计数器初始化操作，设置t=0。

3）随机产生初始种群p0(t)。

4）个体评价，即计算种群中每个个体的适应度，并保存种群当前最优个体。

5）按选择概率Ps，执行选择算子，从当前种群中选择部分个体进入下一代种群。

6）按变异概率Pm，对种群进行变异操作，得到新的种群p1(t)。

7）基于模拟退火的Metropolis准则，对种群个体操作产生新种群p2(t)。

8）进行种群个体选择与复制操作，得到种群p3(t)=Re-Produce[p(t),p2(t)]。

9）计算种群p3(t)的适应度，采用退火操作产生新的种群p(t+1)。

10）终止条件判断，若不满足终止条件，则t=t+1，转步骤4；若满足条件，则执行步骤11。

11）输出满足条件的解。

算法流程如图6所示。

4 实例验证及结论

为了验证调度原则和算法的有效性，文章以某自升式海洋平台为例，进行初始进度计划的生成。表3中给出了平台四级计划层中某一部分的活动及数据。应用遗传模拟退火算法进行计算后生产如图7所示的初始进度计划。

文章针对海工项目的进度计划编制问题，根据海工企业的实际项目生产进程提出了基于平台结构的四级进度计划，明确具体划分细节，引入项目活动的调度优先规则和并行调度规则，采用遗传模拟退火融合算法对进度计划编制问题进行求解。融合后的算法克服了各自算法局部搜索能力和全局搜索能力的缺点，实现了优势互补，并成功应用到了海工项目实例中。

表3 某自升式海洋平台参数

表7 初始方案节点图

[1]贾恒涛.船舶压载舱壳舾涂一体化技术要求研究[J].造船技术, 2010, 4: 40-42.

[2]李筱磊.CCPM在造船项目计划管理中的应用研究[D].大连:大连理工大学.2010.

[3]Wysocki.R.K., McGary.R.Effective Project Management[M].Indiana: Wiley Publishing.2010.

[4]朱晓璐.基于灰色斜率分析的资源受限项目调度问题研究与应用[D].重庆:重庆大学.2011.

[5]Peter Brucker, Andreas Drexl.Resource-constrained project scheduling:Notation, classification, models, and methods[J].European Journal of Operational Research,1999, 3(41):4-41.

[6]李倩, 刘霁.基于蚁群算法的工程项目资源受限施工进度优化[J].中南林业科技大学学报, 2011, 31(8):147-151.

[7]James M.Erickson, C.Ranganathan.Project Management Capabilities: Key to Application Development Offshore Outsourcing[C].2006 IEEE Proceedings of the 39th Hawaii International Conference on System Sciences, 2006:1-10.

[8]Fayez F, Boctor.A new and efficient heuristic for scheduling projects with resource restrictions and multiple execution modes[J].European Journal of Operational Research, 1996,90: 349-361.

[9]杨利宏, 杨东.基于遗传算法的资源约束型项目调度优化[J].管理科学, 2008, 21(4):60-68.

[10]李敬花, 樊付见, 王昊, 等.遗传模拟退火融合算法求解工程二维排样问题[J].计算机集成制造系统, 2011,17(9):1962-1967.