船体分段制造因流程多，周期长，控制难，是造船生产的关键环节，也是影响造船效率的重要因素。因此，如何优化分段制造流程，统筹分段制造资源，已成为业界和学者关注的焦点。

作为实现计划调整智能化和自动化的有效手段，智能算法和仿真分析在分段制造计划优化中得到广泛应用。Cho等^[1-2]基于实例推理对分段装配顺序进行了研究。Glen^[3]应用动态规划方法对分段制造过程中的劳动力和资源问题进行了优化。为提高分段装配和涂装过程中的场地利用率，Liu等^[4]运用启发式算法，对基于离散随机仿真的计划优化系统进行了求解。为实现计划期内生产任务数目最大和生产负荷最优的目标，Bao等^[5]，Kim等^[6]，Kajiwara等^[7]以及Pinha等^[8]基于设备、场地及人力资源等约束，将生产计划优化问题抽象为资源满足问题并建立了优化模型。为了提高钢板堆场和船坞周围设备的利用率，Joo等^[9]和Dohn等^[10-11]采用基于遗传优化的启发算法对这两个区域的吊车使用计划进行了优化分析。Yu等^[12] 以分段制造最短工期为目标，对分段装配流水线采用着色 Petri网进行了仿真和规划。Cha等^[13]运用基于离散时间/事件混合数值仿真对吊车使用计划进行了优化。Zhang等^[14]引入熵的概念对负荷的平衡问题进行了研究。为科学确定分段进出场地的顺序，刘建峰等^[15-16]运用排序函数对分段制造日程计划进行了模拟优化。针对船体曲面分段作业计划在执行过程中出现的异常，赵明华等^[17-18]提出了曲面分段作业计划自动调整算法，并构造了调整评估体系。

虽然国内外学者在分段计划优化问题上取得了一定的研究成果，然而由于分段制造属于典型的离散组合和非线性问题，难以采用常规的优化算法加以解决。本文基于生产连续、负荷均衡的分段制造目标，采用改进的粒子群算法，综合考虑船厂作业设备、作业场地、作业顺序等制约因素，对问题模型进行求解，最后通过算例分析说明优化方案的有效性。

1 高效分段制造作业模型的构建

假设：某造船生产计划包含m个分段生产任务(用D_i表示)，每个生产任务包括n_i个作业阶段，用W_ij(i=1,2,…,m; j=1,2,…,n_i)表示。

1)计划进度的确定。

主要考虑分段制造区域生产资源的局限性及作业阶段之间的逻辑关系。

$\quad\quad\left\{ \begin{array}{l}{F_{ij}} = \min \left( {{\rm{L}}{{\rm{B}}_{ij}},{\rm{L}}{{\rm{A}}_{ij}}} \right),\\{S_{ij}} = {F_{ij}} - {C_{ij}}{\text{。}}\end{array} \right.$

(1)

其中：S_ij和F_ij分别表示作业阶段W_ij的开始时间和结束时间；LA_ij表示由W_ij所需生产资源的可用时间所确定的最早完工时间；LB_ij表示由W_ij所有紧后作业阶段需求时间所确定的最早完工时间；C_ij表示W_ij的标准作业周期。

2) 生产负荷的确定。

在高效造船生产中，一般以物量或工时对各作业区域/阶段生产负荷进行衡量。则有：

$\quad\quad{M_p} = \mathop \sum \limits_{i = 1}^m \mathop \sum \limits_{j = 1}^{{n_i}} {\rm{W}}{{\rm{M}}_{ijp}},$

(2)

$\quad\quad{H_p} = \mathop \sum \limits_{i = 1}^m \mathop \sum \limits_{j = 1}^{{n_i}} {\rm{W}}{{\rm{H}}_{ijp}}{\text{。}}$

(3)

其中：M_P、H_P分别表示在工作日p内的物量负荷和工时负荷；WM_ijp、WH_ijp分别表示某一生产任务某一作业阶段在工作日p内的生产物量和工时需求，若工作日p不在某一生产任务作业时间段内，则WM_ijp和WH_ijp都为0。

3) 分段制造计划优化模型。

为实现高效分段制造目标，每个作业阶段j(j=1,2,…,n_i)的计划优化目标应体现以下特点。

① 拉动式需求：追求计划完成时间和需求时间差距最小；

② 生产负荷均衡：追求计划期内生产负荷方差最小；

③ 尽量缩短造船周期：追求计划周期最短。

考虑上述因素，构建如下优化模型

$\quad\quad\left\{ \begin{array}{l}\min {f_1} = \mathop \sum \limits_{i = 1}^n \left| {{B_{ij}} - {F_{ij}}} \right|,\\\min {f_2} = {\mathop{\rm var}} \left( {{M_j}} \right),\\\min {f_3} = {T_{{\rm{end}}}} - {T_{{\rm{start}}}}{\text{。}}\end{array} \right.$

(4)

其中，f₁表示最小化计划的完成时间和需求时间差距之和，f₂表示最小化计划期内生产负荷方差，f₃表示最小化计划周期；B_ij表示某作业阶段W_ij的需求时间；T_end和T_start分别表示整个计划的完成时间和开始时间。

$\quad\quad\left\{ {\begin{array}{*{20}{l}}{{T_{{\rm{start}}}} = \min \left( {{S_{11}},{S_{21}}, \cdots ,{S_{m1}}} \right),}\\{{T_{{\rm{end}}}} = \max \left( {{F_{1n}},{F_{2n}}, \cdots ,{F_{mn}}} \right){\text{。}}}\end{array}} \right.$

(5)

约束条件如下。

① 需求时间约束：F_ij≤B_ij。

② 物量负荷约束　 M_jP≤CM_j。

③ 场地负荷约束　 N_jP≤K_j。

④ 工序先后关系约束　 F_ih≤S_ij，若 l_ijh=1。

其中，CM_j和K_j分别表示阶段j对应车间的日生产能力和场地数量；M_jp和N_jP分别表示阶段j在工作日p的物量负荷和场地负荷；l_ijh表示分段i各工序的先后关系，若D_ij是D_ih的紧后工序，则l_ijh=1，否则l_ijh=0。

2 改进粒子群算法 2.1 算法改进

因为受粒子更新计算方式的制约，传统的粒子群算法仅适用于连续空间优化问题的求解。而作为典型的离散组合优化问题，生产计划优化问题无法直接运用粒子群算法进行求解。为此，本文基于拉动式计划流程，对粒子群算法进行改进并对优化模型进行求解。

1) 粒子编码。

高效造船分段制造计划优化主要包含两类问题：① 选择作业设备及作业场地；② 选择作业任务执行顺序。

对于问题①，依据每个生产任务的可选设备以及可选场地情况进行编码，具体的编码如图1所示。

其中，生产计划中所包含的生产任务总数通过粒子编码长度L来表示，设备选择编码以X_e标记，场地选择编码以X_k表示。假设e_j表示第j项工序任务对应的可选设备的数量，那么，设备选择编码X_e的第j位编码应取[1，e_j]区间内的整数。同理，若k_j表示第j项工序任务对应的可选场地的数量，那么，场地选择编码X_k的第j位编码应取[1，k_j]区间内的整数。例如，在图1中，X_e的第1位数字为3，表示工序1在可选设备列表中选择了3号设备进行生产；X_k的第1位数字为3，表示工序1在可选场地列表中选择了3号场地进行生产。

对于问题②，若采取基于排序的编码方式，以粒子编码长度L来表示生产计划中包含的总工序数，基于排序的工序执行顺序编码以X_r表示，编码中各基因位的数值为[1，L]内各不相同的整数，表示各个生产任务的执行顺序编号。若采用基于优先权的编码，X_g以各个基因位上的数值来表示相应生产任务的执行优先权数，这些数值是[0，1]范围内的任意值。在对生产计划排程过程中，若发生几项任务同时满足生产资源约束和工序约束的情况，对于优先权系数较高的任务，应优先进行计划排程。如图2所示。

考虑到在基于排序的编码中，粒子群更新后需要将编码中的小数取整，将其转化为[1，L]范围内的整数，同时还要满足各基因位数值彼此不相同这一条件，实现起来有一定难度，而基于优先权的编码中，粒子群的初始化简便，且无需改进粒子群的更新算法就能生成既满足资源约束又满足工序约束的计划方案，因此，本文选择基于优先权的粒子编码方式对工序执行顺序部分编码。

2) 粒子群更新策略的改进。

第t代粒子i的位置向量包括设备选择 $ {{X}}_{{\rm{e}},i}^t$ ，场地选择 $ {{X}}_{{\rm{k}},i}^t$ 以及工序执行顺序 $ {{X}}_{{\rm{g}},i}^t$ 3个部分，各个部分对应的编码如下所示：

$\quad\quad\begin{array}{l}{X}_{{\rm{e}},i}^t = (X_{{\rm{e}},i\_1}^t,X_{{\rm{e}},i\_2}^t, \cdots ,X_{{\rm{e}},i\_L}^t),\\[5pt]{X}_{{\rm{k}},i}^t = \left( {X_{{\rm{k}},i\_1}^t,X_{{\rm{k}},i\_2}^t, \ldots ,X_{{\rm{k}},i\_L}^t} \right),\\[5pt]{X}_{{\rm{g}},i}^t = \left( {X_{{\rm{g}},i\_1}^t,X_{{\rm{g}},i\_2}^t, \ldots ,X_{{\rm{g}},i\_L}^t} \right){\text{。}}\end{array}$

粒子i的速度向量编码表示如下：

$\quad\quad\begin{array}{l}{V}_{{\rm{e}},i}^t = \left( {V_{{\rm{e}},i\_1}^t,V_{{\rm{e}},i\_2}^t, \ldots ,V_{{\rm{e}},i\_L}^t} \right),\\[5pt]{V}_{{\rm{k}},i}^t = \left( {V_{{\rm{k}},i\_1}^t,V_{k,i\_2}^t, \ldots ,V_{{\rm{k}},i\_L}^t} \right),\\[5pt]{V}_{{\rm{g}},i}^t = \left( {V_{{\rm{g}},i\_1}^t,V_{{\rm{g}},i\_2}^t, \ldots ,V_{{\rm{g}},i\_L}^t} \right){\text{。}}\end{array}$

那么，粒子群将按式(6)所示的过程进行更新

$\left\{ \begin{array}{l}V_{{\rm{e}},i\_j}^t = \omega V_{{\rm{e}},i\_j}^{t - 1} + {c_1}{r_1}\left( {{O_{{\rm{e}},i\_j}} - X_{{\rm{e}},i\_j}^t} \right) + {c_2}{r_2}\left( {{Q_{{\rm{e}},j}} - X_{{\rm{e}},i\_j}^t} \right),\\[5pt]V_{{\rm{k}},i\_j}^t = \omega V_{{\rm{k}},i\_j}^{t - 1} + {c_1}{r_1}\left( {{O_{{\rm{k}},i\_j}} - X_{{\rm{k}},i\_j}^t} \right) + {c_2}{r_2}\left( {{Q_{{\rm{k}},j}} - X_{{\rm{k}},i\_j}^t} \right),\\[5pt]V_{{\rm{g}},i\_j}^t = \omega V_{{\rm{g}},i\_j}^{t - 1} + {c_1}{r_1}\left( {{O_{{\rm{g}},i\_j}} - X_{{\rm{g}},i\_j}^t} \right) + {c_2}{r_2}\left( {{Q_{{\rm{g}},j}} - X_{{\rm{g}},i\_j}^t} \right),\\[5pt]X_{{\rm{e}},i\_j}^t = X_{{\rm{e}},i\_j}^{t - 1} + V_{{\rm{e}},i\_j}^t,\\[5pt]X_{{\rm{k}},i\_j}^t = X_{{\rm{k}},i\_j}^{t - 1} + V_{{\rm{k}},i\_j}^t,\\[5pt]X_{{\rm{g}},i\_j}^t = X_{{\rm{g}},i\_j}^{t - 1} + V_{{\rm{g}},i\_j}^t{\text{。}}\end{array} \right.$

(6)

其中，ω为惯性权重系数，c₁、c₂为学习因子，r₁、r₂为区间[0，1]内服从均匀分布的随机数；O_{e,i_j}、O_{k,i_j}和O_{g,i_j}分别表示粒子i的历史最佳设备选择向量O_e,i、历史最佳场地选择向量O_k,i和历史最佳工序执行顺序向量O_g,i的分量 j，j=(1,2,3…,L)。而Q_{e, j}、Q_k,j和Q_{g, j}则分别表示粒子群历史最佳设备选择向量Q_e、历史最佳场地选择向量Q_k和历史最佳工序执行顺序向量Q_g的分量j，j=(1,2,3…,L)。

高效造船分段制造计划的优化问题属于离散数学规划问题。而式(6)所展示的是连续空间优化问题下粒子群的更新过程，在其迭代过程中，编码可能会有小数存在，其结果是设备选择编码 $ X_{{\rm{e}},i\_j}^t$ 和场地选择编码 $ X_{{\rm{k}},i\_j}^t$ 的取值不符合实际意义。因此，需要对粒子更新规则进行调整，使得更新后编码的取值满足实际要求。在此，以含有3个可用场地和4个工序的计划优化问题为例，对改进后的更新策略进行相应说明。

假设第t-1代的粒子i的编码如下

$\quad\quad\begin{array}{l}{X}_{{\rm{e}},i}^{t - 1} = \left( {1,2,1,2} \right),\\[4pt]{X}_{{\rm{k}},j}^{t - 1} = \left( {3,2,1,3} \right),\\[4pt]{X}_{{\rm{g}},j}^{t - 1} = \left( {2,4,3,1} \right){\text{。}}\end{array}$

依照式(6)进行迭代，更新后的粒子编码如下

$\quad\quad\begin{array}{l}{X}_{{\rm{e}},i}^t = \left( {0.4,1.6,1.8,0.6} \right),\\[4pt]{X}_{{\rm{k}},j}^t = \left( {1.2,1.6,0.8,2.3} \right),\\[4pt]{X}_{{\rm{g}},j}^t = \left( {2.5,3.4,3.1,1.2} \right){\text{。}}\end{array}$

工序执行顺序选择采用基于优先权的编码规则，因此，工序执行顺序编码为

$\quad\quad{X}_{{\rm{g}},j}^t = \left( {2.5,3.4,3.1,1.2} \right){\text{。}}$

对于设备选择编码和场地选择编码，采用向上取整方式，因此，设备选择编码和场地选择编码分别为

$\quad\quad\begin{array}{l}{X}_{{\rm{e}},i}^t = \left( {1,2,2,1} \right),\\[4pt]{X}_{{\rm{k}},j}^t = \left( {2,2,1,3} \right){\text{。}}\end{array}$

3) 粒子的解码。

在船舶的生产过程中，存在大量的并行作业过程。如管子加工车间同时加工多个托盘，分段车间同时进行多个分段装焊，船台/船坞同时进行多艘船舶的搭载等，都会导致生产资源为不同生产任务所争夺的情况。这样的生产计划编制问题，可以归结为资源受限制的工程计划问题，可以应用启发式算法来生成可行计划方案。其具体过程如下。

将一个工序任务数量为L的生产计划编制问题的排程过程分为L个阶段，并在每个阶段确定一个工序任务的计划开始时间与完成时间。那么，在阶段p(p=1,2,…,L)中含有3个计划的集合。

① 已排程计划集合CS_p表示截至当前阶段，已完成排程的计划所组成的集合。

② 可排程计划集合AS_p表示现阶段满足工序约束和生产资源制约，可以进行排程的生产计划组成的集合。在拉动式计划体系中，可排程计划对应的是在当前阶段，所有紧后工序都已完成计划排程。

③ 不可排程计划集合US_p表示由于不满足工序约束或者生产资源制约而无法进行排程的生产计划所组成的集合。

在计划排程过程中，每个阶段编码的选择依据是粒子工序执行的顺序。通常在AS_p中选择优先权最大的计划作为当前计划，同时确定计划的开始时间、结束时间和对生产资源的占用时间，完成计划排程工作。当前计划排程完成后，会出现一些计划完成并释放资源，而一些非可排程计划获得满足排程的条件等情况。因此，需要对CS_p、AS_p、US_p集合和生产资源的可用时间进行实时更新。

2.2 求解流程

① 粒子编码：工序执行顺序的选择X_g和作业场地的选择X_k。前者通过优先权系数来表示，即当同一场地各生产任务同时满足排程条件时，则选择优先权系数最大的计划作为当前计划；后者表示工序场地信息，如分段装焊胎位、预舾装场地、小组加工平台和分段涂装场地等。

② 粒子更新策略：工序执行顺序的选择X_g依据式(6)进行更新；场地的选择X_k先依据式(6)进行计算，接着根据取整的规则更新。

③ 粒子解码：粒子的解码运用“拉动式”计划解码算法，根据各工序的需求时间和生产资源占用时间，确定先行计划的完成时间，接着依据标准工期倒推计划开始时间。

3 实船验证

为证明算法的实用性和有效性，选取某船厂的实船分段制造计划进行分析。全船共划分为141个分段，按照高效造船生产模式组织壳舾涂一体化分段制造，针对分段不同作业阶段，对船厂的场地数量及日生产能力等生产资源进行分析统计，如表1所示。

按照高效造船的拉动式工程计划管理体系，根据船台/船坞搭载计划确定的各分段需求时间和各作业阶段的标准作业周期，分析计算该船的分段制造信息，如表2所示。

为准确验证优化效果，若定义优化前后的目标函数值分别为f₀₁、f₀₂、f₀₃和f₁，f₂，f₃，优化总体目标为对模型的3个目标进行无因次化处理并加以综合，则有

$\quad\quad f = {\mu _1}\left( {{f_1}/{f_{01}}} \right) + {\mu _2}\left( {{f_2}/{f_{02}}} \right) + {\mu _3}({f_3}/{f_{03}}){\text{。}}$

(7)

μ₁、μ₂、μ₃分别为目标函数f₁、f₂、f₃的权重系数。为体现需求拉动、负荷均衡的高效造船特点，设μ₁=0.5，μ₂=0.3，μ₃=0.2。式(7)可表示为

$\quad\quad f = 0.5\left( {{f_1}/{f_{01}}} \right) + 0.3\left( {{f_2}/{f_{02}}} \right) + 0.2({f_3}/{f_{03}}){\text{。}}$

采用车间产能利用率对生产资源的利用情况进行分析，设R_cap,j为j工序阶段对应的车间产能利用率，计算公式如下：

$\quad\quad{R_{{\rm{cap,}}j}} = \mathop \sum \limits_{p = 1}^T {H_{jp}}/\left( {T \cdot {\rm{H}}{{\rm{A}}_j}} \right){\text{。}}$

(8)

式中：T为计划期大小，H_jp表示j工序阶段在工作日p内的劳动力负荷，HA_j表示j工序阶段车间每天的劳动力数量。

本文选取Matlab R2016a作为算法程序编译平台。为保证算法在可接受时间内得到最优方案，经过试验选取粒子群算法基本参数：种群内的粒子数为100，最大的迭代次数100，惯性权重系数ω=0.9，学习因子c₁=c₂=0.9。

将优化模型进行编程求解，选取其中的30次随机实验对应的目标适应函数最优值进行系统分析，结果见表3。

为更清楚地分析30次实验所得结果的数据分布，客观评价分段涂装和分段装焊优化后效果，本文采用Matlab中函数boxplot绘制盒图对表3中的目标适应函数最优解进行分析。图3为分段涂装的目标函数和各子函数的盒图分析。

首先分析分段涂装所对应的结果。由表3可知，对于分段涂装所对应的优化问题，其第1个子适应函数值f₁ / f₀₁在30次随机实验中，最小值与最大值分别为0.800 1与0.900 0，第1四分位数Q₁与第3四分位数Q₃分别为0.827 6与0.858 9。因此，在这30组数据上，它的四分位数极差与极差的比值为(0.858 9–0.827 6)/(0.900 0–0.800 1)=31.33%, 说明数据分布集中于中间位置，有相当的统计意义。同时，没有出现离群点，说明所有数据都在四分位数极差的1.5倍范围内。同理，对第2个子适应函数值f₂ / f₀₂和第3个子适应函数值f₃ / f₀₃，其四分位数极差与极差的比值分别为36.27%与36.36%，同样可以得到数据分布比较集中，并且没有特殊的离群点。图4为分段涂装30次随机实验对应的各个目标适应函数的最优值曲线。

从图4可以看出，对于第3个子适应函数值f₃ / f₀₃，其优化后与优化前的周期比较大于1。这是由于优化前尽管分段涂装周期相对较短，但计划严重超负荷运行，而优化后保证了生产计划尽量不超负荷，因此此时分段涂装周期略长，但从负荷均衡角度分析，总的目标函数适应值是可行的。图5为分段装焊的目标函数和各子函数的盒图分析。图6为分段装焊30次随机实验对应的各个目标适应函数的最优值曲线。

图7、图8分别为优化前后分段涂装、分段装焊工序的生产物量负荷对比。

表4为优化前后船体分段制造作业计划各性能指标对比。

由表4可知，对于分段涂装，优化前其方案不可行，而优化后方案不仅可行，而且产能利用率达到88.951 9%，负荷方差为154.158 2。事实上，优化前尽管方案不可行，但仍可计算其负荷方差为3 125.94，是优化后负荷方差的20倍。由此可以看出，优化后的方案更为合理。从分段装焊的结果来看，优化后的产能利用率为83.044 3，是优化前的6倍，而负荷方差小于原方案的负荷方差。需要注意的是，尽管分段涂装的负荷方差从数值看远远大于分段装焊的负荷方差，但涂装量的平均值为107.348 1，而装焊量的平均值为4.084 1，其各自平均值与方差的比值分别为0.696 4和0.896 4。因此，涂装的该比值与相应装焊的比值相当，从而具有较好的优化效果。

通过对比优化前后的分段制造作业计划，可以发现：

1) 优化后的作业计划节拍更加均衡，工序完成和开始数量在相同的时间间隔内保持相对稳定，计划执行控制与管理更为便利；

2) 优化后的生产负荷方差有所减小，优化后分段涂装和装焊的产能利用率提高到近89%和83%，表明生产负荷均衡性和产能利用率经优化后得到明显提高，同时计划的可执行性更强；

3) 优化后的分段装焊周期明显缩短。优化后的分段装焊总周期缩短为376 d，表明优化确实能够提高分段制造效率，缩短分段制造周期。

4 结论

本文以按需拉动、负荷平衡、缩短周期为优化目标，构建了高效分段制造作业优化模型；提出了改进的粒子群算法，对分段制造作业计划进行了优化。通过某船厂分段制造作业计划的实例分析，表明分段装焊产能利用率显著提高，周期明显缩短，优化后的作业计划更为均衡，从而验证了算法的实用性和有效性。本文建立的分段制造优化模型，简单高效，为造船企业推进均衡连续造船提供了简单有效的解决方案。由于分段制造不仅包含作业计划优化问题，还涉及工艺、空间、时间及设施设备的调度等问题，相当复杂，因此如何对各类资源进行全局优化还有待于进一步研究。