打印参数可变模式下3D打印批调度问题研究

王 彬 唐 昊 戴 飞 谭 琦

(1.合肥工业大学电气与自动化工程学院,安徽合肥 230009;2.工业自动化安徽省工程技术研究中心,安徽合肥 230009)

1 引言

3D打印技术被称为“具有工业革命意义的制造技术”,是制造领域中一项正在飞速发展的新兴制造技术.采用3D打印技术进行生产的主要流程是:应用3D模型设计软件设计出打印件的立体模型,然后通过3D打印设备,用液化、粉末化、丝化的打印材料逐层堆积“打印”出打印件[1].随着网络技术与先进制造技术结合得越来越紧密,一种通过物联网将3D打印设备接入制造网络,接收客户设计的3D打印件模型进行打印的网络化制造系统被提出[2],并在实际生产中开始广泛应用.但现阶段3D打印产业处于发展阶段,设备资源比较短缺,因此,针对这种打印任务随机的3D打印服务系统,如何提高系统的处理率是急需解决的问题.

针对该问题,已有学者为了减少设备预热时间、工作台调整时间和打印完成后设备冷却时间[3],研究了3D打印批次规划问题[4].该问题可归类为工件尺寸不同的单机批调度问题,对该问题的相关研究成果较多.例如,Ikura等人首先提出单机单工件簇的批处理优化控制问题[5].Lee等进一步研究了多工件簇的单机批处理优化问题[6],且已有学者提出采用微粒群算法和改进蚁群算法可对问题进行求解[7–8].同时根据各批次加工时间与批中工件的关系,该类批调度问题可分为3类,第1类假定各批次加工时间与批中工件无关[9];第2类假定各批次加工时间取决于批中最大工件[10];第3类则假定各批次的加工时间为批中工件的加工时间之和[11].由于3D打印过程中扫描填充时间与所选批中打印件的总体积成正比,而层间调整所需时间取决于批中最高打印件的高度,因此本文研究的问题属于第2类和第3类的结合.由于打印任务随机到达,因此本文研究的问题也属于在线批调度优化问题[12–14].

上述研究主要是对任务进行调度以提高系统的处理率.除了对任务进行调度外,还可通过改变服务率提高系统性能.例如在单站点传送带给料生产加工站(conveyor-serviced production station,CSPS)系统的优化控制问题中,将服务率作为系统的一个控制变量,求解系统的最优控制策略[15].有学者进一步研究了顾客需求随机到达和服务率可动态实时变化的情况,将系统的最优控制问题建成半马尔科夫决策过程(semi-Markov decision process,SMDP)模型,采用策略迭代算法和Q学习算法求解了系统的最优控制策略,提高了系统的生产率[16].通过以上研究可知,通过动态设定打印参数,调整打印速度,以提高系统的处理率[14].

因此,本文研究在打印任务随机到达情况下,如何根据任务到达情况动态选择任务组合以及设置打印参数,以提高系统的处理率.由于对打印速度影响最大的是切片参数层高[17–18],因此本文选择打印参数层高作为控制变量.虽然层高设置的得越大,打印速度越快,但打印出的产品质量会降低[19],如何减少打印质量损失,也是本文需要考虑的问题.本文根据系统工作模式和决策过程的特点,以各个任务队列长度作为系统联合状态,以任务组合以及打印参数层高作为系统的联合控制变量,以提高生产率、减少打印质量损失、节约电能为综合目标,将该问题描述为SMDP模型,采用策略迭代及Q学习算法对系统的最优策略进行求解.

2 系统组成及决策过程

如图1所示,本文研究的对象是一种3D打印服务系统,主要由存储打印任务的任务队列以及单台3D打印设备组成.打印任务由不同种类的3D打印件模型组成,各类打印任务按照独立的泊松过程随机到达,并自动存储在相应的任务队列中,任务队列容量有限.3D 打印设备以工作台作为其打印区间.系统运行时,根据任务队列中的任务数量,选择进行打印的任务组合,并设置打印参数层高,然后对所选任务组合进行切片处理,再由3D打印设备逐层累积打印,直至打印完成.因此,系统需要根据任务队列中的任务数量对进行打印的任务组合和打印参数层高进行决策,在此定义系统的决策时刻为打印完成时刻或打印任务到达时刻,其典型决策过程如下:在决策时刻,系统根据当前任务队列中的任务数量,选择由各类打印任务组成的任务组合并设置打印参数层高.若所选组合不包含打印任务,则不进行打印操作,等待下一任务到达,以进行下次任务组合选择.当有任务到达时,系统进入下一决策时刻;若所选组合包含打印任务,则从各个任务队列中选取相应个数的任务,按照所选打印参数层高进行打印,打印过程结束时,系统进入下一决策时刻.本文主要研究如何根据任务到达情况动态选择任务组合和层高,以提高系统和系统的生产性能.

图1 系统的示意图Fig.1 Physical model of the system

本文的研究主要基于以下假设:

1) 打印任务服从不同参数的泊松过程随机到达并且相互独立,打印件所需的打印材料相同;

2) 忽略打印过程中的热量散失,喷头在预热和打印时加热功率相同且恒定;

3) 忽略在打印同一层时喷头的空行时间;

4) 喷丝截面为矩形,且忽略由于切片误差产生的打印材料消耗以及打印时间消耗;

5) 工作台每次调整的时间相同.

为了方便地进行数学描述以及进行数学建模,本文定义了系统的参数和变量,如表1所示.本文研究的系统由M种打印任务、M个任务队列以及一台单喷头的3D打印设备组成.这M种打印任务分别代表M种待打印的3D打印件模型,并按照独立的泊松分布随机到达,记第m种打印任务的到达率为λm,这M种打印任务分别存储在M个任务队列中,第m个任务队列用于存储第m种打印任务,其队列容量为Cm.3D打印件模型的种类根据底面尺寸om、体积qm和高度hm来区分.本文将3D打印件模型的水平投影轮廓最小包络矩形作为底面尺寸,记第m种3D打印件模型的底面尺寸为omnm,Length×nm,Width,记其水平投影轮廓最小包络矩形的长和宽分别为nm,Length和nm,Width.一般3D打印设备的工作台为矩形区域,本文将3D打印设备的工作台作为打印设备的打印区域,定义NLength和NWidth为工作台的长和宽.本文以任务m的队列长度cm作为任务队列的状态,其状态空间为

表1 符号变量表Table 1 Variable table

现以M个任务队列的状态作为系统的联合状态,记为Sn(c1,···,cm,···,cM),其状态空间为

定义在系统状态S下采取的行动为vS(JS,hS),其中JS为选择的任务组合,

jm表示所选任务组合中第m种打印任务的个数,所选任务组合中各类打印任务的数量不超过队列长度,即jm≤cm≤Cm.hS为设置的打印参数层高,其取值范围为Hmin≤hS≤Hmax.DJS为系统在状态S下的可选打印件组合的集合.由于多打印任务同时打印时需要将打印任务布排到工作台上,在已知工作台尺寸以及打印件水平投影的最小包络矩形条件下,该问题属于矩形件排样问题.在指定空间布排矩形的方法有多种,可根据问题的不同采用不同的方法.对于复杂的排样问题可采用多启发式算法、粒子群算法等算法[20],对于简单的排样问题可采用Bottom–Left规则[21].因此本文根据具体排样问题选择合适的算法求解得到系统在状态S下的可选任务组合的集合定义系统平稳策略为

优化目标是找到一个最优策略使3D打印服务系统在长时间运行情况下代价最小.

系统状态S随时间随机跳变,记t时刻的状态为St,第n次决策时刻记为Tn,在决策时刻Tn时系统状态为简记为Sn.在决策时刻Tn,系统所选任务组合和层高设置作为决策行动.若0,则不进行打印操作,等待下一任务到达,记决策过程中等待下一任务到达的时间为ϖn,ϖn服从指数分布.当有任务到达时,系统进入下一决策时刻,记为Tn+1,满足Tn+1Tn+ϖn,若到达的是第m类打印任务,则系统转移到下一状态Sn+1(c1,···,···,cM),其中min{cm+1,Cm};若0,则执行打印操作,记打印过程所需的时间为确定.在打印过程中,将第m种打印任务到达的个数记为bm,则系统转移到下一状态

3 系统的半马尔科夫决策过程模型及优化算法

3.1 系统的半马尔科夫决策过程模型

由系统决策过程可知,系统状态跳变只与当前状态有关,与历史状态无关,因此在一次样本轨道仿真决策过程中产生的状态序列{S1,S2,···,Sn,···}是一个嵌入式马尔科夫链.此外由于系统打印过程所需时间为确定值,不服从指数分布,因此系统决策过程是连续时间半马尔科夫过程[22].除状态空间和行动集外,系统的SMDP模型还包括逗留时间分布矩阵Fv(t)、状态转移矩阵Pv以及性能函数矩阵Rv,下面将分别进行分析.

3.1.1 系统逗留时间分布矩阵

首先,定义在策略v下系统逗留时间分布矩阵为

在决策时刻Tn,系统在状态Sn下选择行动若则进行等待操作,等待下一任务到达,决策周期为等待下一任务到达的等待时间ϖntwait,系统转移到下一状态Sn+1,此时状态逗留时间分布如下:

λ为M种任务到达率之和.

图2 打印操作时间轴Fig.2 Timeline of printing operation

接下来文中给出预热时间theat、扫描填充时间tprint冷却时间tcool和打印过程所需时间τ的具体计算过程.

3D打印机在打印前需要对工作台以及喷头等部件进行加热,已有技术实现喷头在较短的时间内加热到设置温度,且基本实现无超调[23],因此本文认为预热时间theat为固定值.

由于打印时喷头需要对每层截面扫描填充,扫描填充完一层后,工作台需要向下调整,然后对下一层进行扫描填充,因此扫描打印时间tprint由喷头扫描填充时间tscan与工作台调整时间组成,喷头扫描填充时间tscan与打印件的体积成正比,工作台调整时间取决于工作台的移动次数.多打印件打印时喷头扫描填充时间tscan等于各打印件的扫描填充时间之和,工作台调整时间取决于最高打印件的高度.喷头扫描填充时间tscan在忽略切片产生的填充体积误差时,可根据扫描路径宽度d、参数层高、喷头的扫描速度ascan以及打印件的总体积求出,计算式如下:

其中:Q[q1··· qm ··· qM]为M种打印件的体积向量.

记所选打印件组合中最高打印件的高度为hmax,hmaxmax{hm|jm0且jm ∈JSn},则扫描打印时间tprint(vSn)计算公式如下:

上式中「·」为向上取整函数.

3D打印机完成逐层扫描填充后,需要等待机器冷却后将打印件取出,记这段时间为冷却时间tcool,本文采用固定值.

综上可知,在决策时刻Tn,系统在状态Sn下选择的行动若则进行打印操作,系统转移到下一状态.在此过程中系统状态逗留时间分布为

3.1.2 状态转移矩阵

定义在策略v下系统的嵌入链转移矩阵为Pv其中表示在状态Sn采取行动,转移到下一状态Sn+1的概率.执行打印操作时,在t时间内,任务队列m由状态cm转移到的概率为

当执行等待操作时,到达的为第m种任务的概率为,系统下一状态为

若cmCm,则Sn+1Sn,当存在任务队列为满时,系统转移到相同状态的概率为

其中:λfull为状态Sn中所有为满队列对应任务的到达率之和,Bfull为状态Sn中所有为满队列对应的任务种类的集合.

3.1.3 性能函数矩阵

本文通过SMDP模型描述3D打印批调度问题,其优化目标是找到一个最优策略使系统在无穷时段下的单位时间代价最小.

首先,由于系统采取不同行动时会产生不同代价,因此定义R(Sn,vSn,Sn+1)为系统在决策时刻Tn采取行动vSn并转移到下一决策时刻Tn+1过程中的单位时间期望代价函数,则性能函数矩阵为

系统的优化目标函数为[22]

系统在执行打印操作或等待操作会产生多类代价,例如任务队列中打印任务的等待代价,打印材料损耗代价,电能损耗代价等,下面将具体分析R(Sn,vSn,Sn+1)的计算.

首先,打印任务在任务队列等待时需要占用一定的存储空间,同时任务等待时间会影响任务的交货时间,因此定义第m种任务等待时单位时间等待代价为k1,m.

其次,3D打印过程需消耗电能,因此定义电能单价为k2.打印设备在打印过程中能量损耗主要用于喷头加热用于融化打印材料,则在忽略热量散失及其他加热装置的条件下,喷头的加热功率g近似等于单位时间融化材料所需的热能,与参数层高h成正比.在参数层高为h时,单位时间打印材料挤出量为dhascanρ,其中d为扫描路径宽度,ascan为喷头的扫描速度,ρ为打印材料的密度.则打印材料由环境温度θenvir加热到打印材料的融化温度θmelt所需的热量为dhascanρδ×(θmelt−θenvir),δ为打印材料的比热容,则选择行动时,打印设备的加热功率为

另外,打印过程中需要消耗打印材料,因此定义材料单价为k3.进行打印行动时,所需的打印材料与选择打印的打印件组合的总体积成正比,则选择打印的打印件组合时消耗的打印材料质量计算式如下:

此外,系统打印完产品会获得报酬,由于层高参数h影响产品质量,因此本文根据产品质量决定产品的打印报酬,根据文献[19]的研究结果可知,打印产品的磨损强度与层高参数h函数关系近似拟合为

式中:ξ2,ξ1,ξ0为各项系数,在此定义打印报酬由固定报酬以及浮动报酬这两部分组成,其中浮动报酬与打印质量成正比,定义打印第m类任务的报酬rm与层高参数关系为

其中:ϑm为打印第m类任务的奖励报酬系数,ϑm,fix为打印第m类任务获得的固定报酬.则采取行动获得的报酬为

因此,系统执行打印操作时,单位时间期望代价为

其中φ1(Sn,Sn+1)为电能代价在整个时间段上的折扣,计算式为

φ3(Sn,,Sn+1)为打印立即报酬在整个时间段上的折扣,计算如下:

与打印操作不同,执行等待操作时只存在等待代价,此时系统单位时间期望代价为

3.2 优化算法

本文的优化目标就是找到一个最优策略v∗,使系统在折扣均准则或平均准则下的无穷时段的单位时间代价最小.在此本文给出策略迭代和Q学习这两种算法求解系统最优策略.

尽管策略迭代算法可以求出系统最优解,但是需要求解系统矩阵,并进行矩阵求逆,当系统参数例如到达率未知,或状态庞大造成维数灾使矩阵运算计算困难时,最优制策略无法求解或求解十分困难.因此,可用Q学习算法进行求解.

Q学习算法的主要步骤分为如下几个过程:首先采用矩形排样方法得到打印件组合行动集DJ,然后将层高h取值范围用一个很小的常数Δh离散化,得到一个离散的紧致行动集Dh,通过组合得到系统行动集.在每次决策过程中,通过观测得到一个样本数据,ωn为第n个决策时刻与第n+1个决策时刻的时间间隔,则平均准则和折扣准则下统一差分计算式为

其中:Qα(·,·)是在折扣因子α下的状态–行动对的值,R′(Sn,Sn+1)表示在第n个决策时刻系统在状态Sn下,采取行动转移到状态Sn+1过程中产生的累计折扣代价.具体代价计算如下:当进行等待操作时

当进行打印操作时

此外,ηn是平均代价的当前估计值,可根据样本轨道直接计算.则Qα(·,·)更新式如下:

其中γ(Sn,vSn)为学习步长.本文介绍的Q学习算法具体步骤已在文献[26]中经进行了详细介绍,在此不再详述.

4 仿真结果

本文根据实验室中的3D打印设备的参数对系统的物理参数进行设置,具体参数设置如表2所示.同时设置了仿真参数如表3所示.根据仿真实验给出的3D打印机和打印件的尺寸可知,本文给出的排样问题属于简单排样问题,因此本文选择Bottom–Left规则对打印任务进行布排[4],按照此规则求解系统可行打印件组合集合为

表2 物理参数表Table 2 Physical parameters

表3 仿真参数表Table 3 Simulation parameters

仿真实验首先介绍了策略迭代算法和Q学习算法在折扣和平均准则下的优化过程,图3为在平均和折扣准则下采用策略迭代算法和Q学习算法的系统优化的优化曲线,此时折扣因子α0.01.由图3可知,平均和折扣准则下采用策略迭代算法对系统进行优化,在第2步或第3步就已经收敛,得到系统的最优策略.在平均准则下采用Q学习算法的优化曲线,每学3000步评估一次,由图可知曲线在第100次评估时算法基本稳定.与策略迭代算法相比,Q学习算法的收敛步数更大.

通过图3可以看出折扣准则下的优化曲线是相互分离的,在不同状态下系统的代价不同.这里定义3个特殊状态.状态1:任务队列全为空.状态14:队列1长度为0,队列2长度为2,队列3长度为3.状态60:任务队列全为满.在状态1任务队列全为空时,由于没有进行打印,因此没有打印报酬,所以代价曲线在最上方.在状态14时队列1长度为0,队列2长度为2,队列3长度为3,此时可以组合成两个最优的打印件组合进行打印,因此获得较高的打印报酬.在状态60时,任务队列全为满,此时等待代价变大,同时由于系统对任务1的处理效率不高,所以代价曲线在状态14的代价曲线的上方.由策略迭代求解的最优策略可知,在状态14时,系统选择的打印件组合J(0,2,0),参数层高h0.1739,在状态60时,系统选择的打印件组合J(0,2,0),层高参数h0.2415,这表明当任务队列为满时,系统选择最优的打印件组合进行打印,层高参数设置较大,与实际情况相符合.

图3 平均和折扣准则下两种算法的优化曲线Fig.3 Optimization curves of two algorithms under average and discount criteria

为了进一步分析两种算法的特点,仿真实验给出了两种算法的运行时间以及优化后系统的平均代价、打印任务的处理率和产品的平均质量,其中策略迭代算法的结果为3996 s,−2.485,0.977,0.0328,而Q学习算法的运行时间以及优化后系统的平均代价、打印任务的处理率和平均质量分别为1222 s,−2.448,0.972,0.0327.同时为了对Q学习算法的结果进行方差分析,在实验中对Q 学习算法进行5次独立试验取均值并统计各项数据的标准差,对应每项的标准差分别为32 s,0.003,0.0019,0.000103,分析各项标准差可知Q学习算法比较稳定.本文还对两种算法的复杂度进行了对比分析,首先比较空间复杂度,根据实验部分设置的系统参数求得系统状态数为3×4×560,策略迭代算法需要存储逗留时间分布矩阵、状态转移矩阵以及性能函数矩阵,由于这3个矩阵维度和系统状态数相同,且都是方阵,所需存储空间为3×60×6010800.而Q学习需要存储每个状态–行动对的值,所需存储空间为

两种存储空间相同.在迭代步数方面,策略迭代算法在第3步就已经收敛,而Q学习算法在第100次评估时算法基本稳定.在运行时间方面,策略迭代算法运行时间为3996 s,然而Q学习算法运行时间为1222 s.通过上述结果可知,虽然策略迭代算法收敛速度较快,但运行时间更长,这是由于策略迭代算法需要进行矩阵求逆运算,所以算法运行时间长.Q学习算法运行速度快,当模型参数未知时,可采用Q学习算法进行求解.本文接下来对3D打印服务系统的性能分析,将依据策略迭代算法的求解结果.

本文研究的系统作为一种排队服务系统,通过设置合理的任务队列容量,可以提高系统性能.为了探究任务队列容量与系统性能之间的关系,本次实验同时比较了3个队列的容量变化对系统性能的影响,在此次实验中假设λ10.2,λ20.3,λ30.5,实验结果如图4所示.根据实验结果可知,任务队列1容量增大时,系统代价会有所上升,任务队列1容量增大到2以后,系统代价也有所上升,随着任务队列2和任务队列3的容量分别增大到2和3时,系统的平均代价逐渐收敛,这是由于两个第2种打印件和三个第3种打印件分别组成两种等高且完全占满工作台的打印件组合.处理这种能够占满工作台且等高的打印件组合,可以节省打印所花时间,提高系统的处理率.

图4 不同队列容量下的平均代价Fig.4 Average cost under different queue capacities

本文同时研究了队列容量变化对不同打印任务的处理率影响,如表4所示.由表4可知当某一种打印任务的任务队列容量增大时,对应种类打印任务的处理率有较大幅度的提高,当队列容量增大到一定值后打印任务的处理率基本不变.随着某一任务队列容量的增大,其他种类打印任务的处理率会小幅度下降,这是由于该种队列容量增大时,其接收对应种类任务的容量越大,当其处理速度不及打印任务到达速度时,任务产生堆积.同时由于任务等待代价随着队列长度增加而增加,因此会优先处理队列长度长的任务,其他打印任务的处理率会有所降低.

表4 不同队列容量下系统处理率Table 4 System processing rate under different queue capacities

上面仿真实验研究了在任务到达率固定时队列容量对系统性能的影响,但是在实际系统中,任务到达率是变化的,因此本次仿真实验探究了任务到达率与系统性能之间的关系.图5为不同到达率下系统的平均报酬,在本次仿真实验中的队列容量设置为C12,C23,C34.由图可知随着任务到达率的增加,系统的平均报酬增大,这是由于在系统打印能力之内,到达率越大,系统单位时间打印的打印件越多,获得的报酬越大.

图5 不同到达率下的平均报酬Fig.5 Average reward under different arrival rates

本次仿真实验还研究了在不同任务到达率下按照先到先服务(first-come-first-served,FCFS)规则、打印参数固定模式和打印参数可变模式这3种模式下系统的处理率和产品平均质量,如表5所示.随着任务到达率增大,系统的处理率和产品质量随之降低.但与FCFS规则和参数固定模式下系统性能相比,参数可变模式下系统的处理率下降比较缓慢.这是由于任务到达率较小时,参数可变模式下系统为了获得较高的打印报酬,将打印参数层高设置得较小,提高了产品质量.随着打印任务到达率增大,任务队列中会堆积较多的打印任务,参数可变模式下的系统为了提高处理速度,将打印参数层高设置得较大,加快了打印任务的处理速度,因此能够及时处理到达的打印任务,打印任务的流失率小.通过比较可知,在任务到达率为[0.2 0.3 0.1]时,3种情况下系统的处理率十分接近,都在99%左右,但在参数可变模式下系统的产品的平均质量与在其他两种模式下系统产品质量相比提高了4.3%.在任务到达率为[0.5 0.3 0.5]时,参数可变模式下系统处理率比FCFS规则下系统的处理率高出6.6%.根据仿真实验结果可知,参数可变模式下系统对任务到达率变化的适应性更强,当到达率较小或较大时,通过动态设置打印参数调整打印任务处理速度,提高系统的处理率.

表5 不同到达率下系统处理率和产品平均质量Table 5 System processing rate and average product quality under different arrival rates

5 总结

本文研究了在打印任务随机到达情况下,如何根据任务到达情况动态选择任务组合和层高的问题,并将优化问题描述为SMDP模型,采用策略迭代算法和Q学习算法这两种优化算法求解了系统的最优调度策略.仿真实验结果表明所求调度策略可以提高系统的处理率.本文目前只考虑了简单的排布问题以及单3D打印设备,如何将复杂排样问题纳入到整个优化问题中,以及如何对多台3D打印设备进行资源优化,是未来值得研究的问题.