船舶分段涂装并行施工调度优化

刘 涛， 姚志荣

(上海江南长兴造船有限责任公司， 上海 201913)

0 引 言

随着国内外各大船厂对壳舾涂一体化造船模式的研究和应用，传统的整体造船法将生产作业物量遗留至船坞和码头阶段进行施工的方式，现已逐步被舾装前移、分段涂装、总组舾装和涂装完整性施工的分段式生产方式所替代，大幅降低船坞和码头的施工周期，提高对总组平台的利用率，提高船坞吊车吊装效率，从而提高造船企业整体的生产效率[1]。基于分段的船舶制造流程如图1所示。船舶分段涂装建造过程因自身存在不稳定因素，使在造船生产计划中分段涂装计划的编制和优化更加困难，因此需要对船舶分段涂装的业务流程和计划管理流程进行分析。本文以国内某造船厂为背景对船舶分段涂装业务流程和计划管理模式进行分析，对船舶分段涂装施工调度问题进行研究，为后续船舶分段涂装项目调度优化研究奠定基础。

图1 基于分段的船舶制造流程

1 船舶分段涂装施工业务流程

1.1 船舶分段涂装生产流程

船舶分段涂装在整个船舶制造过程中起着承上启下的作用，是拉动前道分段物量完成和保证后道搭载节点的关键，因此在整个船舶制造过程中，分段阶段需完成对主船体75%的涂装作业工作量[2]。船舶制造中的分段涂装生产流程如图2所示。

图2 船舶分段涂装生产流程

1.2 现代造船企业生产计划管理流程

现代造船企业的生产计划管理流程是自上而下分阶段逐步分解的过程，主要分为线表计划、大日程计划、中日程计划和小日程计划。

船舶分段涂装的生产计划管理是在船舶建造总进度计划指导下的小日程计划：根据前道部门双月滚动计划确定分段到达的开始作业时间；根据后道搭载部门的双月滚动总组搭载计划，确定分段配送的需求时间；涂装部门根据当前在制分段生产情况和跨间、劳动力等资源负荷情况，制定分段涂装部门的生产计划。由上至下分为5层，如图3所示。一级计划为公司双月滚动计划(分段涂装计划，见图4)，二级计划为部门月计划，三级计划为作业区双周滚动计划(见图5)，四级计划为单船周计划，五级计划为班组日计划。

作业区周计划为部门各施工作业区依据部门双月滚动计划，编制各生产作业区周度项目的开工和完工计划，主要用于对作业区承担各号船施工项目完成双周滚动计划所需资源和周期进行反馈调整，对生产进度和资源消耗进行控制协调。

图3 船舶制造业涂装生产计划管理流程图

2 船舶分段涂装项目网络计划

2.1 船舶分段涂装项目网络计划模型

对船舶分段涂装的分级网络计划制定分级网络计划模型，该模型采用自顶向下的方式将项目计划逐层细分，直至项目被完全分解为只包含任务不包含任何子网络计划的末级网络计划[3]，以上海某大型造船厂为背景，将项目计划共分为5层分级网络计划。

分级网络计划模型为

P={P11,…，P1i,…，P1n,A11,…，A1j,…，A1m,S1,E1|i=1,…,n1，j=1,…,m1}，其中每个P1i可进一步分解为由ni个网络计划P2ij与mi个任务T2ik及其之间的关系集A2i、开始节点S2i和结束节点E2i构成的二级网络计划，即

P1i={P2ij,…，P2ij,…，P2in,T2i1,…,T2ik,…,T2im,A2i,S2i,E2i|j=1,…,ni，k=1,…,mi},采用上述方式对项目计划逐层分解，直至达到5层分级网络计划。船舶分段涂装分级网络计划模型建立过程如图6所示。

图7展示了船舶分段涂装分级网络计划的建立流程。

2.2 船舶分段涂装分级网络计划模型优化

船舶制造企业中船舶分段涂装生产计划是按照线表计划逐级编制的，越往下分解包含的对象任务越少，对其进行优化效果不明显，因此需对底层网络计划进行合并。将作业过程中资源需求相似或作业工序相近的同级网络计划合并成虚拟父级计划并进行优化，再将虚拟父级计划还原至子网络计划中，保证原子网络计划任务对象的逻辑关系未改变，同时将具体任务对象的开始结束时间进行优化[4]，形成虚拟的分级网络计划模型，如图8所示。

3 基于遗传算法的船舶分段涂装并行施工周期优化

对分段涂装生产调度的业务流程分析后发现，在其调度过程中存在的主要问题是周期优化问题和资源均衡优化问题。船舶涂装分段制造过程通常是多船型分段并行生产作业，在作业过程中对冲砂跨间、油漆跨间、人力、分段堆场等资源的使用优先级是相同的，因此在船舶分段涂装生产过程中计划安排的合理性将直接影响每个分段施工过程对资源的使用，若发生某些意外事件(如跨间设备发生损坏、连续下雨、班组人员流失等)，还会导致项目整体周期的拖延，因此调度过程主要考虑2方面问题[5]：

(1) 在船舶分段涂装生产过程中，如何在紧前关系约束和资源约束的前提下使各分段总体施工周期达到最短，即资源-周期最短化调度优化问题。

(2) 对船舶分段涂装调度优化得到最优周期后，如何使各分段施工工序间对资源的利用率得到提升，对劳动力、跨间等资源利用均衡化，即周期-资源均衡调度优化问题。

虽然这2类调度优化问题在一般工程项目中有较多研究讨论，但针对船舶制造过程中涂装过程的调度优化研究较少,现对船舶分段涂装周期和资源均衡优化问题进行研究。

3.1 船舶分段涂装并行施工周期优化问题模型

船舶制造企业按照网络计划方式进行计划管理，通过在网络计划图底层网络对象任务中增加虚拟开始/结束作业的方式，将号船分段涂装施工对象的网络计划进行合并，形成带作业周期和资源需求量的虚拟网络计划图[6]，如图9所示。

图4 部门双月滚动计划流程图

图5 部门双周滚动计划流程图

图6 船舶分段涂装分级网络计划模型

图7 船舶分段涂装分级网络计划的建立流程

图8 优化后的船舶分段涂装生产分级网络计划模型

图9 虚拟网络计划图

图9中：ni为第i个作业的作业编号；r1i和r2i分别为第i个作业在单个工作日对R1、R2等2种资源的消耗量；di为第i个作业的周期；S、E分别为合成项目的虚拟开始和结束作业；s1、e1、s2、e2分别为项目1、2 的虚拟开始和结束作业；ds1、ds2、de1、de2分别为虚拟作业s1、e1、s2、e2对应的周期[7]。

船舶分段涂装项目工期优化问题包含m个并行项目，共享k种可更新资源(其中第k种资源的供给上限为Rk),第i个项目包含ni+2个作业(其中第0个和第ni+1个作业为项目i的虚拟开始和结束作业，具有一定的持续时间但不消耗任何资源)。第i个项目中的第j个作业记为Aij,其工期为dij，开始时间记为Sij,h为第i个作业的时间，对第k种资源的需求量为Rijk,用Pij表示作业Aij的紧前作业集合，It表示第t个工作日正在进行的所有作业集合，则问题的数学模型可以描述为

(1)

(2)

Sij≥Sih+dih,∀h∈Pij,∀i,j

(3)

(4)

rijk≥0

(5)

(6)

式(1)为目标函数，表示所有项目的最短加权总工期，i表示第i个项目的权重；式(2)指并行项目的权重系数之和必须为1；式(3)为项目作业的紧前关系约束，作业开始前必须保证其紧前作业集中的所有作业均已完工；式(4) 为资源约束，在单个工作日内所有作业对某一资源的需求量之和必须小于该资源的供给上限；式(5)指作业对任一资源的需求均不得为负；式(6) 为第t个工作日正在进行的所有作业集合。

对上述船舶分段涂装调度优化问题数学模型进行如下假设:

(1) 分段开始进跨冲砂作业直至油漆完工交验；

(2) 对于跨间设备、堆场场地等资源的使用，各施工班组共享；

(3) 在单位时间内各资源供给可满足生产需求；

(4) 各号船分段油漆施工工序相互独立；

(5) 不考虑天气、分段脱期供应等因素。

3.2 船舶分段涂装并行施工周期优化问题模型求解

3.2.1 船舶分段涂装并行施工周期优化问题算法的求解思路

在船舶分段涂装并行施工工期优化问题中作业对象较多，随着分段数目逐步增加，染色体的长度变大，使问题解的空间变大，造船种群的多样性变小(问题解空间变大，而种群规模却不变)，易使问题收敛至小范围内的局部最优解，找不到全局最优解，从而出现早熟问题[8]。在分层遗传算法的基础上融入模拟退火算法思想，构成模拟退火分层遗传算法。模拟退火算法能以一定概率接受劣解，具有很强的局部搜索能力，可以弥补遗传算法局部寻优能力弱的问题，帮助算法跳出局部最优解[9]，同时还可对遗传算法的交叉算子和变异算子进行模拟退火操作，达到与自适应遗传算法类似的目的，这样融合可有效地提高分层遗传算法的局部寻优能力和质量，形成船舶分段涂装并行施工调度问题模型算法的求解思路。模拟退火分层遗传算法的流程如图10所示。

3.2.2 基于遗传算法的模拟退火分层遗传算法设计

基于遗传算法的模拟退火分层遗传算法在低层和高层遗传算法进化过程中，不进行免疫操作，直接采用模拟退火处理后的交叉概率Pc和变异概率Pm,进行交叉和变异操作，避免算法早熟，及时将低层算法结果传输至高层遗传算法，确保每运行一代都进行终止判断，如果不满足终止条件，继续高层遗传算法，当进化5代后，返回低层遗传算法进行新一轮的寻优。

(1) 染色体编码

染色体编码方式采用任务列表的形式进行，其表达式为Vk=[r1,r2,…,ri,…,rmn] ，其中mn为总任务数，ri为第i个任务。

(2) 适应度函数

适应度函数为f(s)=1 /F(s) ，其中：F(s)为个体s的目标函数值。

(3) 初始化种群

一般遗传算法均采用随机方式生成初始种群，但对本文研究的问题采用常规随机化方式生成初始化种群不太合适，主要原因是无法满足作业紧前关系约束。如何进行初始化将直接影响初始种群的好坏，最终影响优化算法的整体计算效率和最优解质量[10]。

图10 模拟退火分层遗传算法流程图

(4) 解码操作

周期优化问题是利用每个作业的具体开始时间去求解对应的施工周期，对具体作业的周期进行优化，但在染色体中只包含作业本身固有的逻辑作业关系，并不包含作业本身具体的作业开始时间，因此染色体需要进行解码操作。

假设有m个作业工序，Ti表示作业i的周期，Sj表示作业j的开始时间，染色体Vk=[r1,r2,…,ri,…,rmn] 表示经过优化后的作业排序列表，则对该染色体的解码进行如下操作：

Step 1：令S1= 0,j= 1；

Step 2：当j≤mn时，j=j+ 1，转Step 3，否则转Step 6；

Step 3：Sj= max{Sk+dk}(k∈Pj) ，转Step 4；

Step 4：判断各资源在作业j的持续时间内是否存在冲突， 若存在则转 Step 5，否则转Step 2；

Step 5：Sj=Sj+ 1，转Step 4；

Step 6：返回所有作业的开始时间，结束。

求得各项目周期为

Ti=Si(n i+1)-Si1

(7)

加权后项目的总周期为

T=∑∂iTi

(8)

(5) 模拟退火操作

① 基于遗传算法的模拟退火操作，自适应的Pc、Pm函数实现其表达式为

(9)

(10)

式中：num为最大进化代数；T1为进化代数的倒数。在进化初期T1较高、Pc较大，有利于结合优良基因，交叉产生更多优秀个体，而Pm较小，因为进化初期变异操作不起主要作用；随着进化代数的增加，T1逐渐减小，Pc逐渐减小，避免过多的无用交叉，提高算法效率，而Pm则逐渐增大，有利于产生新个体，增加种群多样性，帮助种群跳出局部最优解。

② 交叉和变异后个体的模拟退火操作

在交叉和变异操作后个体Vi的邻域N内随机选取一个问题的一点Vi1(Vi1也是问题的一个可行解)，随机生成[0,1]之间的数q，判断Pt(T2) 是否大于q，若大于则用Vi1代替Vi，否则保留Vi[8]。

(11)

式中：f(Vi1)和f(Vi)为个体的适应度值；fmax为初始种群个体的最大适应度值；T2为进化代数；Pt(T2)随着进化代数的增加不断减小，使算法在进化前期接受恶解而在后期则只接受好解。

3.3 船舶分段涂装并行施工周期优化问题实例分析

以上海某大型造船厂分段涂装施工项目作为实例进行分析，以不同船舶间分段的2个相同部位的压载舱作为研究对象，项目1.1表示集装箱船分段A的压载舱区域涂装施工(使用中途油漆配套)，项目1.2表示散货船分段B的压载舱区域涂装施工(使用佐敦油漆配套)，对网络计划模型中作业关系相似、资源需求相近的底层网络计划作业工序进行合并，添加虚拟作业时间，确保各分段涂装施工工序的开始时间和作业逻辑关系保持不变，形成新的虚拟父级网络图。船舶分段涂装并行施工项目单代号网络计划如图11所示。

图11 船舶分段涂装并行施工项目单代号网络计划图

本例求解的是在资源约束下优化船舶分段涂装施工项目工期，其中分段A和分段B的权重系数分别为0.6和0.4，资源R1和资源R2的供给上限分别为40和33，算法参数设置为种群数量=90,子种群个数C=3，最大进化代数num=80,独立进化代数num=5,交叉变异概率Pc和Pm根据式(9)和式(10)动态改变。

由式(7)计算，项目1.1的分段A优化后的周期为T1=S30+S4=31，项目1.2的分段B 优化后的周期为T2=S31+S5=31 ，加权后的项目总周期为T1=∂iT1+∂2T2= 31,如表1所示。

表1 并行分段作业调度优化后的开始时间

通过对此问题模型分别采用标准遗传算法(GA)和 SAHGA 方法进行计算求解并对比结果，以证明本文提出的算法对问题的优化效果，各进行50 次迭代计算过程后，可知本文采用的SAHGA算法较一般遗传算法对问题最优解求解效率更高，并且具有更好的收敛性。调度优化后的计算结果对照如表1和表2所示。

从表 2 可知，利用SAHGA算法在求解船舶分段涂装周期调度算法在50次运算中，有46次找到最优解31.0，求解效率也更高(平均26次迭代计算)。

表2 GA和SAHGA方法优化结果比较

4 结 论

从宏观角度对整个船舶制造流程进行分析说明，对船舶分段涂装施工业务流程和涂装施工计划管理进行梳理分析，应用网络计划管理方法建立船舶分段涂装施工分级网络计划模型，并对分级网络计划模型的特点进行说明，通过船舶生产实际情况将底层网络计划进行优化处理，最后对船舶分段涂装并行施工调度所要解决的问题点进行梳理，明确船舶分段涂装并行施工项目调度优化的研究方向，即主要针对船舶分段涂装周期优化问题进行研究。通过对船舶分段涂装施工周期优化问题进行描述，建立周期优化问题的数学模型，应用求解算法对该问题进行求解分析，引用了基于遗传算法的SAHGA。该算法以船舶分段涂装施工项目总周期最小化为目标，在种群的初始化和解码过程中考虑作业紧前关系约束和资源约束，保证每种作业工序的排序都成为可行的调度方案，使研究问题得到简化；然后引用遗传算法分层思想，避免遗传算法中“早熟”现象发生；最后通过在算法中引入模拟退火的思路，改善算法对问题最优解的求解效率；最终通过船厂分段涂装生产实例验证表明本文提出的SAHGA对船舶分段涂装周期的调度优化相比遗传算法效果更明显，更易满足船舶分段涂装的生产周期需求。