基于深度学习的资源投入问题算法

陆志强，任逸飞，许则鑫

(同济大学 机械与能源工程学院，上海 201804)

0 引言

为了满足市场订单需求，降低飞机生产装配成本，目前国际大型飞机制造公司摒弃传统的固定站位式飞机装配模式，吸取丰田汽车流水生产线理念和精益生产理论，对飞机总装生产线进行流程再造，设计了全新的飞机移动生产线装配模式。从而大大缩短了飞机总装时间，降低了飞机制造成本，提高了装配质量，可按需连续生产。装配线上的飞机以稳定的速度平稳地通过所有工位，从而完成整个装配过程。每个工位都存在空间容量限制，并包含不同种类和数量的作业，而每个作业均有固定的执行时间和所需资源种类和数量，同时不同作业间包含特定的时序约束。基于上述生产背景，任一单架飞机的总装作业装配过程在本质上是一类具有复杂约束的大规模单项目调度问题，同时涵盖了具有正则目标的资源受限项目调度问题(Resource Constrained Project Scheduling Problem, RCPSP)及与之关联的资源投入问题(Resource Investment Problem, RIP)[1]。本文以RIP为研究对象，即在保证给定生产工期条件下，满足作业时序约束等，引入单位资源成本系数，通过合理分配各类资源和决策各个作业的调度时间，达到项目资源投入总成本最小的目的。

MÖHRING[2]首先提出了RIP，证明该问题为NP-hard(nondeterministic polynomial)问题，并通过包含16个作业的算例验证了其所设计的图解精确算法求解RIP的有效性；RODRIGUES等[3]针对RIP设计了一种改进的分支定界算法，减少了解空间，提高了算法的效率。由于精确算法无法求解大规模问题，许多学者通过研究RIP特性，结合求解RCPSP算法思路，设计了不同的启发式和元启发式算法进行求解。ZHU等[4]将RIP拆分成排序问题和资源决策问题两个子问题求解，并提出一个多开始迭代搜索启发式算法。SHADROKH等[5]采用对资源容量和作业列表编码的双链表编码方式的遗传算法求解延迟惩罚成本的RIP。NAJAFI等[6]设计了一种遗传算法求解RIP，并详细介绍了通过实验设计和响应曲面法调整遗传算法参数；AFSHAR-NADJAFI[7]考虑了资源需要招募和释放的多模式RIP，提出了以作业浮动时间为编码的模拟退火方法；JAVANMARD等[8]针对资源多技能的RIP设计了一种基于遗传和粒子群的算法，该算法能够校准参数和染色体结构，保证解的可行性。上述文献所提到求解RIP的算法均采用对资源量搜索的方式，求解在不同资源量下对应的RCPSP。然而现有算法所设计的资源上下界差距较大，使得搜索空间大，搜索效率低，极易产生不可行的资源组合。同时RCPSP本身也是NP-hard问题，现有搜索算法求解时间较长，中大规模算例的解与最优解有一定偏差，从而会错过最优资源组合。RANJBAR等[9]对作业序列编码并通过路径重连和遗传算法直接求解RIP，但是该算法会产生大量不可行解，需要对优先级不可行的活动列表进行调整；任逸飞等[10]提出了基于全局作业影响的改进调度机制的遗传算法，通过基于全局资源水平影响的作业调度评估策略优化非关键作业的调度位置，然而该评估策略在求解大规模算例时效率较低，求解时间较长。

飞机移动生产线调度问题，由于现场环境复杂多变，而传统的搜索算法由于其容易陷入局部最优以及算法本身搜索时间较长成本较高而不能满足现场需求[11]。结合优先级规则的启发式调度算法具有较低的时间复杂度，能够快速做出调度计划。然而在大量文献[11-15]研究优先级规则过程中得出一个被广泛认同的结论：单个同一种规则并不能在所有算例中都比其他规则具有最优性[13-15]，混合组合多种规则比单一规则的求解效果好[11-12]。现有算法在选择调度规则时的缺点是根据调度系统稳态行为进行选择[16]，当系统状态发生变化时，算法并不能根据系统状态的变化作出对应调整，进而改变调度规则的选择。因此，需要人工或专家系统进行调整[11]，但是其不足之处在于需要丰富的调度经验和知识，以及对调度环境具有较强适应性和高效的反应速度。针对上述算法的不足，本文提出通过机器学习方法对调度规则进行智能选择。机器学习通过计算机或智能系统模拟人类的学习行为自动获取知识和技能，重新组织已有的知识结构，并不断实现系统的自我完善。MOUELHI-CHIBANI等[16]通过神经网络根据当前系统状态为每台机器动态转化调度规则，实验结果优于静态使用调度规则；EL-BOURI等[17]在5台机器和3个调度规则的小规模算例实验下，通过神经网络为每台机器选择调度规则，实验结果证明该算法所得结果优于所有机器都使用同一种调度规则的结果；吴秀丽等[18]针对智能制造环境下的混合流水车间实时调度问题, 提出了基于BP神经网络的数据驱动的实时调度方法，并验证了所提方法在不同的调度性能指标下优于固定单一调度规则；曹琛祺等[19]对调度序列进行处理,将作业车间调度问题转化为一个分类问题，并使用人工神经网络构建分类器。对于调度实例,利用训练得到的分类器得出优先级,再利用优先级得到调度序列；SHOU[20]设计了一个前馈神经网络为资源受限项目调度问题选择合适的优先级规则，其中选择3个特征作为神经网络的输入端，输出端为9种优先级规则；ÖZKAN等[21]通过建立人工神经网络从3个优先级规则中选择最合适的规则分配到不同的算例中，使得项目完工时间最短。RIP作为传统RCPSP的拓展问题，是一种更为复杂的NP问题[22]。本文提出了基于深度学习的双层迭代循环搜索算法。算法上层为一种启发式资源搜索框架，通过资源搜索和调整机制逐步缩小资源搜索空间。同时，在满足上层资源搜索空间的基础上，设计了下层基于实时调度状态的调度优先级规则智能决策算法，并将调度结果反馈到算法上层，指导上层优化资源调整。

综上所述，本文在现有求解RIP算法的基础上提出了基于深度学习的调度规则智能分配算法。通过大量实验，选择12个特征作为系统输入特征，采用现阶段比较成熟的深度学习模型，通过从历史离线调度数据中学习隐含的匹配关系，实现在项目调度过程中的每一个阶段都能根据当前的调度状态动态智能地分配最优的调度规则，进而完成整个项目作业的调度计划。

1 问题描述及数学模型

数学模型中决策变量如下：

目标函数为：

(1)

模型约束为：

(2)

(3)

∀j∈J,∀t∈T;

(4)

(5)

xjt={0,1},∀j∈J,∀t∈T。

(6)

其中：式(1)表示目标函数即最小化资源投入成本；式(2)表示确保每一个作业在给定作业执行工期内完成；式(3)表示时序约束，即每一项作业在其所有紧前作业完成后才能开始；式(4)表示作业一旦开始就不可中断；式(5)表示项目中所有作业的结束时间都不超过给定项目工期上限；式(6)表示决策变量的可行域。

2 算法设计

现有文献提到的算法在选取调度优先级规则时，所选优先级规则贯穿整个调度过程中保持不变。但是，随着部分作业的调度完成，由于作业时序约束影响和资源使用情况的变化，现有算法并不能保证原有优先级规则在后续作业调度过程中是最优调度规则。针对现有算法缺乏预测性和前瞻性，本文设计了一种实时调度优先级规则智能决策机制。该策略思路是：对相关调度问题算例的详细历史调度数据进行离线学习，通过数据挖掘方法获取其中潜在的调度规则知识，建立当前调度状态与对应该状态下的最优调度优先级规则的映射知识网络，即构建了基于实时调度状态的调度优先级规则智能决策系统，能够根据获取的实时调度状态数据快速切换优先级规则，对每一个调度阶段进行最优的调度决策，从而实现整个调度过程的智能连续性调度。本文使用人工神经网络(Artificial Neural Network, ANN)作为智能决策系统的核心方法，通过BP(back propagation)神经网络进行调度规则知识的挖掘。

综上所述，针对资源投入问题，本文提出了基于ANN的双层迭代循环搜索算法(Artificial Neural Network-Iterative Loop, ANN-IL)。ANN-IL的双层迭代框架为上层是通过启发式方法得到可行的资源组合，下层为求解在上层算法输出结果为资源约束的RCPSP问题的算法，其迭代寻优机制为下层算法在上层算法输出结果基础上进行调度优化，并将调度结果反馈到上层作为其进一步优化依据，即算法下层为通过基于实时调度状态的调度优先级规则智能决策机制进行作业调度，并将调度结果反馈到算法上层，指导上层算法对资源组合进行调整。ANN-IL算法流程如图1所示。

2.1 启发式资源搜索框架

(7)

(8)

定义tESTj，tEFTj，tLSTj，tLFTj分别表示通过关键路径法得到的作业j的最早开始时间、最早结束时间、最晚开始时间和最晚结束时间；tASTj和tAFTj分别表示作业j在调度时的开始时间和结束时间。

资源调整机制：计算各个作业的延迟时间Δtj=|tESTj-tASTj|，选择max{Δtj,∀j∈J}对应作业j的资源需求量rjk更新rk，即rk=rk+rjk；验证更新后的rk是否可行，若rk不可行，重新计算Δtj，max{Δtj,∀j∈J}，更新资源rk=rk+rjk，依此类推直到rk可行；若rk可行，则完成资源调整机制。

ANN-IL算法上层启发式资源搜索框架具体步骤流程如下：

步骤2验证rk是否可行，若不可行，转步骤3；若可行则令k=1，转步骤4。

步骤3进行资源调整机制，更新rk=rk+rjk，转步骤2。

步骤4降低资源k一个单位量，即rk=rk-rjk，调用下层基于实时调度状态的调度优先级规则智能决策算法，得到Tc，转步骤5。

步骤6得到最终资源组合rk，求出目标函数值。

2.2 基于实时调度状态的调度优先级规则智能决策算法

基于ANN的双层迭代循环搜索算法中下层为基于实时调度状态的调度优先级规则智能决策算法，其机制架构如图2所示。该算法主要有离线训练模块和实时调度决策模块，离线训练模块包含训练样本构建、样本数据归一化处理和人工神经网络模型构建，实时调度决策模块包括调度优先级规则智能决策机制和作业调度过程。实时调度决策模块通过离线训练模块得到的学习模型在调度的每一阶段根据当前调度数据，智能决策调度优先级规则，并指导作业调度进行。

2.2.1 离线训练模块

在离线训练模块中，首要就是构建用于挖掘调度状态和调度规则间映射关系模型的训练数据，本文通过文献[24]所提算法，针对项目调度标准算例库(Project Scheduling Problem Library, PSPLIB)中算例求解，将求解的结果分为多阶段，每一阶段代表一个作业的调度。比如，当整个项目进行到阶段i时，可以获取项目在阶段i的状态参数Χi，其中Χi=(x1,x2,…,xn)，将该状态参数作为人工神经网络的输入层特征参数。同时，由于整个项目最终的最优结果已确定，从而可以得到该阶段下调对应的最优调度优先级规则Yi，其中Yi=(y1,…y2,…,ym)，并将此作为人工神经网络的输出端数据，因此(Χi,Yi)构成了离线训练数据样本。通过基于BP神经网络的学习机制对样本数据(Χi,Yi)进行知识挖掘，得到调度过程中每一阶段的调度状态与调度优先级规则的映射关系，并将其作为可供实时调度模块使用的调度决策机制，指导整个项目的调度过程。

(1)训练样本构建

训练样本数据(Χi,Yi)中调度状态数据Χi通过文献[24]所提算法求解所得。首先选择PSPLIB算例库中部分不同规模算例作为训练数据，通过参考算法得到算例的最终调度方案。然后根据所得调度方案确定作业调度顺序，每调度一个作业表示调度过程的一个阶段，根据调度方案确定该阶段下所定义的调度状态数据，即人工神经网络模型的输入端。调度状态特征选取时，需要综合考虑当前调度状态以及对后续调度状态的影响，使得选取的特征具有前瞻性和整体性。本文设置以下12个调度状态特征，如表1所示。

结合文献[20,21],选择以下8种优先级规则作为输出端Yi数据，如表2所示。

表1 实时调度状态特征表

续表1

表2 优先级规则集合表

(2)样本数据归一化处理

针对人工神经网络的各维度输入量Χi存在较大差异数量级问题，本文通过式(9)对样本输入数据进行归一化处理。

(9)

在训练神经网络时，对于输出数据Yi，在调度的每一阶段，令能够选取到该作业的优先级规则对应数值为1，未能选取到该作业的规则对应数值为0。在实时调度阶段，根据输入数据Χi，会生成在区间[0,1]内的输出数据Yi，选择最大数值对应的优先级规则为最终确定的调度规则。

(3)人工神经网络模型构建

本文中BP神经网络前三层以RLUE函数为激活函数，输出层以Sigmoid函数为激活函数，以网络的均方误差为目标函数。采用Adam算法[25]进行优化，以目标的负梯度方向对参数进行调整，不断地修正所有隐层和输出层神经元的权值和阈值，直到实现最好的优化目标，保存此时神经网络中的所有权重参数。

在训练模型中，对输入层而言，每个输入层的神经元对应一个项目调度状态值，输入层的神经元数目取决于项目调度状态的个数。输出层由对应的规则组成，由于对于不同的规则可能对应相同的调度结果，数据训练的输出为一组由0和1组成的向量，其中0表示该规则不是此状态下最优规则，1表示该规则在此状态下为最优规则。在预测模型中，输入层为实际调度中的状态特征通过标准化之后的向量。输出层为一组大小在[0,1]之间，长度为优先规则数量的小数向量。输出向量与调度规则一一对应，最大数对应的规则，则为该调度状态下的调度规则。搭建完成基于BP神经网络的调度知识模型后，将获取的数据输入到该模型中进行训练，得到项目调度状态到调度规则之间的映射模型，保存模型参数。

2.2.2 实时调度决策模块

将人工神经网络与串行调度相结合，构成实时调度决策模块。在线调度阶段，基于BP神经网络的学习模型能够依据当前调度阶段的系统状态，实时决策最佳调度优先级规则，具体步骤如下：

步骤1初始化，j=0，tS0=0，N={0}，U={1,2,…J}，待调度作业集合D=∅。

步骤2计算当前阶段下12个调度状态特征，根据人工神经网络模型，从8种调度优先级规则中选择最佳调度规则λ，转步骤3。

步骤3根据调度优先级规则λ，确定待调度作业j，更新D={j}，转步骤4。

步骤4根据串行调度机制对作业j调度，确定tSj，更新集合N=N∪{j}，U=CU(N∩U)；如果U≠∅，则转步骤2；如U=∅，则转步骤5。

步骤5调度完成，输出最终调度结果和Tc。

3 数值实验与分析

为验证本文设计算法的有效性，选择PSPLIB标准算例库中作业规模为30作业，60作业，90作业规模算例进行实验，实验平台采用Windows10 64位操作系统，Intel Core i7-8700、3.20 GHz CPU、16.00 G RAM，开发环境为Pycharm和Python 3.7。人工神经网络的相关参数为：输入层神经元数目12，输出层神经元数目8，隐层1神经元数目100，隐层2神经元数目50，训练样本数80 000个算例。

2.1 两组围术期指标比较 观察组手术时间、术后肛门排气时间及住院时间均短于对照组(P<0.05)；观察组术中出血量少于对照组(P<0.05)。见表1。

针对不同规模算例的RCPSP问题，通过单一调度规则启发式算法和基于实时调度状态的调度优先级规则智能决策算法之间的性能对比，验证该算法的有效性。实验结果如表3～表5所示，其中ANN表示本文算法求得算例的解，AVG表示8种单一调度规则启发式算法求得算例解的平均值，即

AVG=(SPT+LFT+MST+MTS+

OGRPW+GRD+TRS+WRUP)/8；

GAP1=100%×(min{SPT,LFT,MST,

MTS,OGRPW,GRD,TRS,

WRUP}-ANN)/ANN;

GAP2=100%×(AVG-ANN)/ANN。

表3 30作业规模实验结果

续表3

表4 60作业规模实验结果

表5 90作业规模实验结果

为进一步验证本文求解RIP所设计的双层迭代循环搜索算法(ANN-IL)的有效性，通过与改进文献[24]所提出的算法(P-GA)进行对比实验，不同算例规模的详细实验数据如表6～表8所示。表中：GAP为两种算法求解算例的目标函数值的偏差百分比，GAP=100%×[(ANN-IL)-(P-GA)]/(P-GA);tA，tG分别表示两种算法的求解时间(单位：s)。

表6 30作业规模两算法对比实验结果

表7 60作业规模两算法对比实验结果

表8 90作业规模两算法对比实验结果

从表6～表8可以得出以下结论：针对30个作业的小规模算例，本文所提算法ANN-IL与对比的遗传算法差距较小，其中一个算例的值甚至优于遗传算法的值。两种算法的平均误差在2%左右，证明了该ANN-IL算法在求解RIP时解的有效性。由于ANN-IL相当于一种启发式方法，在求解速度方面，两种算法不是一个数量级，ANN-IL的平均时间不到1 s，而遗传算法的平均时间为68 s。针对60，90个作业的中大规模算例，ANN-IL的结果次于遗传算法，误差大概在3.8%～5%左右。但在求解速度方面，60规模算例，ANN-IL运算时间平均约3 s，遗传算法平均求解时间约为186 s，是ANN-IL运算时间的60倍；90规模算例实验中，遗传算法平均求解时间约为ANN-IL运算时间的60倍。如图5所示为不同作业规模下两算法实验结果比较，虚线表示两算法所求目标函数值相等，由图5可得ANN-IL算法求得的解与对比算法所求解的差值在一个极小范围内波动。由于P-GA算法运算时间波动幅度较大，为方便比较，通过对CPU时间做底数为10的对数处理，由图6可得本文算法ANN-IL运算时间远小于对比算法时间。综上可得本文设计算法在求解精度误差可接受范围内可以极大缩短求解时间，求解效率远高于传统的元启发式算法。

4 结束语

本文提出一种基于人工神经网络的双层迭代循环搜索算法(ANN-IL)实时调度求解资源投入问题。该算法通过数据挖掘方法获取实时调度状态和对应的最优调度优先级规则的映射知识网络，即构建了基于实时调度状态的调度优先级规则智能决策系统，能够根据获取的实时调度状态数据快速切换优先级规则，对每一个调度阶段进行最优的调度决策，从而实现整个调度过程的智能连续性调度。实验数据表明，本文设计的算法性能上优于任何单一优先级调度规则，运算时间上远远小于常用的元启发式算法。因此，本文所设计的基于实时调度状态的调度优先级规则智能决策系统为合理指导调度过程提供了技术支持，提高了生产调度决策的实时性和智能性。在今后研究中，考虑对不确定环境下的资源投入问题做进一步研究，如资源可使用情况不确定，紧急订单插入等情况。