一种基于深度Q网络的无关并行机动态混合流水车间调度方法

本发明属于混合流水车间调度控制技术，具体涉及一种基于深度Q网络的无关并行机动态混合流水车间调度方法。

混合流水车间指的是按照流水式生产线布置，包含多道工序且每道工序有一台或多台并行机器的生产车间，是一个复杂的多阶段决策过程，对这种车间结构进行研究可有效平衡机器的使用率、增大产能。目前针对HFSP问题的研究大多假定车间信息是完全已知的静态制造环境，且大多针对理想的标准HFSP问题进行研究。然而，当今的制造系统随时面临着各种动态扰动，如：紧急插单、机器故障等，这些扰动会造成实际生产与预定排产计划偏差较大，严重影响了生产效率。同时同一阶段的不同机床在加工同一零件时往往不具有相同的加工能力。以上描述的调度问题称作带有不相关并行机的动态混合流水调度问题(DHFSP-UPM)。因此，研究带有非等效并行机的动态HFSP在线调度方法能够对提高处理扰动事件的能力，增强实际生产系统鲁棒性具有重要意义。

长久以来，很多学者致力于研究如何应用强化学习算法求解动态调度问题，目前已成功求解多类经典动态调度问题。强化学习是一种基于连续状态选择最优的决策方法，根据每个决策点的系统状态信息选择最适合当前生产环境的调度规则，以实现指定指标的最优。由于生产信息复杂多样，调度规则数量庞大，且强化学习的决策机制要求所获取的系统状态具有一定的连续性，目前学者的研究主要用于解决单阶段决策动态调度问题，即一个缓冲区用于存储工件，多个机床根据系统状态信息选择工件，如单机问题、并行机车间问题、作业车间问题、流水车间问题等。

但以上研究中的强化学习决策机制难以求解本发明涉及的混合流水调度多阶段决策问题，即HFSP中每个阶段的机床只从所属阶段的缓冲区中选择零件，一个阶段决策完成后，获取的下一个状态可能是任一个阶段的缓冲区和机床的状态，在决策过程中智能体同时是每个阶段的机床，获取的系统状态同时是每个阶段的缓冲区信息和机器信息，两个连续决策获取的状态不具有相关性。因此通过现有的RL决策方法难以解决混合流水动态调度问题。

总结分析现有的有关成果，有关混合流水车间调度问题的研究，主要存在以下问题：

(1)传统考虑带有并行机特点的混合流水调度研究中，大多假设并行机具有相同加工能力，或根据机床加工效率具有不同的加工时间，有一定的局限性。考虑完全无关并行机更符合实际加工场景。

(2)目前通过深度强化学习算法解决调度问题的研究中，已经成功解决单机调度问题、并行机调度问题、流水调度问题，但通过DQN算法动态选择调度规则求解本发明提到的混合流水调度问题研究还是一片空白。混合流水调度不同阶段的状态特征不具有相关性，难以通过现有算法求解。

(3)实际生产环境中的复杂加工状况很难用有限的参数指标来表达。特别的对于混合流水车间调度问题，需要构建既能表达每个工序阶段信息，也能表达整体加工信息的状态特征向量。同时还要依据指定优化指标设计奖励函数，缺乏统一的参考。

本发明的目的在于提供一种基于深度Q学习的考虑无关并行机的动态混合流水车间调度方法。

实现本发明目的的技术解决方案为：本发明所述的一种基于深度Q学习的考虑工件到达和无关并行机特点的动态混合流水车间调度方法，以最小化平均加权拖期为调度目标，用深层神经网络拟合价值函数，将每个决策点的加工系统状态作为输入训练模型，将工件排序规则与机器分配规则的组合作为动作候选集，结合强化学习的奖惩机制，为每次调度决策选取最优的动作组合，具体包括如下步骤：

步骤1：根据本发明考虑的混合流水车间问题，引入无关并行机和工件随机到达两种约束，建立强化学习在该调度问题上的应用框架，以最小化平均加权拖期为优化目标建立新的数学模型。并在此基础上通过编程搭建离散仿真环境，包含工件个数，工件种类数，机床个数，阶段数，加工完成标志done等参数。

转入步骤2；

步骤2：执行车间仿真环境初始化，同时初始化容量为MEMORY_SIZE的经验回放池D，随机初始化状态价值神经网络V(θ)及目标网络V(θ)′。其中D用于存储每一个重调度点的决策数据。转入步骤3：

步骤3：等待当系统中某一阶段遇到如工件到达的动态事件时，智能体依据重调度点的系统状态St以贪婪值e-greed为概率选择动作At，执行动作后得到奖励Rt,同时系统到达下一个状态St+1。将当前的状态特征St、选取的动作At、获得的奖励Rt、到达的下一个状态St+1、加工完成标志done作为本次决策的样本(St,At,Rt,St+1,done)放入经验回放池D。其中加工完成标志done为布尔量，仅当最后一阶段加工完最后一个工件后为true，其余情况皆为false。决策步计数器count+1，转入步骤4：

步骤4：在智能体训练前，需要在经验回放池D中预先存储MEMORY_WARMUP_SIZE个决策样本数据。判断D的数据个数是否达到阙值MEMORY_WARMUP_SIZE：

如果没到达，则重复步骤3；否则转入步骤5

步骤5：判断决策步计数器count是否是LEARN_FREQ的整数倍，LEARN_FREQ表示每隔多少决策步训练一次状态价值神经网络V(θ)：

如果是，则转入步骤6；否则转入步骤7

步骤6：随机从样本回放池D中随机提取BATCH_SIZE条数据，用于训练状态价值神经网络V(θ)，V(θ)通过梯度下降法更新参数，同时判断决策步计数器count是否是1000的整数倍：

如果是，则将神经网络参数深拷贝给目标网络V(θ)‘，转入步骤6；否则直接转入步骤6。

步骤7：判断加工完成标志done是否为true；如果是，代数计数器episode+1,转入步骤7；否则重复步骤3；

步骤8：判断代数计数器episode是否到达阙值Max_episode；

如果没到达，执行车间仿真环境初始化，重复步骤3；否则结束训练。

本发明与现有技术相比，其显著优点在于：

(1)本发明克服了现有技术中难以解决HFSP各加工阶段的状态特征不具有相关性的问题，提出一种基于深度Q学习的求解机制，通过在每个阶段单独提取状态特征，保证了HFSP各加工阶段的状态特征具有相关性。

(2)提出了一种考虑无关并行机和随机工件到达的动态混合流水车间调度的数学模型，给出结合离散事件仿真原理实现训练环境的编程实现思想。

(3)提出了一种用于表征最小化平均拖期时间的奖励函数，以及能够在复杂加工过程中能表示局部特征和全局特征的状态向量。通过数学表达验证了提出的奖励函数的合理性。

图1为本发明提出算法解决HFSP与目前强化学习解决调度问题对比图。

图2为本发明的基于DQN解决考虑无关并行机特点的动态混合流水车间调度方法流程图。

图3为假定10类工件同时加工时的模型训练过程图。

图4为假定15类工件同时加工时的模型训练过程图。

下面结合附图对本发明作进一步详细阐述：

本发明所述的一种基于深度Q网络的无关并行机动态混合流水车间调度方法，步骤如下：

步骤1：根据本发明考虑的混合流水车间问题，引入无关并行机和工件随机到达两种约束，以最小化平均加权拖期为优化目标建立新的数学模型。建立强化学习在该调度问题上的应用框架，并在此基础上每个重调度点的决策函数env.step()，完成离散仿真环境的编程实现，包含工件个数，工件种类数，机床个数，阶段数，转入步骤2；

进一步地，步骤1所述的调度系统目标函数为最小化平均加权拖期，所建立的强化学习应用框架如图X所示：调度过程含S个阶段，每个阶段s∈[1，S]有Ms个机器,每个机器mi(1≤i≤Ms)加工同一类型工件时具有不同的加工时间.从零时刻开始，n类作业独立间隔到达，每类作业j∈n的到达时间间隔服从均匀分布。每个工件必须从第1个阶段到第3个阶段顺序加工，每个工件在每个阶段都要在一台机床上进行加工。作业到达后即可进行加工，如果作业不能立即处理，则作业将存储在缓冲区BF中。每当机器加工完成一个作业，或一个新的作业到达，这一时刻称为重调度点t，将当前阶段的状态特征St输入到DQN中，DQN依据St选择最合适的调度规则作为动作，并依据调度规则选择要加工的工件和加工该工件的机器。当前阶段到达下一个重调度点t′时，将t′的状态特征St′输入到DQN中，并将St′作为St的next_state。工件在当前阶段加工完成后立刻被放入下一个阶段的BF中。当工件在最后阶段的机器完成加工后，被放入交货区进行交付。

进一步地，步骤1所述数学模型建立如下，首先进行一些必要的假设和硬约束，其中一些列出如下：

所有工件独立，可能产生拖期；

机床的功率不同，且提前知晓；

零时刻缓冲区无工件，所有工件随机到达；

对于任意阶段，缓冲区中新增加的工件被视为该阶段的工件到达事件(即上一阶段加工完成后被放入下一阶段缓冲区的动作被视为工件到达事件)；

每个机器只有加工完成一个工件才能加工下一个工件；

每个工件一次只能在一台机床上加工；

非占用状态下，每个阶段的任何机器上都可以加工工件；

任何两个阶段之间的存储容量是无限的(即在两个加工过程之间，一个工件可以等待任意时间)；

工件的工装时间和两个连续阶段之间的输送时间包括在相应阶段的缓冲区的排队时间内。

接下来给出本发明研究问题所使用的符号：

Jjk：类型为j的第k个工件

SJj：类型为j的工件集合

Isi：阶段为s的第i个机床

类型为j的工件在阶段s的估计加工时间

Pjsi：类型为的工件在阶段s的第i个机床的实际加工时间

Pjk：类型为j的第k工件的总加工时间

Ajks：类型为j的第k工件到达阶段s缓冲区的时间

Djk：类型为j的第k工件的交货期

机床i的理想功率

wi：机床i的实际功率

xjksi：如果在阶段s将作业Jjk分配给机器i，则xjksi＝1；否则，xjksi＝0。

更准确地说，数学模型可以表示如下：

STjksi＝Ajks+Qjks (4)

Cjksi＝STjksi+Pjksi (5)

STj′k′si＞Cjksi (6)

Aj,k,1＞0 (7)

Aj,k,s+1＝Cj,k,s (8)

STj,k,s+1＞Cj,k,s (9)

目标函数(1)是最小化所有工件加工完成后的平均加权拖期。公式(2)描述了非等效并行机的特点，任一类型工件在同一阶段的不同机床上具有不同的加工时间，其实际加工时间由实际功率与理想功率的比值与估计加工时间的乘积决定。公式(3)描述了每类工件的在所有机床上的实际平均加工时间。公式(4)描述了工件的阶段开始加工时间等于到达缓冲区的时间与在缓冲区的排队时间的和。公式(5)描述了工件的阶段完工时间等于阶段开始加工时间与工件在该机床实际加工时间的和。约束(6)确保对于同一台机器连续处理的两个作业，只有在前一个作业完成后，才能启动下一个作业。约束(7)要求初始时刻缓冲区无工件，所有工件随机到达。约束(8)确保工件在一个阶段加工完成后，立刻被送入下一阶段缓冲区排队。约束(9)是工艺限制，即一个作业连续两道工序，下一道工序必须在前一道工序完成后才能开始。约束(10)确保作业通过所有阶段，并且在每个阶段仅由一台机床处理。

进一步的，步骤1定义的车间仿真环境初始化函数实现步骤如下：

步骤2：执行车间仿真环境初始化，进行DQN算法建模，同时初始化容量为MEMORY_SIZE的经验回放池D，随机初始化状态价值评估网络V(θ)及目标网络V(θ)‘。同时完成加工系统状态建模，用于决策点的系统状态获取。其中D用于存储每一个重调度点的决策数据。转入步骤3：

进一步的，步骤2所述的DQN算法建模如下：DQN是一种Q-RL强化学习的改进算法，通过结合DL深度学习来解决高维条件下的价值函数拟合问题，主要改进有两个方面：经验回放和目标网络结构异步更新。经验回放的动机是：深度学习作为有监督学习，要求数据满足规模大、独立同分布，且数据之间无关联性的特点。但强化学习中通过每个决策步的实时决策以获取状态与奖励进行学习，为了获取大量训练数据往往难度较大。因此为了克服经验数据的相关性和数据利用率低的问题，采取了预先通过仿真实验将MEMORY_WARMUP_SIZE个样本数据存储到经验回放池中，当满足上述条件后，每隔LEARN_FREQ个决策步随机从经验回放池中抽取BATCH_SIZE个数据进行训练。对于LEARN_FREQ的取值，通常取为100-200；对于MEMORY_WARMUP_SIZE的取值，通常取为每个episode决策步总数的10-100倍；对于BATCH_SIZE的取值，通常为2的倍数，常取32、64、128、256等；对于经验回放池的存储上限MEMORY_WARMUP，经验回放池通常设置为堆栈结构，当存储到达上限时，会将最早的样本数据顶出，从而可能会造成有效经验的丢失，因此通常在电脑性能允许下尽可能大。

进一步的，步骤2所述的双网络结构优化如下：对于传统的DQN算法中，回报的估计和动作价值的估计都和神经网络的权重矩阵W有关，当权重值变化时，回报的估计和动作价值的估计都会变化，容易出现不稳定的情况。因此目标网络实在原有的神经网络之外再搭建一份结构完全相同的网络。在每次训练后权重更新的过程中，只更新评估网络V(θ)(原网络)的权重。在完成一定次数的更新后，再将评估网络的权重值赋给目标网络V(θ)‘，进而进行下一次更新。

步骤3：等待当系统中某一阶段遇到如工件到达的动态事件时，智能体依据重调度点的系统状态St以贪婪值e-greed为策略从候选动作集中选择动作At，执行动作后得到奖励Rt,同时系统到达下一个状态St+1。将当前的状态特征St、选取的动作At、获得的奖励Rt、到达的下一个状态St+1、加工完成标志done作为本次决策的样本(St,At,Rt,St+1,done)放入经验回放池D。其中加工完成标志done为布尔量，仅当最后一阶段加工完最后一个工件后为true，其余情况皆为false。决策步计数器count+1，转入步骤4：

进一步的，步骤3所述的状态特征以阶段为单位，每个重调度点获取的为某一阶段的状态特征，每个特征向量包含8类特征，共4n+3Ms+4个参数。如对于任一阶段s的机床msi，其加工第j类工件的第k类特征记作ak,j,s,所定义的状态特征集共同表示了环境所处的局部信息和全局信息。

状态特征的定义如表1所示

表1机器状态特征定义表

对表中使用到的参数做统一说明：假设此时某一阶段s出现动态事件，则提取该阶段的缓冲区和机器的上述状态特征作为状态向量。t为当前决策点所处的环境时间，n为总的工件类型数，Jjk表示第j类的第k个零件，Nj表示缓冲区中第j类零件的个数，Ng表示缓冲区中工件的剩余交货期落在指定区间的个数，Pjs表示第j类工件在阶段s所有机器上的平均加工时间，Djks表示工件Jjk在阶段s的阶段交货期，对于任一工件的交货期，按下式进行计算：

其中Ajks为工件到达第一阶段缓冲区的时间，h为预设的交货期紧张因子。

进一步的，步骤3所述的候选动作集如下：

表2决策过程的候选动作集

本发明选用调度规则作为候选动作集，主要分为两个类别，工件分派规则及机床选择规则，由于本发明研究的是无关并行机特点混合流水车间调度，阶段内的不同机床具有不同的加工能力。因此既选择最合适的工件，也需要选择最合适的机床。

表2调度规则候选动作集

对于上述定义的调度规则，其实施步骤如下：

假设s阶段缓冲区的空闲工件的集合表示为Os＝{Jjk}，s阶段内的空闲机床的集合表示为F＝{msi}，Fs内的每个参量表示决策点t时刻s阶段的空闲机床的编号msi。

步骤4：在智能体训练前，判断经验回放池D中的数据个数是否达到阙值MEMORY_WARMUP_SIZE：

如果没到达，则重复步骤3；否则转入步骤5

步骤5：判断决策步计数器count是否是LEARN_FREQ的整数倍，LEARN_FREQ表示每隔多少决策步训练一次状态价值神经网络V(θ)：

如果是，则转入步骤6；否则转入步骤7

步骤6：随机从样本回放池D中随机提取BATCH_SIZE条数据，用于训练状态价值神经网络V(θ)，V(θ)通过梯度下降法更新参数，同时判断决策步计数器count是否是1000的整数倍：

如果是，则将神经网络参数深拷贝给目标网络V(θ)‘，转入步骤6；否则直接转入步骤6。

步骤7：判断加工完成标志done是否为true；如果是，代数计数器episode+1,转入步骤7；否则重复步骤3；

步骤8：判断代数计数器episode是否到达阙值Max_episode

如果没到达，执行车间仿真环境初始化，重复步骤3；否则结束训练。

六、实施例

为了验证本发明提出方法在不同生产配置下的有效性和通用性，在此将DQN决策系统与各种单一及复合调度规则在不同生产配置下的性能进行了比较。

首先对于DQN算法中的智能体参数设计，折扣因子γ用来衡量未来奖励对本次决策的影响程度，值越小决策过程越重视当前决策收益，通常为0.9-0.999，取γ＝0.9。探索率ε表示智能体有ε的概率随机选择动作，否则选择价值最高的动作，初始阶段通常将ε设定的很大，有助于智能体在环境内进行充分探索，随后在每次决策后将ε的值以ε-decrement逐次减小，直到1e-3，以便在收敛后稳定选择最优的动作,取ε＝0.4，ε-decrement＝1e-6。训练集样本数量batch_size表示每次模型训练时从样本回放池中提取的样本数据个数，通常为32、64、128等，取batch_size＝64。

其次对于DQN算法中的神经网络参数设计，网络结构设定为全连接层，共包含1个输入层，7个隐层和1个输出层。输入层包含4n+8m+4个节点，与决策点获取的系统状态参数个数一致；每个隐层包含64个节点，激活函数设为relu；输出层包含9个节点，与动作个数一致。学习率表示在每次训练中对模型修正的程度，取lr＝0.001。

最后，此处使用的测试算例是随机生成的，假设车间开始(0时刻)无任何工件，随后n个类型的工件各自服从泊松分布到达，任一类型j的连续两次新作业的到达时间间隔服从U(1,10)的均匀分布；每个工件Jjk在同一加工阶段的不同机床上加工时间完全独立，其加工时间Pjki服从U(1，20)的均匀分布；不同类型工件所占权重W服从U(1，5)的均匀分布。假设总加工阶段数S＝3，每个加工阶段的机床数目m＝8。依据工件总个数N、工件种类n、交货期紧张因子K三个参数设置12组对照试验，其中工件总个数N分别取50、100、200，工件种类n分别取10、15，交货期紧张因子K分别取1、2，具体对照试验参数设计见表。每组对照试验随机生成30个算例，计算完成后取平均值。

表3对照试验参数设计

表4对照实验结果对比

由表4可知，相比单一调度规则，本发明提出的基于DQN的调度方法在大多数加工条件下均由于单一调度规则，具有根据加工状况实时选择调度规则的能力。在所有加工条件下均接近最优解，运行稳定。尽管训练过程往往需要花费大量的时间(受限于机器的性能，在本机i5处理器训练时间约10-30h)，但一经训练完成，在实际应用中可以在极短时间内做出决策，满足了完全反应时动态调度对实时性的要求。

图3为工件类型设定为10时，随着智能体的不断训练，工件平均加权拖期时间的变化图。每次将所有工件加工完成算作一个episode，在开始探索阶段内，智能体的上下波动较大。但当探索率到达0.001后，智能体倾向于选择最佳的调度规则，随着episode的不断增加，算法逐渐收敛，工件平均加权拖期减小到下限，本模型在2150个episode后，已经能稳定获得最优解。

图4为工件类型设定为15时，随着智能体的不断训练，工件平均加权拖期时间的变化图。随着工件类型的增加，模型收敛难度变大。本模型在6000个episode后，已经能稳定获得最优解。