分布式3D 打印服务的实时多任务调度研究*

赵军富 杜海渊 靳永胜 李建军

（①内蒙古科技大学，内蒙古 包头 014010；②内蒙古蒙牛乳业（集团）股份有限公司，内蒙古 呼和浩特 010000）

“工业4.0”由集中式控制向分散式增强型控制的基本模式转变，建立了一个高度灵活的个性化和数字化的产品生产模式，实现大规模定制[1-4]个性化产品。当今，智能制造与IIoT 和云制造（CMFg）的结合，使3D 打印技术成为大规模定制和大规模生产的强大动力[5-7]，有效地缩短了设计与原型制造之间的时间[8-11]。3D 打印成为定制化大规模生产的最佳技术[12-14]，能以较少的材料和能源制造出常规制造技术无法实现的复杂形状。

在IIoT 中，制造资源都被收集在一个虚拟的资源池中，为用户提供在线按需使用的制造服务[15-17]。在符合时间、成本、服务质量（QoS）和服务可用性的情况下，在一段时间内分配和调度服务以执行一组任务的过程称为多任务调度。本文研究IIoT 中多任务调度的方法，实现自主实时多任务调度来提高制造系统的性能[18-20]。

3D 打印、云制造和IIoT 技术的快速发展，使3D 打印能够以相对低的成本制造定制产品，其应用范围从研发领域的原型设计扩大到医疗、航空、汽车等领域的大规模定制生产[5-10]。Zhou L 等[21]在云制造中建立3D 打印服务模型，描述了服务需求者、服务提供者和云制造平台之间的关系，给出了3D 打印服务匹配过程中的模型尺寸、打印精度、打印材料、成本、时间等属性，对3D 打印服务调度（3DPSS）提出了一种基于优先级的改进遗传算法。该改进遗传算法与粒子群优化算法（PSO）和模式搜索算法相比，改变了任务调度的数量，缩短了平均任务交付时间。

Chen T 等[6]为3D 打印制造业设计了一个物联网系统，该系统为实现工作量平衡使用分支限界法寻找最短交付路径，以尽量减少订单交付时间。

Luo X 等[22]提出了一个建模框架，解决网络制造环境下有效管理3D 打印资源的匹配问题,研究了基于动态和静态数据的3D 打印任务分配方法，在建模过程中采用二分图匹配算法对静态特性的各项参数指标进行了定量分析，同时对3D 打印机的动态特性，建立了通用的动态数据采集系统用于实时监测和协调3D 打印机，尽量缩短任务完成时间。

表1 为对现有关于分布式3D 打印服务调度文献的归纳总结，但这些研究中忽略了几个重要方面。首先，这些研究只关注静态调度而完全忽略3D 打印服务调度中的实时性要求，与统一调度概念相违背。其次，大部分研究都针对数量有限的3D 打印服务进行调度，无法在高负荷的情况下平衡分布式3D 打印机之间的工作量，难以提高资源利用率。最后，这些研究选择了基于群体的优化方法来调度3D 打印服务，如改进遗传算法，采用这种优化算法可能导致提交的3D 打印任务响应时间相对延长，与实时性要求相矛盾。为此，本文研究了一个基于IIoT 定制的3D 打印任务的实时分配和调度架构，提出了实时分配算法和基于优先级的自适应实时多任务调度的算法（adaptive real-time multi-task priority-based scheduling，ARMPS），为定制的3D打印任务进行最佳分配和动态实时调度，实现负载平衡，提高能源效率和资源利用率，促进生态可持续发展。

表1 对现有分布式3D 打印服务调度文献总结

1 3D 打印任务在IIoT 中实时分配与调度

1.1 分配与调度模型

图1 所示为本文提出的基于IIoT 定制的3D 打印任务的实时分配和调度架构。3D 打印任务的需求者将3D 打印模型和3D 打印属性提交给IIoT 平台，3D 打印服务的每台3D 打印机都有其特定的属性，主要属性包括打印材料、打印精度、喷嘴直径、填充百分比、每克价格、模型体积、G 代码的路径长度、最后期限等。

图1 3D 打印任务实时分配与调度框架

每个定制的3D 打印任务通过分配和调度模块在3D 打印服务提供商数据库中精确选择最合适的3D 打印机，在满足实时性和分布式3D 打印之间的工作负载平衡要求下，当需求者提交多个零部件需求时，必须指定这些零部件状态为关联或非关联，关联零部件即为同一组，将使用相同的3D 打印机，非关联的可以使用不同的打印机。

1.2 任务分配与调度

为了实现能源优化，平衡3D 打印机之间的工作量，采用基于图形着色的在线任务分配算法[23]，根据匹配属性将提交的3D 打印任务与IIoT 平台中最合适的3D 打印机相匹配。同时，提出一种基于优先级的自适应实时多任务调度算法，实时调度每一个3D 打印任务，满足3D 打印任务的实时性以及动态性要求。

1.2.1 任务分配

在线图着色算法是图形的顶点按顺序到达，每个新的顶点一旦到达都被分配一个不能改变的颜色。本文引入在线图着色的任务分配算法，图形中的每个顶点代表一个要执行的3D 打印任务，颜色代表3D 打印机，在线图着色的定义与将3D 打印任务分配给3D 打印机的思路完全一致，每个顶点的着色类似于将一个3D 打印任务通过严格的属性匹配方案分配给一个3D 打印机。匹配打印任务主要依据的打印属性如下。

（1）打印材料（M）。假设每台3D 打印机的打印材料不能改变，则 3D 打印任务所需的打印材料（M3DPT(x,y)）必须与3D 打印机的打印材料（MPZ）相同，即M3DPT(x,y)=MPZ。

（2）打印精度（AC）。打印精度（AC3DPT(x,y)）与打印每一层的厚度有关，对机械性能和打印品的表面光滑度有要求。3D 打印任务所需的打印精度应大于或等于3D 打印机的打印精度（ACPZ），即AC3DPT(x,y)≥ACPZ。

（3）喷嘴直径（ND）。3D 打印机喷嘴的直径（ND3DPT(x,y)）影响3D 打印部件的细节、强度和重量。打印3D 打印任务所需的喷嘴直径应大于或等于3D 打印机的喷嘴直径（NDPZ），即ND3DPT(x,y)≥NDPZ。

（4）填充百分比（INF）。填充百分比决定3D 打印部件的强度，3D 打印任务的指定填充率（INF3DPT(x,y)）应小于或等于3D 打印服务提供商在打印零件时调整的填充率（INFPZ），即INF3DPT(x,y)≤INFPZ。

（5）每克价格（PG）。成本以每克价格表示，3D 打印任务实际所需的每克价格（PG3DPT(x,y)）应大于或等于3D 打印服务提供商提供的每克价格（PGPZ），即PG3DPT(x,y)≥PGPZ。

（6）模型体积（Vol）。打印的3D 模型的最大体积（Vol3DPT(x,y)）必须小于3D 打印机允许的3D打印量（VolPZ），即Vol3DPT(x,y)＜VolPZ。

（7）G 代码的路径长度。在CAM 阶段模型根据提交的层高被切开，然后转化为G 代码文件，G代码的路径长度将用于打印时间的计算。

（8）最后期限（DL）。需求者提交的最后期限（DL3DPT(x,y)）应小于等于服务提供者提供的交付时间，即

图2 所示为任务分配流程。当同时收到多个3D 打印任务时，首先由在线图着色算法根据用户预定的3D 打印任务的类别或等级自动生成的优先级进行排列，对于具有相同优先级的多个3D 打印任务将依据其最后期限（DL3DP(x,y)）进行升序排列。然后对优先级高的3D 打印任务进行分配，每个打印机的工作时间总和大于或等于工作时间阈值，同时打印材料、打印精度、喷嘴直径、填充百分比、每克价格、模型体积等打印属性满足条件时，计算所有3D 打印工作时间的总和，并与其工作时间最后期限（DL3DP(x,y)）进行比较，若，则离开打印列表，其状态改为零，否则该打印机仍在列表中，其状态保持不变。最后，就绪的3D 打印列表根据它们的能效功耗比（PPWPZ）降序排列，从而重新着色，更新3D 打印列表。

图2 任务分配流程

1.2.2 任务调度

基于优先级的自适应实时多任务调度算法能够保证每个3D 打印任务根据其提交的优先级进行及时调度，以便准确地满足每个任务的最后期限。

（1）任务优先级。当请求者指定或选择已提交3D 打印任务类别时，自动生成一个任务优先级。3D 打印任务的类别为[1,5]，其中1 代表最低的优先级，5 代表最高的优先级，每个类别都有一个预定的优先级，若是非关联零部件，需求者为每个3D 打印任务单独指定一个不同的类别；若是关联的零部件，则为整个提交的3D 打印任务指定为同一个类别。式（1）给出了在打印机Z上执行的成功分配的3D 打印任务的队列，相关的优先级向量（βP(Z)）显示在式（2）中。

式（2）中，当具有相同优先级和相同到达时间的3D 打印任务分配和调度在同一个3D 打印机（即打印机Z）上执行时，这些3D 打印任务将根据它们的最后期限升序排列在打印机PZ中。

（2）到达时间（a3DPT）。根据到达率λ由式（3）可以依次产生不同3D 打印任务的到达时间。

式中：a3DPT是一个当前3D 打印任务的到达时间；a3DPT-1是其前一个3D 打印任务的到达时间；是一个高斯随机数，其中λ是到达率，其平均值为，方差为 σ2。

如图3 所示，在任务调度阶段，首先确定优先次序，判断同一时间（Ti）到达的3D 打印任务数是否大于等于2，若成立，则按优先级顺序降序排列，对于相同优先权的3D 打印任务需要根据他们预设的最后期限升序排列。然后由多任务调度算法计算开始时间、执行时间、完成时间，将这些计算出的时间与接收该3D 打印任务的提交期限进行比较，来检查这个3D 打印机是否满足工作最后期限，是否有足够的时间来执行这个3D 打印任务。如果这些时间限制中存在任何一个不匹配，那么子列表中的第二个3D 打印机就会进入调度阶段，重复进行所有计算和比较，否则这个3D 打印机将当前3D 打印任务执行完毕，同时在队列中的第二个3D打印任务进入分配和调度阶段之前，可用的3D 打印的列表被更新。

图3 确定ARMPS 算法优先次序

2 性能评价

使用Matlab2021 进行仿真模拟实验，研究 3D打印数量、到达率等参数发生改变时对系统架构性能及分配和调度算法的影响，实现对系统的架构，以及 3D 打印任务的分配和调度算法的评估。

（1）3D 打印任务的数量（3DPTs）

在高负载情况下通过仿真模拟对架构的性能进行测试，3D 打印任务的数量从5 个任务增加到300 个任务。

（2）到达率（λ）

将3D 打印机的数量设定为50 台，改变到达率λ的值，将λ=0.25 逐渐增加到λ=16。默认值为：ρ=0.9，α=0.4，λ=0.25。文中所有图表都绘制了每个模拟实验在5 次运行中获得的平均数值。本研究中的性能指标包括成功率、平均响应率和系统获得的总价值。

成功率：成功分配的3D 打印任务数量与所有提交的3DPT 的数量之比。

平均响应速度：3D 打印任务从到达时间到成功分配给3D 打印机的时长。

系统获得的总价值：到截止时间成功分配的3D 打印任务的总价值与所有提交的3D 打印任务的总价值的比率。

此外，在仿真模拟中使用同一组数据集对本文提出的架构分别使用多任务调度算法与3D 打印服务调度的改进遗传算法[21]、粒子群优化（PSO）、模式搜索（PS）等调度算法进行对比，验证所提出的架构的稳健性。

2.1 3D 打印任务数量

如图4 所示，随着3D 打印任务数量从5 增加到300，响应速度逐渐增加，在300 个3D 打印任务高负荷的试验中，每个任务的平均响应速度达到1.60 min。

图4 3DPTs 的数量增加对平均响应速度的影响

图5 所示为4 种不同的调度方法对每个3D 打印任务的平均响应速度的对比。将本文所提架构的参数ρ=0.9、α=0.4、λ=0.25 设置为默认值，3D 打印数量限制在最多80 个。由图5 可知，本文所提架构采用多任务调度算法较其他三种调度方法平均响应速度明显提高。

图5 调度方法ARMPS、改进遗传算法、粒子群优化、模式搜索对每个3D 打印任务的平均响应速度

如图6 所示，在ρ=0.9、α=0.4、λ=0.25 为默认值时，3D 打印任务数量增加到100 时，成功率仍然是100%。当3D 打印任务数量接近200 个时，成功率略有下降，增加到300 个任务时成功率为97.6%。

图6 改变3DPT 的数量对本架构的成功率影响

2.2 到达率

图7 给出了当默认值ρ=0.9、α=0.4、λ=0.25 时，通过改变到达率和3D 打印任务数量对平均响应速度的影响。在300 个3D 打印任务数量试验中，通过增加到达率可以提高每个3D 打印数量的平均响应速度，在λ=0.25 时平均响应速度是1.40 min，在λ=16 时平均响应速度达到1.65 min。

图7 到达率和3D 打印数量对平均响应速度影响

从图8 中可以看出增加到达率几乎不影响成功率。结合图4、图6 至图8 可以看出，当设置ρ=0.9、α=0.4 达到负载平衡。本文所提出的架构在高负载情况下，特别是3D 打印任务以极快的方式连续到达时，能够明显地应对高度动态的3D 打印任务的演变情况，这些结果证明了所提出架构的稳健性和可扩展性。

图8 到达率和3D 打印数量对本框架的成功率影响

2.3 负载平衡

如图9 所示，在300 个3D 打印任务的试验中，默认值ρ=0.9、α=0.4、λ=0.25 时平均响应速度为1.65 min，而无负载平衡的情况下，同样λ=0.25 平均响应速度为1.42 min，由此可见，应用负载平衡算法增加了平均响应速度。

图9 应用负载平衡算法对平均响应速度的影响

应用负载平衡算法的主要目的是避免某些3D打印机负载不足和过载，确保3D 打印任务在3D打印机上均匀分布。由图10 可见，设置默认值ρ=0.9、α=0.4、λ=0.25，应用工作负载平衡算法改善了3D 打印任务在可用3D 打印机上的分布，从而使停止状态3D 打印机的数量比例大大降低。因此，本文所提的负载平衡算法能减少能源消耗并提高资源利用率。

图10 应用负载平衡算法前后不工作的打印机数量之间对比

此外，本文架构中采用PPW 优先考虑最节能的可用3D 打印机，减少使用甚至关闭效率较低的3D 打印机，不仅可以促进节能，而且可以防止某些3D 打印机的过载或欠载，加强经济和生态的可持续性。

2.4 鲁棒性

将3D 打印机的数量设定为50 台，ρ=0.9、α=0.4、λ=1 为默认值，改变3D 打印任务数量和到达率的值，3D 打印任务数量由10 逐渐增加到100，然后再剧增到500，如图11 所示，当λ=1 和λ=30 时，打印任务数量为100 时，对应的平均响应速度分别是1.0 min 和1.15 min；打印任务数量为500时，对应平均响应速度是3.7 min 和3.9 min。由此可见，在打印机数量一定的情况下，3D 打印任务数量的从100 剧增到500，平均响应速度有所降低，λ的变化对平均响应速度影响不大。

图11 3D 打印任务数量剧增平均响应速度变化情况

默认值ρ=0.9、α=0.4，当λ=30 时，打印任务数量为100 和500 时，对应的成功率分别为99.0%和95.2%，可见在3D 打印任务数量剧增成功率下降不大，如图12 所示。在相同数量的3D 打印任务条件下，到达率的增加几乎不影响成功率。

图12 3D 打印任务数量剧增成功率变化情况

综合图11 和图12，在3D 打印机数量不变和3D 打印任务的数量剧增的情况下，任务调度和分配的算法具有持续正确处理数据的能力，本框架具有稳健性，算法具有鲁棒性。

2.5 获得的系统总价值

图13 显示了所提出的架构使用EDF 调度算法与ARMPS 算法获得的总价值比较。由图13 可知，本文架构中ARMPS 算法获得的总价值高于采用EDF 算法时获得的总价值。EDF 算法是根据截止时间给3D 打印任务分配优先权，不考虑其重要性。而ARMPS 算法相反，它根据3D 打印任务的重要性分配优先权，根据3D 打印任务的重要性分配优先级的过程模拟了工业4.0 的真实场景。

图13 EDF 算法与ARMPS 算法进行任务调度系统获得的总值的对比

3 结语

本文提出了一个用于IIoT 中个性化3D 打印的实时绿色感知多任务调度架构，该架构由分配和调度两个相互联系的部分组成；提出了一种基于图形着色的在线算法，以完全符合用户自定义属性的方式充分分配3D 打印任务。此外，还开发了一种基于优先级的自适应实时多任务调度算法来满足3D打印任务的动态性和实时性要求，平衡了IIoT 中分布式3D 打印之间的工作负载，同时提高了资源利用率。在高负载环境中，通过性能评估测试证明所提出的架构是稳健的、可扩展的。