海工产品分段建造中日程计划优化

李敬花，陈俊宗，杨博歆

(哈尔滨工程大学船舶工程学院，黑龙江 哈尔滨 150001;)

0 引言

以“壳、舾、涂一体化”和“设计、生产、管理一体化”为主要特征的现代造船模式，决定了以分段制作为核心的中日程计划在海工产品建造中的重要地位。在海工产品建造过程中，其高度复杂性体现在任务数量多、建造周期长、不同分段间制作工艺的差异导致建造流程的不同等方面，而中日程计划是衔接船厂线表计划与车间生产计划的桥梁，是船厂计划执行与进度考核的重要依据。由于海工产品建造的特点，导致海工产品中日程计划明显区别于船舶中日程计划，常规项目的计划方式更加难以直接应用。因此，基于进度网络图(关键路径法、关键链法)、挣值技术(Earned Value Management，EVM)、横道图、趋势分析等的技术，虽然在理论上可以对海工产品计划进行编制和优化，但是大多脱离船厂实际，在长周期、海量建造任务的计划中优化的效果有限，且难以保证计划的可执行率。如文献[1]虽然对单代号网络图进行了改进，在进度网络中插入冗余的时间节点，解决了当工程项目任务不能按照预期方式完成时进度网络卡顿的问题，但其在构建进度网络的过程中作出了过多的假设，使该方法在海工产品建造项目具体实施上存在一定的局限。文献[2]运用改进的层次分析法，结合进度网络实现了施工计划的工期/成本/资源优化，但是其用于优化的进度网络规模过小，与实际海工产品建造项目存在较大差距，并且使用权值来综合各指标，使优化效果变差且可解释性不佳。另一方面，海工产品具有高定制性，针对不同平台作业地点有对应的设计，在长项目周期中使“边设计边建造”[3]成为常态，计划的鲁棒性要求极高，船舶先行中日程计划在计划模式、管理精度和管理柔性各方面都无法应用在海工产品建造中。文献[4]通过分析船舶分段建造流程与生产计划，构造了仿真系统的评价模型和优化目标，实现了船舶分段建造计划的仿真和优化，但是忽略了船舶建造生命周期中设计过程对建造计划的影响。

其中，设计过程对建造计划的影响可以归结为非线性建造的影响，先行中日程计划中每个作业任务可以看作一个大的工作包(Work Package，WP)，又可以向下划分为工作指令(Work Order，WO)和派工单(Work Job，WJ)[5]，不同作业任务间WO/WJ的联系形成分段的建造过程的非线性化。若将海工产品分段建造默认为随时间推进而线性增长的过程，则在船厂内部、外部庞杂的生产环境下，这种理想化的假设就不符合海工产品中日程计划优化的实际要求。如文献[6]提出工程资源熵作为资源均衡水平的新指标，结合关键路径完成工程项目资源—工期双目标的优化，但仅解决了在资源或工期一个指标固定的情况下去优化另一指标的问题。文献[7]通过赢得值预测技术，对海洋工程组块陆地建造项目的关键路径进行进度分析，完成了计划与费用的控制，虽然对赢得值法的不足进行了改进，但仍按照传统挣值管理中进度绩效指标(Schedule Performance Index，SPI)和成本绩效指标(Cost Performance Index，CPI)的单一指标来对进度进行管控，忽略了设计/生产内部环节中的非线性因素，若用该方法求解实际海工产品建造项目计划问题，得到的优化结果极可能造成项目活动之间的时间间隔过大或过小，也违背了海工产品建造项目精益制造的需求。文献[8]通过研究国际海洋工程施工承包(Engineering Procurement Construction Installation，EPCI)，总承包项目模式、分析项目范围，借助P6软件，在计划编制层面上完成了项目计划的分级与工作分解结构(Work Breakdown Structure，WBS)的制定，但该方法仅将项目周期中的工期作为重点考虑目标，疏于结合海工产品自身建造特点和设计—生产进度网络来对项目中工期/成本/资源内容进行深入探讨。

本文针对上述问题，结合海工产品生产的实际特点，对海工产品分段建造中日程计划优化进行研究，建立了海工产品分段建造中日程计划数学模型，并基于改进多目标非支配遗传算法设计了一种适用于非线性建造方式的优化方法:多目标非支配遗传模拟退火算法(Non-dominated Sorting Simulated Annealing Genetic Algorithm-Ⅱ，NSSAGA-Ⅱ)，以实现海工产品分段建造过程中的工期、成本和资源均衡的多目标优化，最后，将遗传模拟退火算法(Simulated Annealing Genelic Algorithm，SAGA)、带精英策略的快速非支配排序遗传算法(fast elitist Non-dominated Sorting Genetic Algorithm，NSGA-Ⅱ)与本文设计的方法进行对比分析，验证了NSSAGA-Ⅱ在解决海工产品分段建造中日程计划优化问题上的有效性和优越性。

1 问题描述与数学模型

1.1 问题模型

1.1.1 非线性建造活动的约束问题

传统海工产品分段建造中日程计划优化大多以“分段的建造过程线性化”为前提条件，工作量随时间推移严格按正比增加。但在实际项目建设中由于各种随机的环境扰动，活动流程的线性化几乎无法实现。例如，在一些分段的建造中，随着生产熟练度的上升，整体建造速度也逐渐提高，整体建造曲线斜率逐渐提升;在有的分段建造后期，由于工序复杂度的提升，使整体建造速度下降，整体曲线斜率也相应变小。

在非线性建造模式下，前导图中的端点约束，如开始—开始依赖关系(SS)，开始—结束依赖关系(SF)，结束—开始依赖关系(FS)，结束-结束依赖关系(FF)，就不再适用[9]。例如，船厂在订货时，根据生产计划的需要，材料运抵日期提前于材料需要日期的一段储备时间，称为采购纳期。纳期的存在使在同一海工产品建造项目内容上的设计活动与建造活动之间应留有一段过渡时间，从而保证生产材料在投入使用前供应商能够及时交货。如图1所示，该段过渡时间就很可能因为设计活动内容与生产活动内容的非线性进行而发生变化。这种情况下，为保证项目仍能按计划顺利进行，需要对该非线性工期/工作量约束进行转换。

如图2所示，虽然活动j的开始时间与结束时间都严格遵守SS约束和FF约束，但由于活动i的生产方式并不符合线性条件，活动i与活动j不能时刻保持“两活动间隔不小于2天”的约束，甚至出现了交叉[10]。

(1)非线性工期约束转换

非线性工期约束的转换方式如图3所示，约束表述为活动j与活动i的工期间隔不小于tij天，则在工作量/工期坐标系中，在函数定义范围内的任一纵坐标，活动j与活动i对应的横坐标差值大于等于tij:

在函数斜率相等处，两活动的横坐标差值最小。如式(2):

若无式(2)情况，式中w1在活动函数端点处选取。此时，活动i和活动j的非线性工期约束tij转化为SS依赖关系，活动i与活动j的SS约束为Sj-Si天。

(2)非线性工作量约束转换

如图4所示，约束表述为活动j与活动i的工作量间隔不小于wij人·d，则在工作量/工期坐标系中，在函数定义范围内的任一横坐标，活动i与活动j对应的纵坐标差值大于等于wij:

在函数斜率相等处，两活动的纵坐标差值最小。如式(4):

若无式(4)情况，式中t1在活动函数端点处选取。

同样，活动i和活动j的非线性工作量约束wij转化为SS依赖关系，活动i与活动j的SS约束为Sj-Si天。

1.1.2 进度决策选择

本文的研究内容为海洋工程分段建造中日程计划中总工期、成本增额以及资源均衡的多目标优化问题。海工产品分段在建造过程中会出现很多在计划编制阶段并未预期到的问题，如更复杂的生产内容、更高的产品质量要求或者新技术的引进都会对计划的正常进行产生影响。此时，如果再继续保持原有建造速度，工期必然会产生延误，甚至带来更多不可知的风险。为了缩短工时，船厂可以通过增加资源的方式进行赶工，但同时也增加了成本[11]。因此本文的优化手段是对采用原建造速度的典型建造方式和采用赶工加班的非典型建造方式之间进行权衡，同时兼顾不同建造方式下的资源均衡，以找到工期最短、成本增额最小、资源平均日占用量最合理的计划决策。其中由于工时延误带来的间接成本增加也算在工时延误的损失中。

分段建造是海工产品建造的最主要最基本的环节。该环节主要包括分段钢材切割、小组立制作、平直/曲面前道、平直/曲面后道、胎位安装、分段舾装、分段涂装、分段合拢等内容。某单船分段建造的进度前导图如图5所示。其中:方框表示项目活动;带箭头的实线表示活动的建造先后关系。活动10A-11，10B-11间的虚线表示分段最终搭载先后顺序为10A→…→10B。

在计划执行过程中，会发生因需求变更而导致的建造作业内容增加，或因设备故障、天气等原因导致的项目进度拖期。为满足项目建造目标，可以通过优化资源配置完成计划的追赶，根据历史实绩数据为每个活动配置两种建造模式。如表1所示为某海工产品分段101的进度决策表。

表1 分段101进度决策表

1.2 数学模型

本文对海工产品分段建造中日程计划优化的参数设定如下:建造内容包含活动个数为n，第i个活动的开始时间为Si，结束时间为Fi。工程总开始时间为Sstrt。f(t)表示该活动工作量随时间的函数关系，f-1(w)表示该活动时间随工作量的函数关系。AK表示活动的普通前后约束。非线性活动间工期约束为AT，tij表示在任意时刻活动j与活动i的时间间隔应不小于tij天。非线性活动间工作量约束为AW，wij表示在任意时刻活动i已完成的工作量应始终超前于活动j至少wij人·d。每种活动的建造方式为Di，成本增额为RCi。项目建造期间每日的资源占用量为Rt。

在海工产品分段建造过程中，为对建造进度进行科学有效的管控，优化目标为项目工期、成本增额以及资源均衡程度。目标函数如式(5)所示，

式中:总工期RT等于项目最后一条活动的开始时间与持续时间之和;总成本增额RC等于各活动成本增额之和;资源均衡程度RM等于建造期间每天占用资源量的方差。

约束条件如下:

(1)每道活动的结束时间等于开始时间与持续时间之和。

(2)处于紧前紧后约束AP关系的活动，紧后活动的开始时间应不小于紧前活动的结束时间。

(3)处于约束AT下的活动，紧前紧后的活动应时刻满足最短时间间隔不小于约束tij。

(4)处于约束AW下的活动，紧前紧后的活动应时刻满足最小工作量差距不小于约束wij。

(5)每种活动只能选择典型建造方式和非典型建造方式中的一种。

(6)建造的总开始时间为0。

(7)每日资源占用量不超过每日资源占用上限。

输入条件为:在进度前导图中存在n个建造活动，且所有活动的基本属性信息和分段资源使用计划都已明确。

输出条件为:当所有活动的决策方式以及建造工期/工作量/资源限制全部满足约束条件，得到活动在进度网络图中的中日程计划安排方式。

2 海工产品分段建造中日程计划优化算法设计

2.1 算法策略

因为海工产品分段建造计划前导图中所涉及的内容与限制较多，在确定NSSAGA-Ⅱ初始参数后，需将所有活动的基本属性信息进行转化以完成后续的优化操作。首先，完成进度网络图中的路径构建。根据活动表单中的活动基本信息，结合每个活动的前道后道关系建立活动的建造路径，为每个活动添加相应的路径信息。当在某个活动处出现路径交叉时设置候选路径，保证进度网络图中从源点至汇点之间所有路径都能遍历到，而且也为以后计算实时关键路径作准备。

构建好活动建造路径后，还需将非线性工期/工作量约束进行处理，将其转化为与其限制等效的普通前导图约束关系。在本算法中，所有非线性约束关系都转化为SS关系。采用1.1.1节中的转化方法，通过约束中的滞后工期/工作量来计算两个连续活动的前者开始时间和后者最早开始时间之差，从而找到两连续活动的SS约束关系。

应用NSSAGA-Ⅱ对海工产品分段建造中日程计划进行优化，其过程为:通过启发式算法生成初始种群。设置最大进化代数，当进化代数达到上限时，算法结束。在每一代进化过程中分为两个阶段:第一阶段首先进行染色体的遗传进化(交叉和变异)，得到进化后的染色体并将两者进行合并。获得种群数量为初始数量两倍的新种群后，对新种群中所有个体计算多目标值(总工期、成本增额、资源均衡方差)，然后根据多目标值进行Pareto排序，再对处于同一非支配排序序列中个体进行个体拥挤距离计算，淘汰非支配排序靠后的个体和拥挤距离小的个体，将种群规模调整到原种群大小。第二阶段为模拟退火阶段，设置退火的初始温度，每一轮退火后按照降温规则降低当前温度，当温度冷却到设定的结束温度时，退火结束。每一轮退火中通过种群交叉产生新解并通过Metropolis准则判断是否采纳交叉产生的新个体。

求解海工产品分段建造中日程计划优化问题步骤如图6所示。

2.2 编码生成

为解决2.1节中描述的海工产品分段建造中日程计划优化问题，对每个染色体采用双排编码的方式。每个染色体个体表示待优化问题的一个可行解。将n个活动的进度决策用一条长度为2n的染色体表示。其中:前n位表示为每个建造活动前置的缓冲时间，采用整数编码，取值为算法设定范围内的自然数;后n位表示每个建造活动的建造方式，采用二进制编码，0代表典型建造方式，1代表非典型建造方式。按照约束条件(5)，每个活动只能选取一种建造方式。在中日程计划优化问题中，如{22，21，12，23，14，15，3，35，24，16，7，13，0，0，0，0，0，0，0，0，0，0，0，0}就为一条合法染色体(真实长度由活动数量决定)。染色体编码方式如图7所示。

在计划优化过程中，由于建造进程的非线性，经活动间隔最小化计算处理后，某两个活动的非线性工期/工作量约束会根据当前染色体中这两个活动对应基因的不同组合而转化为不同的结果。如前导图中标识的活动101-5与活动101-6的非线性工作量约束w101-5，101-6为82人·d，经转化后的标准约束如表2所示。

表2 活动101-5,101-6的特殊约束转化

2.3 求解过程

2.3.1 初始种群

为保证足够的搜索空间与较高的运行效率，算法经运算实验，将种群数量定为200较为合适。按照进度网络和约束条件排列好活动顺序后，使用削峰填谷的启发式算法对资源进行均衡，并将均衡结果作为初始种群。采用削峰填谷算法进行资源均衡的步骤如图8所示。

2.3.2 交叉操作

算法的交叉操作选择两点交叉的方式，分别在父代染色体中的两段上，每段随机生成两个交叉点，将交叉点中间的部分互相交换，从而产生两个子代。如图9所示为交叉操作。

因海工产品分段建造计划网络复杂程度很高，算法容易陷入两种极端:“早熟”并快速收敛于局部最优以及收敛时间过长。为改善算法性能，使用自适应的交叉概率使种群的进化过程更加合理。自适应交叉概率如式(14)所示。

式中:fmax为种群最大适应度值;favg为种群的平均适应度值;f'为要交叉的两个染色体中较大的适应度值[12]。对于海工产品分段建造中日程计划优化而言，染色体的输出为多目标值，为保证工期目标/成本目标/资源目标三者的重要程度相同且尽量降低适应度值fi因某一目标值过大/过小产生的影响，fi的取值如式(15)所示。

式中v1，i、v2，i和v3，i分别为染色体i的3 个目标值。

2.3.3 变异操作

算法的变异采用双点交换变异，在父代染色体中的两段中，每段随机生成两点，将两点处的基因互换位置，生成一条新的染色体作为子代。如图10为变异操作。

自适应变异概率如式(16)所示。

式中f为变异染色体的适应度值。

2.3.4 非支配排序

海工产品分段建造中日程计划优化目标分别是最小化总工期、最小化成本增额以及最小化资源均方差，算法求解的关键在于获取Pareto最优解集。当两个体在非支配比较时，若某个体的所有目标性状都优于另一个个体，就认为前者支配后者，否则两者互为非支配关系。非支配排序是依据个体的非支配水平来对种群进行分层，种群中性状最好的非支配层称为Pareto前沿。算法终止后，末代种群的Pareto前沿作为算法的输出。非支配排序是一个循环的目标值分级过程，寻找种群中性状最好的一组，将其放入非支配0层并从原种群中除去。然后，继续寻找剩余种群的一组最优个体，将其放入非支配1层。以此类推，直至整个种群中所有个体都被分层。如图11为非支配层级的划分示例。

进行非支配排序时，先按照种群中个体的第一目标值(工期)将种群升序排列，遍历比较时仅比较个体的第二目标值(成本增额)和第三目标值(资源)，从而进一步提升算法的运算效率。非支配排序过程的伪代码如下:

输入种群中所有个体的多目标值;

输出种群中所有个体的非支配层。

2.3.5 计算拥挤距离

计算拥挤距离的目的是对处于同一非支配层的个体再次进行选择性排序。个体的拥挤距离表示该个体在该非支配层内与其周围一定范围内其他个体(通常取左右两个个体)之间的间隔距离，是评价该个体在空间分布上均匀程度的指标[13]。若某个体的拥挤距离越大，则其在该非支配层的空间分布越均匀。传统拥挤距离的计算方式为:首先计算前后两个个体在某一目标值上的差值与该目标值上最大值和最小值的差值之比，然后将该个体在所有目标值上的拥挤距离相加，为该个体的拥挤距离。其中，同层端点处个体的拥挤距离设为大数，使其能够排在拥挤距离前列从而直接保留。如式(17)所示。

然而，多目标值拥挤距离的和并不能客观地反映个体的真实拥挤距离。在海工产品分段建造中日程计划优化问题中，当目标值的维数超过2时，通过式(17)得到的个体拥挤距离的可用性会逐步变差。在此基础上，建立以多目标值为轴的拥挤距离多维坐标系，将个体与相邻两个体间的欧式距离作为指标，通过动态参数的修正，计算得到该个体在非支配层上的拥挤距离。如式(18)所示。

2.3.6 精英策略选择算子

精英策略即保留父代中的优良个体直接进入子代，将Pareto解集中性状优秀的解保留下来。精英策略选择算子对两倍于初始种群个体数目的父代进行删减。首先淘汰父代中的不可行方案，其次按照非支配层从低到高排序，将非支配层数低的个体直接放入子代，直至放入某一层时个体超出种群规模限制，将该层中个体拥挤距离大的个体优先放入子代，直至种群数目与种群规模一致。如图12所示，为精英策略选择算子原理图。

2.3.7 Metropolis准则筛选

Metropolis准则是一个以概率接受新解的过程，概率随温度的变化而动态变化。Metropolis准则并不完全排斥劣化解，这使种群多样性能够始终得以保持。因为进度网络图线路复杂，关键路径也会随着优化进程而发生改变，优化结果很可能陷入弱极值而避开最优解集。迂回搜索的策略增大了算法容错率从而克服了迭代收敛过早或易陷入局部最优的缺点，使算法具备更高的容错率。

Metropolis准则规定，在新旧解选取中，根据比较解的目标性状，如果新解非劣于旧解，则选用新解。如果新解劣于旧解，则生成一个概率选取新解。概率与新旧解的目标性状和当前迭代温度有关。

为更大程度地增加种群多样性，本文对该概率进行一些平滑，使其有更大几率接受被支配解，也使运算过程更容易跳出局部最优。

3 实例验证与算法性能评估

实例验证选用某船厂海工产品分段建造的实际进度数据，通过分析建造活动约束，构建活动进度前导图并使用本文设计的NSSAGA-Ⅱ对中日程计划进行优化。

如表3～表9为该海工产品分段建造的信息表。通过对实际建造进度数据的回归分析，得到活动的进度函数。项目开始时间为第0天，每个活动可供选择的建造模式如下所示。

表3 101、102分段先行中日程计划决策信息表

表4 161、162、171分段先行中日程计划决策信息表

表5 10A总段先行中日程计划决策信息表

表6 711分段(总段)先行中日程计划决策信息表

续表6

表7 122、132、142分段先行中日程计划决策信息表

表8 10B总段先行中日程计划决策信息表

续表8

表9 项目活动非线性约束

通过NSSAGA-Ⅱ优化输出得到的pareto最优非支配解集如表10所示。在获得的158个方案中，工期范围为275 d～350 d，成本增额范围为0万元～5.4万元，资源均衡方差范围为0.195 52～0.667 15。在所有方案中，较短的工期会伴随着较高的成本增额或较高的资源方差，较长的工期则伴随较低的成本增额或较低的资源方差，均符合船厂实际情况。

表10 pareto最优非支配解集

续表10

续表10

与传统海工产品分段单目标/双目标的计划优化方法相比，将工期、成本增额与资源均衡程度同时作为优化目标可大大降低生产过程中因计划与实际不合从而出现的计划变更问题。与传统多目标值加权作为适应度值的优化算法相比，将多目标Pareto解集作为算法的输出解的好处在于解决了优化前期就使不成熟的权重参与到算法中的问题。在以上158个输出里，船企可根据各目标值的重要程度，通过再次决策选取一个最符合生产实际的解，作为用于未来建造的计划。如图13所示为解集中序号为40、79、119的解所对应的进度甘特图。

为验证本文设计的NSSAGA-Ⅱ在解决海工产品分段建造中日程计划优化问题上的有效性和优越性，将NSSAGA-Ⅱ与SAGA、NSGA-Ⅱ进行比较，计算结果如图14～图16所示。

对实例运算后的数据进行分析，SAGA因为采用工期、成本和资源方差加权求和的方式来确定目标值，权值的选取受主观因素的影响，算法结果的可解释性不好，并且在与其他算法运算结果对比后得知，该解集相较于其他算法解集的被支配程度非常高，说明该算法在实际海工产品复杂网络下优化目标数量增多时确实存在优化瓶颈。NSGA-Ⅱ得到的解集较为优秀，该算法运行20次的平均解个数为124.5。NSSAGA-Ⅱ的优化结果最好，NSSAGA-Ⅱ运行20次的平均解个数为156.6。将SAGA(30次运算)、NSGA-Ⅱ和NSSAGA-Ⅱ的运算结果进行非支配排序，发现在Pareto前沿中NSSAGA-Ⅱ的运算结果个数占63.9%，进而说明NSSAGA-Ⅱ在迭代过程中能够有效地从局部最优跳出，从而得到优化程度更高的Pareto解集。

如表11所示为SAGA 的30次运算结果。其中每种权重w运算5次。

表11 算法运算结果比较

4 结束语

针对海工产品分段建造中日程计划优化问题，本文在传统进度约束的基础上延伸出非线性建造方式下的工期/工作量约束和转化方法，构建进度前导网络图，建立以总工期、成本增额和资源均衡方差为优化目标的数学模型，提出了基于NSSAGA-Ⅱ的海工产品分段建造中日程计划优化方法。在得出优化结果的非支配Pareto解集后，对比分析SAGA和NSGA-Ⅱ在求解同一问题的优劣，验证了算法的有效性和优越性。在面对复杂进度网络和非线性化的活动建造模式时，基于NSSAGA-Ⅱ的海工产品分段建造中日程计划优化方法可以对船厂分段建造中的进度管控提供一定的辅助决策方案，对工期/成本/资源有显著的优化效果，具有一定的理论研究意义和工程实践意义。未来可基于机器学习完成工期/工作量的非线性转换和多建造模式匹配，进一步提升海工产品建造中日程计划编制的智能化程度。