考虑零件构建方向的增材制造单机调度研究

黄 彬，肖彦楷

(福州大学机械工程及自动化学院，福建 福州 350108)

增材制造(additive manufacturing，AM)技术是通过逐层添加材料的方式制造实体零件的技术[1]。作为一种不需要传统的刀具、夹具、模具以及多道加工工序的新兴智能制造技术，增材制造对解决复杂结构物体的加工难题、缩短新产品的研发周期具有极大的帮助。以往增材制造的研究主要集中于材料、设备、工艺及精度等方面，近年来，对增材制造生产调度的研究引起了国内外学者的重视。

在增材制造技术中，选择性激光熔融(selective laser melting，SLM)工艺因为其具备制造可直接使用金属零部件的能力，是目前发展最快、应用前景最好的技术之一。面向SLM工艺的生产调度研究中，Li等[2]建立了以最小化平均成本为目标的调度模型；Chergui等[3]建立了以最小化拖期时间为目标的增材制造调度模型；Kucukkoc等[4]以最小化最大完工时间为目标，研究了面向SLM工艺的调度问题；Fera等[5]建立了以最小化生产成本以及提前期/拖期为目标的单机调度模型。

上述研究考虑了零件体积、机器容积、交货期等因素，且假设零件只有单一的构建(打印)方向。文献[6]表明，零件在满足工艺以及客户需求时，通常有多种构建方向可供选择，而不同构建方向的组合对零件加工时间会有很大的影响，因此有必要研究考虑零件构建方向的增材制造调度问题。本文在综合考虑零件构建方向、交货期的前提下，研究面向SLM工艺的AM机器的单机调度问题，提出了以最小化零件单位体积生产成本为优化目标的数学模型，并设计了一种改进分布估计算法对模型进行求解。

1 问题描述及调度模型

1.1 问题描述

与传统机器加工不同，来自于不同订单，不同形状、尺寸和交货期的零件可同时在一台AM机器上加工。本文将同时在同一AM机器上的零件加工定义为一个作业，作业的完工时间取决于作业内最后一个零件的完工时间。在满足一定条件的情况下(足够的有效生产面积，交货期等)，一个作业可能包含多个不同的零件，一般每个零件至少有一个备选构建方向。由于不同的零件构建方向将导致零件加工时的最大高度不同和在AM机器上的投影面积不同，进而影响到作业内零件的数目，导致加工时间和成本不同，因此零件分配前要明确零件的备选构建方向。当采用不同的零件分配方案时，作业的数目有可能改变。

增材制造作业总成本由零件的最大高度和总体积决定，因此不同零件组合成的作业的生产成本不同，且相同零件组合成的作业在不同的构建方向下的生产成本也不相同。一个作业内安排的零件越多，必然导致作业的加工时间越长，但可以减少总作业数目以减少机器准备时间(布置作业以及清理时间)，并且多个零件还可以均分零件分层时间(分层时间由作业内零件最大高度决定)所导致的成本；而作业内零件较少时，零件可以选取高度较低、投影面积较大的构建方向以降低成本，但这势必增加多个作业带来的机器准备时间以及额外的零件分层时间，降低机器利用率。因此增材制造的单机调度要求在一定的优化目标下，将所有订单中的零件拆分到几个作业并依照一定的加工顺序分配到一台AM机器中，从而找到一种可行的调度方案。

1.2 调度模型

1.2.1模型假设

面向SLM工艺的增材制造单机调度问题，做以下假设：1)加工过程中只考虑一种制造材料；2)作业的零件之间不会相互接触，且不考虑零件之间的嵌套问题(嵌套指在一定条件下，小零件可放在大零件的孔隙中或斜面下)；3)为了保证零件质量，零件在加工平台上仅放置一层；4)所有零件的备选构建方向均能满足质量要求，并且都可放置于AM机器的生产区域内；5)生产过程中，机器具有固定的加工速度、层厚度参数及单位人工成本、作业生产准备时间。

1.2.2数学模型

定义以下变量符号：Ii为第i个零件(i=1,…,m)；Jj为第j个作业(j=1,…,n)；Kik为第i个零件的第k个备选构建方向(k=1,…,M)；hik为第i个零件在第k个备选构建方向的高度；aik为第i个零件在第k个备选构建方向在生产区域的投影面积(包含了一定的裕度，以避免零件接触)；Vi为第i个零件的体积；A为机器的生产区域面积；ts为机器的准备时间；th为单位高度的分层时间；tV为单位体积材料的加工时间；Ct为单位时间机器的运行成本；CH为单位时间的人工成本；Dj为第j个作业的交货期，等于作业内所有零件交货期的最小值；hmax(j)为第j个作业内零件的最大高度；C为所有作业零件的单位体积生产成本；xij为反映零件i是否放入作业j的二进制决策变量，yik为反映零件i是否选择备选机构建方向k的二进制决策变量；zj为反映作业j是否被安排生产的二进制决策变量。

由上可得，作业j零件的生产成本Cj为：

Cj=(tg(j)+tp(j))Ct+(ts+tg(j)+tp(j))CH

(1)

(2)

tp(j)=thhmax(j)

(3)

式中：tg(j)为作业j生产时加工材料的时间(激光头的运动时间)；tp(j)为作业j生产时的分层时间。

作业j的完工时间tj为：

tj=tj-1+tp(j)+tg(j)+ts,t0=0

(4)

以最小化所有作业零件的单位体积生产成本为优化目标的增材制造单机调度问题可以描述为如下模型：

(5)

(6)

(7)

(8)

zj-zj+1≥0

(9)

(10)

tj-Dj≤0

(11)

式(5)为最小化所有作业零件单位体积生产成本的目标函数；式(6)表示一个零件最多只能安排在一个作业中；式(7)表示每个零件生产时只能选择一个备选构建方向；式(8)表示每个作业只能生产一次，不能重复生产，且所有作业都需要完成；式(9)表示作业按照先后顺序加工；式(10)表示每个作业内零件的总投影面积要小于机器总生产面积；式(11)保证作业的交货期。

2 模型求解的改进分布估计算法

2.1 分布估计算法(EDA)

分布估计算法(estimation of distribution algorithm，EDA)是一种基于统计学原理的随机群体优化算法[7]，该算法具有较强的全局收敛能力和较快的收敛速度。以二进制编码问题为例，算法中解空间分布的概率模型可以使用一个概率向量ρ(g)表示：

ρ(g)=[ρ1(g),ρ2(g),…,ρn(g)]T

(12)

式中：ρi(g)为在第g次迭代中个体的第i个基因位置上取值为1的概率。在本文模型中，基因位置i代表采用某个构建方向的零件i。

(13)

式中：α为学习速率，α∈(0,1)。

2.2 改进的分布估计算法(IEDA)

2.2.1编码方式

算法中作业所包含的零件组合以及其对应的构建方向都采用自然数编码方式，即Jj=[I1,I2,…,Ii]，Kj=[K1k,K2k,…,Kik]，1≤i≤m，1≤k≤M。Jj表示作业j内所包含的零件组合，Kj表示作业j内各零件构建方向的组合。

一个生产流程通常包括多个作业，称为作业组，可表示为J=[J1J2…Jj]T。

由于一个作业能容纳多少零件是由零件所占的生产面积决定的，因此每个作业的零件数不一定相同。每个作业内的零件具有固定的构建方向，作业组的构建方向矩阵可表示为K=[K1K2…Kj]T。

2.2.2概率模型及其更新

概率模型及其更新机制是设计分布估计算法的关键。本文采用m×M的ρ(g)作为概率模型，表征各零件选取各备选构建方向的概率，如式(14)所示：

(14)

式中：ρik(g)为第g次迭代中零件i选择第k个备选构建方向的概率，矩阵每行的元素之和为1。显然本文中ρ(g)所产生的每个个体都有m个随机采用构建方向k(1≤k≤M)的零件。

为保证算法初始阶段对解空间的均匀采样，初始概率分布取均匀分布，同时在每次迭代中选取适应度值最优的前10%个体作为更新概率模型的依据，使用Heb规则更新概率矩阵，如式(15)所示：

(15)

2.2.3适应度函数

本文构造的适应度函数Fitness如下：

Fitness=C+F(x)

(16)

式中：C为目标函数；F(x)为惩罚函数。当作业满足式(6)～(11)的所有约束时，F(x)等于0；否则，F(x)为足够大的正值。

2.2.4邻域搜索策略

由于EDA局部搜索能力较差，因此本文引入一种邻域搜索机制设计一种IEDA来求解上述调度问题。在已知零件作业分组的情况下，对原精英种群内每个作业内零件的构建方向进行搜索，降低作业内零件的最大高度，可以较好地弥补EDA算法的不足，提高收敛效率。具体流程如下：

1)判断作业j中最高的零件，记为Imax。如果Imax当前的构建方向是其所有备选构建方向中高度最小的构建方向，则转至步骤5)；如果Imax存在其他高度更小且投影面积位于作业剩余生产区域面积内的备选构建方向可供选择时，则进行步骤2)；如果Imax由于作业剩余生产区域面积不足而无法选择其他高度更小的备选构建方向时，转至步骤3)。

2)选取Imax可供选择的备选构建方向中高度最小的构建方向，返回步骤1)。

3)判断除Imax外的其他零件是否存在投影面积比其当前构建方向的投影面积小且高度不高于Imax的备选构建方向，如果存在则进行步骤4)；如果不存在转至步骤5)。

4)随机选取步骤3)中可选零件中的一个零件，改变其构建方向，选取一个投影面积小于它当前投影面积且高度不高于Imax高度的备选构建方向。返回步骤1)。

5)如果j达到最大值，转至步骤6)；否则j←j+1，转至步骤1)。

6)根据式(16)计算并对比经过局部搜索后的各作业组的适应度值，用适应度值最优的作业组取代精英种群中的原作业组。

2.3 算法流程

1)生成初始种群和概率模型，令迭代代数iter=1，根据式(16)计算各作业组的适应度值；

2)选择适应度值最优的前10%的个体作为精英群体；

3)对精英群体进行邻域搜索；

4)根据式(15)更新概率模型(式(14))；

5)根据概率模型对精英种群采样生成新种群；

6)如果iter已经达到最大值，转至步骤7)；否则令iter←iter+1，转至步骤2)；

7)输出最优解。

3 算例

某企业需用一台AM机器加工一批零件，每个零件的体积、交货期、备选构建方向及相应的投影面积及最大高度见表1，AM机器参数见表2。

表1 零件的尺寸及其交货期

续表

表2 AM机器的参数

在同一台式机上，分别运行EDA和IEDA算法各300次求解本文调度问题，算法的最大迭代代数为50，种群大小为50。两者的优化结果对比见表3，由表3可以看出，IEDA的收敛稳定性比EDA更好，收敛率更高。求得的最优作业分配为[1,2,3,0;4,5,6,7;8,9,10,0]，相对应的构建方向为[3,3,1,0;4,1,3,2;4,3,3,0]。即1,2,3为第一个作业，4,5,6,7为第二个作业，8,9,10为第三个作业；零件1选择其编号3的构建方向，零件2选择其编号3的构建方向……零件10选择其编号为3的构建方向。本调度方案的每立方厘米材料的加工成本为21.374 3元，各作业的完成时间分别为77.674 4 h、108.211 0 h和44.379 1 h。

表3 EDA与IEDA优化结果对比

4 结束语

本文面向选择性激光熔融工艺，建立了以最小化所有零件单位体积生产成本为优化目标的单机调度模型，以解决考虑零件构建方向的增材制造生产调度问题，并引入邻域搜索策略对标准分布估计算法进行改进，设计了一种改进分布估计算法求解本文的调度问题。算例分析表明该方法可行、有效，为增材制造生产调度的研究提供了一种新的方法和途径。