基于改进粒子群算法的多机器多任务3D打印智能调度方法

周明霞，张梦娜，李宇，吴 川，张 潇

(徐州医科大学 医学信息与工程学院，江苏 徐州 221000)

0 引言

3D打印，也称为增材制造(AM, additive manufacturing)，根据材料类型与凝聚方式，目前3D打印机主要分为光固化式、光融化式以及热熔化式。与传统的减法制造不同[1]，该技术通过将材料融化经喷头一层一层“打印”目标物品，因此使得3D打印具有应用范围广，能满足个性化多样化要求的优点[2]。同时随着制造技术的不断发展与精度提升，3D打印已进入零件生产等领域[3]，受到了越来越多用户的密切关注。

随着3D打印技术的快速发展，批量3D打印成本高的问题凸显，在一定程度上限制了3D打印技术的应用与发展，因此在工厂生产过程中，提高3D打印机的利用效率，降低3D打印成本，合理安排任务调度方案尤为重要。3D打印调度问题是指在面对多机器多任务的实地工厂生产时，根据目标物品的要求，合理有效地将生产部件任务分配给3D打印机以最终完成客户的要求。在此过程中，工厂需平衡生产部件的成本要求、材料要求、时间要求，部件之间的关系，考虑3D打印机的工作台大小等多方面约束因素[4]，因此面向多机器多任务的3D打印调度问题是一个复杂多变、难以求解的问题。

基于上述问题，为推进3D打印的广泛应用，需将批量打印成本作为重要考虑因素。3D打印技术操作所需时间主要包括人工操作时间(放置物品所需材料、开机输入模型、清理台面)、机器预热时间(达到设定的温度)、打印目标成品时间等[5]。其中，打印机预热时间占据较长的空白时间段，浪费许多人工成本与耗能，因此在考虑调度问题时，根据3D打印机一层一层累积的特点，任务调度时可以将多个部件任务分配在同一台打印机上，以此减少多个机器开机预热时间，提高打印机的利用效率，减少损耗成本。但由于机器工作台面积和最大高度的限制，一些部件无法分配给一些机器，因此难以确定如何分配零件放在合适的机器上生产，即调度问题。

目前，3D打印批量调度成本最优化的研究较少，同时阶段安排打印批次容易陷入局部最优的困境。粒子群算法是一种传统的群体智能优化算法，通过模拟鸟类觅食，将鸟类聚集看做一个粒子群，在不淘汰任何一个个体的情况下，根据群体中个体之间的协作与信息共享最终找到觅食的最优解。由于其思想简单，模拟效果好，粒子群算法被广泛应用于非线性、非凸性或组合优化问题[6]。因此提出一种基于改进粒子群算法的成本最优化模型以求解面向多机器多任务的3D打印调度问题。

以下章节划分：第1章首先介绍国内外研究现状，总结了目前对于面向多机器多任务的3D打印调度问题研究较少，成本最优又在实际生产中扮演重要角色，因此研究该问题十分必要。在第2章阐述研究的多机器多任务的3D打印调度问题，并在第3章给出数学模型。考虑实际生产场景，分析打印工场，结合生产流程，建立单位体积成本模型，在第4章中阐述如何具体应用改进粒子群算法寻找单位体积平均成本最优化，解决面向多机器多任务的3D打印调度问题。第5章中，基于具体的一个实验算例，给出基于改进粒子群算法的3D打印智能调度方法的实验结果与分析。最后在第6章中进行总结。

1 国内外研究现状

智能制造一词，20世纪末最早起源于美国，自此世界多国投入智能制造的研究[7]。3D打印是智能制造领域的重要部分，它是以计算机三维设计模型为直接驱动，目前我国3D打印处于快速发展阶段[8]。

为提高3D打印机利用效率，降低生产成本，推动3D打印技术的进一步应用，以成本最优化为目的，研究面向多机器多任务的3D打印调度问题十分必要。针对3D打印调度成本最优化的研究较少，目前有一些用于批处理过程的生产调度技术，如L.Rickenbacher等人提出了一个针对SLM过程的通用成本模型，对每个过程进行详细的建模与分析，包括预处理和后处理过程[9]；文献[10]通过研究真实的供应链场景设置模型，为分布式备件生产奠定了基础。但面对复杂场景，需要新的生产计划模型促进优化。

同时，对成本模型内部具体架构研究较少，阶段安排打印批次容易陷入局部最优问题。L.Rickenbacher等人提出的成本模型未应用解决实际生产问题，但发现同时构建多个部件，将大大减少任务完成时间，从而使得成本降低[11]。Uzsoy等人提出了面向工件尺寸不同的单机调度问题，同一批次的工件加工时间取决于该批次中加工时间最长的工件[12]，同时同一批次的工件需满足机器的容量限制。食品加工、半导体芯片老化测试等符合该问题的特征[13]。

多机器多任务的3D打印调度是一个难以解决的问题，如何将部件更高效合适的分配进入机器与批次是难以确定的，特别当一个新的部件加入批次时，部件的成本与加工时间都将发生变化，由此结合实际生产问题，在批量3D打印调度中，成本不易控制，难以确定哪个零件在哪个机器上生产。因此，研究多机器多任务的3D打印调度问题并提出一易实施高效率的方法是十分必要的。

2 多机器多任务的3D打印调度问题阐述

常用的FDM(fused deposition modeling)类型的3D打印机一般具有喷头、热床、丝杆、步进电机和控制板等部件[14]。喷头一般是由步进电机、加热器、喷嘴和风扇组成。加热喷嘴后，将耗材通过喷嘴挤出在热床上。打印机的喷头与热床固定在丝杆上，通过转动丝杆调节喷头移动。而金属3D打印机中核心部分即为单螺杆挤出装置，主要由螺杆、料筒、喷嘴、螺杆驱动装置、支承装置等几大部分组成[15]，是熔融原料制备装置、堆积快速成形的前提保证。

金属3D打印的原理是先通过计算机辅助设计(CAD)或计算机动画建模软件建模为一组3D数据，将数据与原料输入3D打印机，机器便会逐层分切，金属耗材为固态材料，在高功率光束照射下，固态材料烧结或熔解，冷却后成型，通过层层烧结、熔炼和焊接制成金属物品。

在3D打印调度问题中，假设有需要加工的P个部件，工厂中有M台机器，每个部件、机器有预定义的相关参数信息。同时，根据部件的需求，这些部件包含附加信息，如截止日期、材料需求等。在分配收到订单时，遵循以下原则：1)部件不可再分割，每个部件作为一个独立的整体被明确的分配到一个机器上；2)所有的部件都需要进入调度序列最终打印完成；3)被分配到机器上的部件的底面积不得超过机器的工作台面积，高度不得超过机器的高度；4)一个机器可以同时处理多个部件。

在讨论成本问题时，每台机器设置指定的打印速度和层厚，设置固定的工作台底面积及支持的最大高度，同时在人工操作阶段、清理阶段，设置固定的人工成本与时间成本。当一个工厂收到订单时，需要根据订单需求将部件重新组合分配至合适不同的机器上完成，同时使订单成本最小。在此过程中，研究需要解决以下几个关键问题：1)所有部件都分配给合适的机器；2)在合适的机器上确定所有部件的加工顺序；3)目标是使得加工成本尽可能小。

面向多机器多任务的3D打印调度问题，在满足约束的情况下，可将部件放入同一个作业中同时被一个机器加工，以提高3D打印机的利用效率。在理想状态下，M个机器加工P个部件所需的总成本与时间成正相关。由于3D打印技术是层层累积的，在机器同时处理多个部件组成的一个作业时，完成时间取决于作业中高度最大的部件打印完成时间。即：

hj=max{hp},p∈Pmj

(1)

其中:Pmj表示分配在机器m上的作业j中的部件集。

在调度过程中，所有部件在高度和底面积的限制下，随机分配给合适的机器，经过组合优化调度，最终使得成本最优化并完成所有部件的打印，由此确定的调度序列即为问题的最优解。

3 单位体积平均成本最优化模型

为了方便表述搭建的研究多机器多任务的3D打印调度问题模型，表1给出构建解决问题的数学模型所用的符号及其定义。

表1 符号及其定义

每个部件包含部件高度h、体积v以及底面积s共3个参数信息，机器包含支持的最大高度H、工作台面积S两个约束参数，为保证部件打印完整与准确，在调度过程中，需满足以下约束：

1)当一个作业的任意一个部件分配给一个机器时，该作业必须全部分配在该机器上；

2)部件的高度需小于该机器支持的最大高度，否则该部件不可在不符合条件的机器上打印；

max{hp·Xjp·Ymj}≤H

(2)

3)同一作业中打印的部件的底面积之和需小于该机器工作台的面积，否则不可调度安排在该机器上。

(3)

4)每个部件之间相互独立，每台机器之间相互独立，任何一台机器的工作情况不影响其他机器。

5)不考虑故障等不确定因素。

在这一模型中，机器相关系统参数已知。每个部件需且仅需打印一次，对机器加工多少部件没有要求。

P个部件在M个机器上的总成本计算公式为：

MTC×Tah×hj+Tn×Cp+W

(4)

其中:hj=max{hp},p∈Pmj，Pmj表示分配在机器m上的作业j中的部件集。

该成本计算方式主要包括4个部分:1)由总体积所需确定的原材料融化的成本；2)由完成时间确定的分层打印成本，由于3D打印技术是层层累积的，在机器同时处理多个部件时，即一个作业时，完成时间取决于高度最大的部件打印完成时间；3)人工成本，建立新作业机器开机、预热以及清理机器的时间统称为机器设置时间，此过程需要人工操作；4)机器工作期间的损耗成本[16]。

为研究面向多机器多任务的3D打印调度问题，在合理调度完成部件的打印任务基础上，提出构建单位体积平均成本最小化的函数如下：

(5)

综上，面向多机器多任务的3D打印调度问题，构建考虑上述单位体积平均成本的模型，模型建立如下：

(6)

4 基于改进粒子群算法的问题求解

4.1 粒子群算法

粒子群优化算法(particle swarm optimization)是一种群体智能优化算法，1995年由Eberhart博士和Kennedy博士提出，通过模拟鸟类觅食行为，每只鸟都作为一个独立觅食的个体，通过传递信息，让其他的鸟知道自己的位置与食物情况，以此判断自己所找到的食物是不是最优的，这样利用群体中个体的信息共享与协作找到全局最优[17]。

粒子群算法思想容易简单且只需调整少量参数便可实现，目前已广泛应用于优化问题[18]。粒子群算法通过一群无质量的独立粒子来代表鸟类，每个粒子仅有位置矢量与速度矢量两个参数，以表示粒子所处的位置以及运动的速度、方向[19]。在智能优化过程中，每个粒子单独寻找最优解，并记录下来，根据适应度即目标函数值的不断更新，经过粒子群之间的位置信息以及目标函数值的共享，记录当前个体的最优值Pbest及全局最优值Gbest。经过算法的不断迭代，粒子群们向最优位置移动，最终得出全局最优解与位置。

面向多机器多任务的3D打印调度问题，尝试在编码方式及更新策略上进行针对性改进。首先采用了十进制顺序二维编码方式表示问题的解，并在更新策略上应用线性递减权值的动态ω来调整全局与局部的搜索能力。

4.2 编码与解码方案

面向多机器多任务的3D打印调度问题比较复杂，在编码过程中不仅需要考虑部件的组合调度，还需要为一个作业中的所有部件选择一个合适的加工机器，因此仅仅采用一维的部件编码是不可取得。因此，采用十进制顺序二维编码方式表示问题的解。第一部分为基于机器的编码，用于确定每个部件的加工机器选择，第二部分为基于部件的顺序编码，用来确定部件的加工组合顺序。通过该二维编码方式，可以得到问题的一个可行解。

假设一工厂接到10个部件的订单，编号为1,2,3,…，10，可调用的加工3D打印机3台，编号为1,2,3，则其中的一个可行解表示如下：

部件编号 1 2 3 4 5 6 7 8 9 10

机器向量 1 3 2 1 1 3 2 1 3 2

顺序向量 1 1 1 2 3 2 1 2 1 2

部件编号对应的机器向量值，表示对应的加工机器编号，如部件1,4,5,8在机器1上加工；部件编号对应的顺序向量值，表示部件组成的一个作业在对应机器上的组合加工顺序，如机器1加工的4个部件加工顺序为[p1]、[p4,p8]、[p5]，部件4与8作为一个作业放入机器1加工，机器1需加工4个部件组成的3个作业。

则上述粒子解码后，得到3个机器加工10个部件的一个解，在机器M1上完成部件P1的单独加工、部件P4、P8的组合加工及部件P5的单独加工的3个作业，在机器M2上完成部件P3、P7的组合加工与部件P10的独立加工的2个作业，在机器M3上完成部件P2、P9的组合加工与部件P6的单独加工的2个作业。

机器1 [p1]、[p4,p8]、[p5]

机器2 [p3,p7]、[p10]

机器3 [p2,p9]、[p6]

4.3 种群初始化

一般来说，随着迭代次数的增加，算法的搜索时间增加，但搜索的结果可能会更好，因此对于粒子群算法，选择合适的迭代次数与种群数十分重要。一般地，种群数取20～50，具体取值根据研究问题的复杂程度而定。针对多机器多任务的3D打印调度问题，因其较为复杂，故设置种群数PN为50，迭代次数IN为300。

粒子的初始位置均匀的分布在整个搜索空间，初始化过程中，将粒子群初始化为一群可表示问题解的随机粒子，每个粒子包含机器向量与顺序向量二维实数，向量值的取值空间为[1,m]，m为机器总数；初始速度可设置为0或一个随机值；将对应的初始适应度函数即单位体积成本值作为个体最优解。

在初始设置速度时，设置为0时，粒子与搜索空间是静态的，当速度非0时，考虑到当粒子速度较大时，粒子移动较快，容易错过最优解，从而增加迭代次数，提高了算法复杂性，较小时，开发能力强，但容易陷入局部最优，收敛缓慢，算法效率不高[20]。因此为合理寻求算法搜索能力与收敛速度的平衡，设置了粒子的最大速度，通常设定为粒子的范围宽度，且保持变量变化的范围为10%～20%。

4.4 更新策略

在初始化为一群随机粒子(随机解)后，这些粒子通过不断的分享个体与群体之间的位置与最优值，迭代后更新位置与目标函数值，最终得到最优解。在算法的每一次迭代中，记录下当前个体的最优值Pbest以及全局最优解Gbest，之后更新自己的速度与位置。

种群的多样性即各粒子个体上的差异决定了算法的全局探索能力，因此在更新个体粒子向最优解学习移动时，如何保持粒子间的差异性十分重要。在粒子群算法搜索的前期，往往希望能快速的搜索更多的领域并确定全局最优的大致范围，而在搜索后期，往往希望快速准确找到局部的最优解，完成收敛，因此在整个算法迭代过程中，搜索要求与希望不是一成不变的[21]。

个体粒子在向最优解靠拢时，一定程度上对自身轨迹进行调整，开展对未知领域的探索，此探索能力为全局探索能力。而在原始轨迹上进行进一步探索的便称为局部探索能力。为有效防止陷入局部最优，采用线性递减权值的动态ω来调整全局与局部的搜索能力。ω又称为惯性因子，取值为非负。当ω取值较大时，全局搜索能力较强，而局部搜索能力较弱；当ω取值较小时，全局搜索能力较弱，而局部搜索能力较强。一般在实际应用中ω取值由大变小，先全局最优搜索至大致范围，在局部搜索最优值，提高效率与准确率。

惯性因子ω更新公式如下：

ωt=(ωini-ωend)(Gk-g)/Gk+ωend

(7)

其中：Gk为最大迭代次数，ωini为初始惯性权值，ωend为迭代至最大次数时的惯性权值，一般取ωini=0.9，ωend=0.4，从而有利于算法后期的收敛。

速度更新公式如下：

vi+1=ω×vi+c1×rand()×(Pbestt-xi)+

c2×rand()×(Gbesti-xi)

(8)

其中：vi+1为粒子的速度，rand()代表介于(0，1)的随机值，c1、c2为学习因子，通常c1=c2=2，xi为粒子的当前位置。

PSO算法没有像遗传算法的交叉变异操作，而仅仅根据自己的经验更新搜索，追随最优的粒子。式(8)包含3个部分之和，第一部分表示上次速度矢量的影响，第二部分称为自身认知项，表示基于个体经验粒子向自身最优解移动的矢量，第三部分称为群体认知项，表示基于个体与群体的经验粒子向全局最优解移动的矢量。

位置更新公式如下：

xi+1=xi+vi+1

(9)

种群在迭代过程中，根据式(8)、(9)更新速度与位置矢量，但由于本问题中部件与机器都是整数，更新后的新粒子不一定代表有效解。因此对更新后的位置矢量进行四舍五入和边界限制处理调整，使之成为有效解。

基于前文建立的面向多机器多任务的3D打印调度问题的数学模型，算法中的适应度函数为单位体积平均成本函数。在迭代过程中，不断比较适应度，并将更小的单位体积成本值更新为全局最优值。

4.5 收敛依据

优化收敛停止准则一般有两种，一是设置最大迭代次数，二是达到可接受的满意适应度值，设置上一次最优化适应度值与更新后的最优化适应度值之间的差值小于某个值停止迭代，即达到收敛要求[22]。本研究设置收敛判据为迭代次数是否到达到300次，达到收敛判据后，便退出循环，输出结果。

4.6 算法流程

面向多机器多任务的3D打印调度问题，基于改进的粒子群算法，将目标函数设置为单位体积平均成本，考虑机器工作台底面积与支持的最大高度及其他约束，通过不断迭代优化最终得到单位体积成本最优值及最优调度方案。

算法的流程如图1所示。

图1 改进粒子群算法流程图

算法的详细步骤如下：

步骤1：依据调度原则，在考虑约束的情况下，初始化粒子群及参数设置，包括粒子数PN，迭代次数IN，学习因子c1、c2，惯性权重ω，最大粒子速度等；

步骤2：根据参数设置初始化粒子位置矢量与速度矢量，根据式(6)所建立的模型，计算适应度单位体积成本值，初始化个体最优值Pbest和全局最优值Gbest；

步骤3：利用式(8)、式(9)更新粒子的速度矢量与位置矢量；

步骤4：对更新后的粒子进行编码解码，更新适应度单位体积成本值，更新种群；

步骤5：与之前存储的单位体积成本比较，更新个体最优值Pbest和全局最优值Gbest，将更优的目标函数值更新，同步更新对应的粒子解集；

步骤6：判断是否满足收敛判据，若迭代次数满足设定的迭代值，则停止迭代，否则转到步骤3继续执行；

步骤7：循环结束，输出最终的目标函数值与粒子解集，得到结果。

5 实验结果与分析

选区激光熔化金属3D打印步骤如下：1)设计模型；2)将模型转化为打印机能识别的Gcode代码；3)将代码输入打印机开始打印；4)铺粉器将金属粉末铺至打印工作台；5)激光器将金属粉末融化后完成一层的打印；6)每完成一层的打印，打印平台会便下降一层的高度，直至打印完成。3D打印实例如图2所示。

图2 批次调度实例

5.1 实验算例

面向多机器多任务的3D打印调度问题，实验任务设置为在2个不同的机器完成6个不同的部件打印任务，使得生产成本最优，其中要求部件P4不可在机器M2上加工。

实验数据中部件与机器的相关数据来自 Exeter’s ORE-Repository数据集，该数据集可供永久访问。此外，根据实际生产应用情况，增加机器单位体积损耗参数。需加工部件相关参数如表2所示，机器相关参数如表3所示。

表2 部件参数信息

表3 机器参数信息

经过分析，部件P2的高度大于机器M1的支持最大高度，部件P3的高度大于机器M1的支持最大高度，底面积大于M1的工作台面积，部件P4明确要求在机器M2上完成，因此在调度过程中，基于约束条件，部件P2、P3不可分配给机器M1，部件P5在调度过程中不可分配给机器M2。

实验仿真环境为Windows 10操作系统，采用python3.8实现算法的编程。在该算例中，总的部件数P为6，机器数M为2。基于改进粒子群算法，在python3.8环境下运行，将算例中的数据代入进行了30次独立的运行搜索，经过多次迭代最终得到了最优方案及最优单位体积平均成本。

具体参数设置如下：粒子群种群数PN为50，迭代次数IN为300，学习因子c1=2、c2=2，惯性权重ωini=0.9，ωend=0.4。

初始化过程中，求得各部件在各机器上的单位体积平均成本如表4所示，由于不满足约束条件，部件P2、P3不可分配给机器M1，部件P4在调度过程中不可分配给机器M2，相应位置的目标值为空。则其中的一个可行解为：

机器M1 [P1]、[P4]、[P5]、[P6]

机器M2 [P2]、[P3]

该调度方案表示各部分单独在机器上打印，取单位体积平均成本低的作为加工机器。由此计算出总单位体积平均成本为4.632 5 GBP/cm3，即适应度初始值为4.632 5 GBP/cm3。

表4 各单位体积平均成本

5.2 实验结果

经过粒子群算法300次迭代，不断更新个体最优值与全局最优值，式(8)、式(9)更新粒子的速度矢量与位置矢量，最终最优方案结果如表5所示。

表5 最优调度方案

即调度方案为：

机器M1 [p1]、[p4,p5]

机器M2 [p2,p3,p6]

在机器M1上完成部件P1的单独加工与部件P4、P5的组合加工的2个作业，在机器M2上完成部件P2、P3、P6的组合加工1个作业，其对应的单位体积平均成本为4.531 2 GBP/cm3。

最佳调度方案与一部分其他调度方案对比的单位体积平均成本减少量如表6所示。

表6 最优调度方案与其他方案对比

在30次计算中，有22次达到最优，证明了方法的可靠性。面向多机器多任务的3D打印调度问题，采用上述最优调度方案进行部件与机器的调度，最终比单独打印加工的单位体积平均成本(初始值)4.632 5 GBP/cm3降低了0.101 3GBP/cm3，较其他调度方案均降低了单位体积平均成本，因此认为提出的基于改进粒子群算法的面向多机器多任务的3D打印智能调度方法是有效且实用的，较好地降低了生产成本，提高3D打印机的利用效率。

6 结束语

针对批量3D打印成本高，多机器多任务的3D打印批次调度复杂的问题，建立以最小单位体积平均成本为目标的优化模型，并提出一种基于改进粒子群算法的智能调度方法求解该模型。实验结果表明该模型方法能有效解决面向多机器多任务的3D打印调度问题，合理的调度序列有效地降低了完成订单的总成本，有利于提高工厂的打印效率，以更低的成本为客户提供服务，有利于3D打印技术的推广。随着3D打印技术的不断发展，未来的3D打印调度问题将越来越复杂，在成本最优化问题上的研究也将更加深入。未来将在此基础上结合实际工厂完成订单情况，更加

深入的分析，以解决更复杂的问题。同时深入研究面向多机器多任务的3D打印调度问题，与其他智能优化算法进行对比，进一步分析算法能力，提高算法搜索能力。