基于深度强化学习的非置换流水车间调度问题

2021-02-25肖鹏飞张超勇孟磊磊

计算机集成制造系统 2021年1期

肖鹏飞，张超勇+，孟磊磊,2，洪辉，戴稳

(1.华中科技大学数字制造装备与技术国家重点实验室，湖北武汉 430074；2 聊城大学计算机学院，山东聊城 252059)

0 引言

流水车间是一类制造行业常见的生产布局配置形式[1-2]。流水车间调度问题可以描述为：工件集N={J1,J2,…,Jn}由机器集M={M1,M2,…,Mm}进行加工，每个工件经由相同的工艺路线，即经由机器M1，M2，…直到最后一台机器Mm加工。调度决策就是安排工件通过每台机器的加工顺序。若规定所有m台机器上n个工件的加工顺序均相同，则称其为置换流水车间调度(Permutation Flow-shop Scheduling，PFS)问题；若允许不同机器上工件的加工顺序可以改变，这类松弛置换约束条件的调度问题称为非置换流水车间调度(Non-Permutation Flow-shop Scheduling，NPFS)问题。NPFS问题需要满足以下约束条件：①每台机器每个时刻只能加工一道工序且不允许中断；②每个工件Jj都有对应于机器i(i=1,2,…,m)上的工序加工时间pij，准备时间包含在加工时间内或可以忽略不计；③每台机器前的等待队列容量足够大，以满足重新排列工件加工顺序的需要。相较于PFS问题n!的解规模，NPFS问题有最多高达(n!)max{m-2,1}种不同候选解，研究表明当机器数m≥3时，NPFS为非确定性多项式(NP)难题。调度方案的生产周期(makespan)是所有工件最后一道工序完工时间的最大值。最小化Makespan的NPFS问题较为常见，简记为Fm||Cmax[3]。

目前，在求解流水车间调度问题的传统方法中，精确算法受限于问题的规模和性质，而启发式和元启发式算法能在较短的时间获得问题的近优解。针对Fm||Cmax问题，Ying[4]提出一种迭代贪婪(Iterated Greedy，IG)算法，并分三阶段运用IG算法改进各组机器上工件的置换加工顺序;Fernandez等[5]提出一种打破捆绑的插入规则启发式方法，与IG算法结合取得了很好的效果;Lin等[6]和Ying等[7]研究了基于禁忌搜索和模拟退火的混合方法和基于有向图模型的蚁群优化算法解决该问题。然而，启发式和元启发式算法将调度过程视作静态不可分割的整体，不能适应复杂多变的实际生产环境。简单构造启发式(Simple Constructive Heuristic，SCH)根据确定的规则在每个调度决策时刻挑选工件加工，体现了调度问题的实时性特点。大量研究发现，多种SCH优先规则的线性或随机组合更有优势。Panwalker等[8]依据性能指标对113种不同分配规则进行了归纳和总结;Mouelhi等[9]研究表明，可以通过神经网络依据制造系统当前状态和车间操作环境参数，在有机器空闲时自动化地选择高效分配规则。强化学习算法可以产生适应实际生产状态的调度策略。Wei等[10]通过定义“生产压力”特征值和两步调度规则，将Q学习用于作业车间的组合分配规则选取，但该方法采用的表格型强化学习模型并不能描述实际复杂加工过程;Wang等[11]在解决单机调度问题时应用Q学习算法灵活选择调度规则，优化了Makespan等3个目标;文献[12-13]研究了Q学习算法解决最小化误工时间相关目标的动态随机作业车间调度问题;Miyashita[14]采用结合函数泛化器的时序差分(Temporal Difference，TD)法减少平均误工时间和在制品数量的加权总和;张志聪等[15]给每台机器定义15个状态特征，利用TD法训练线性状值函数泛化器求解NPFS问题，但线性函数泛化器拟合和泛化能力有限;Wang等[16]将Q学习用于随机经济批量实时调度问题;Li等[17]用强化学习解决订单式生产系统联合定价、提前期确定和调度综合决策问题。

采用神经网络逼近强化学习值函数的方法源于上世纪90年代，由于常常出现不稳定不收敛的情况，一直没有太大突破。近年来，归因于Google 的DeepMind公司在游戏和围棋操控方面的研究，一种基于评价(critic)和决策(actor)机制的深度强化学习方法被提出并引起了广泛关注，该方法结合了深度神经网络能够利用历史数据在线学习和强化学习依据状态灵活选取对应行为的优点。Mnih等[18-19]在神经学认知基础上，利用卷积神经网络拟合值函数，设置类似海马体的经验回放记忆体并独立设置目标网络，使得提出的深度Q学习网络(Deep Q-learning Network，DQN)算法在游戏操作学习的过程中超出人类专业玩家水平。

本文在DQN算法的基础上，首次提出一种基于状态值TD学习的深度强化学习算法，该算法保留了DQN的主要优点，同时创新性地将异策略的Q学习替换为同策略的TD学习，这是因为：①调度问题转化为强化学习问题后，行为空间属于多维离散空间，不适合采用基于一维离散行为值函数的Q学习；②Q学习采用异策略，用最优估计价值的行为替代交互时采取的行为，可能造成过高估计[20]。本文所提算法的模型与实际调度过程更接近，不但适用于计算复杂度更大的NPFS问题，而且从原理上适合解决动态调度问题。

1 基本原理

1.1 强化学习

强化学习是一种机器学习算法[21]。强化学习算法无须知道状态转移概率矩阵，无须在迭代时扫描很多状态，因此是解决序贯决策问题包括马尔科夫决策过程(Markov Decision Processes, MDP)和半马尔科夫决策过程(Semi-Markov Decision Processes, SMDP)的有效方法。

1.1.1 马尔科夫决策过程

马尔科夫性是指系统的下一个状态仅与当前状态有关，而与以前状态无关的性质。状态转移满足马尔科夫属性的多阶段决策问题属于MDP问题。MDP可以用五元组来描述：

E={Z+,S,A(s),P,R}。

(1)

式中：智能体(Agent)处于环境E中，Z+={0,1,2,…}表示各个决策阶段的集合；对于状态空间S，每个状态s∈S是环境状态的描述；A表示行为空间，A(s)表示状态为s(s∈S)时可以采取的行为的集合；P为状态转移概率函数，P(s,a,s′)和R(s,a,s′)分别表示状态为s时采取行为a(a∈A(s))后状态转移到s′的概率和获得的即时报酬。

(2)

式(2)描述了值函数的迭代形式及两类值函数间的关系。最优策略及其对应的最优值函数定义为

∀s∈S:V*(s)=Vπ*(s)。

(3)

以最优策略更新等式(2)得到最优贝尔曼等式：

(4)

依据式(4)可以证明，在条件为∃s∈S:Vπ(s)≤Qπ(s,π′(s))下将动作改为π′(s)=argmaxaQπ(s,a)能够使策略更好，对应的值函数单调递增。

1.1.2 策略迭代和值迭代

强化学习需要同时更新交织在一起的策略与价值。观察贝尔曼等式，可以将问题视作不断迭代优化的过程，思路如下[20]：

(1)以某种初始策略π开始，对∀s∈S计算当前策略π对应的值函数Vπ(s)；

(2)利用这个值函数，找到更好的策略π′；

(3)利用更优的策略继续更新值函数，得到Vπ′(s)；

(4)不断重复步骤(2)和步骤(3)，直至π与π′一致。

经过若干轮这样的迭代，当前策略会逐步收敛到最优策略。这种解决问题的思路形成的算法称为策略迭代算法。

实际上，值函数迭代和策略更新可以同步进行。由于存在最优策略，对于每个状态，最优策略采取的行为不会比其他行为差。由此可以得到状态值函数的更新方法：V(s)←maxaQ(s,a)，即

(5)

1.1.3 评估状态值的TD价值迭代算法

TD法结合蒙特卡罗和动态规划方法，采用经典贝尔曼公式进行迭代，直至值函数收敛。基本迭代公式如下：

V(st)←V(st)+α[rt+1+γV(st+1)-V(st)]。

(6)

式中：rt+1+γV(st+1)为TD目标;δt=rt+1+γV(st+1)-V(st)为TD偏差;α为步长或学习率。迭代公式(6)是有模型强化学习公式的精简和变形，适用于无模型的强化学习。算法流程如表1所示。

表1 评估状态值的TD算法

1.2 深度学习

1.2.1 深度神经网络

深度学习是在人工神经网络的基础上发展而来的一种表示学习，其主要模型是深度神经网络[23]神经元和人工神经网络模型(如图1)。深层神经网络结构具有更大的容量和指数级的表达空间，使得模型能够处理非线性数据，从而有更强的学习能力。

深度学习在近期的成功主要依赖于海量的训练数据、非常灵活的模型、足够的运算能力和足够对抗维数灾难的先验经验。LeCun等[24]提出一种预训练与微调相结合的技术，大幅减少了训练多层神经网络的时间，各种优化技术的出现，如单侧抑制的Relu激活函数，使得梯度消失问题进一步缓解。同时深度残差[25]的技术应用可以使网络层数的堆叠达到百层以上。

1.2.2 激活函数

激活函数(activation function)是神经网络设计的一个核心单元，激活函数赋予神经元自我学习和适应的能力[26]。激活函数在神经网络中引入了非线性学习处理能力，使得模型能处理非线性数据。常用的激活函数包括阶跃函数、sigmoid函数、tanh函数和近似生物神经元的激活函数如Relu、Leaky-Relu及softplus等。由于近似生物神经元的激活函数在绝大多数网络和应用中比传统函数好，本文采用Relu激活函数。

1.2.3 优化算法

目标函数的优化是神经网络训练中的核心问题之一。研究应用中除了常用的随机梯度下降(Stochastic Gradient Descent, SGD)以外还相继出现了动量优化算法(Momentum)、RMSProp和Adam算法。这些算法策略不仅加快了求解速度，还降低了超参数(如学习率)对求解过程的影响，简化了求解过程。考虑到内存消耗和学习率，在深度学习领域提及的目标优化方法一般是指支持数据集分块，并按照分块单元数据包(mini-batch)训练的优化算法。

2 深度强化学习方法

2.1 调度问题的转化

将强化学习应用于调度领域的关键问题和难点是将调度问题转化为一个SMDP问题。首要问题是定义系统各个时刻的状态特征。

2.1.1状态特征

状态特征和可选行为的定义与调度问题特征紧密相关。一般而言，遵循以下原则[15]：

(1)状态特征能够描述调度环境的主要特点和变化，包括系统全局特征和局部特征。

(2)所有问题的所有状态通过一个通用特征集来表示。

(3)状态可以通过状态特征来表示和概括各种不同调度问题。

(4)状态特征是一种对状态变量的数值表征。

(5)特征应易于计算。正规化特征因为可以用相对统一的尺度描述不同问题而被优先考虑。

流水车间中第i台机器Mi的第k个特征记作fi,k。对于机器Mi(1≤i

表2 状态特征列表

即使一些特征可能冗余，采用多种特征可以让机器学习效率更优。一些特征也可以作为是否触发相应行动或工作的指示。状态特征1描述了不同机器上的工件数量的分布；状态特征2描述了当前分配在各机器上的工作负荷；状态特征3描述了各机器从当前状态开始须要完成的总工作负荷；状态特征4、5描述了当前在各个等待队列中工件的最长或最短加工时间；状态特征6表示正在加工作业的剩余加工时间，进而表征机器的忙/闲状态；状态特征7、8表示机器上等待加工工件的最长或最短剩余加工时间；状态特征9、10描述工件在某机器上加工时间与其在下一台机器上的加工时间的比值情况；状态特征11～14决定机器是否应该采用Johnson-Bellman规则定义的行为；状态15决定即使有作业等待加工时，是否应该让机器保持空闲。所有特征一起提供了某状态下的机器和工件信息。智能体感知加工状态特征的深度神经网络结构如图2所示。

2.1.2 启发式行为

可以选取SCH给每台机器定义候选行为集，其中优先分配规则用于强化学习可以克服短视的天性。与状态相关或无关的行为都应该被采纳，以充分利用现有调度规则理论和智能体从经验中学习的能力。本文选取了最小化生产周期目标问题中常用的28种行为，如表3所示。

表3 每台机器候选行为集

续表3

机器Mm-1能够采取的行为集合是{a(k)|1≤k≤3，5≤k≤28}，机器Mm能够采取的行为集合是{a(k)|k={1，28}，5≤k≤16}，其他机器Mi(1≤i≤m-3)上没有行为限制。

2.1.3 报酬函数

报酬函数的选择依据以下规则：①反映行为的即时影响，与行为的即时报酬联系密切；②累积的总报酬反映目标函数值；③报酬函数能够应用于不同规模的问题。由于优化目标是最小化生产周期，智能体能够在周期更短的调度中获得更大回报。

注意到生产周期与机器利用率紧密相关。定义δi(t)为机器的忙闲状态指示函数为：

(7)

报酬函数定义为：

(8)

式中：m为机器数;rk表示系统在决策时刻tk-1执行行为后转移到tk时刻状态获得的报酬。显然rk等于时间间隔[tk-1，tk]平均每台机器空闲时间的相反数。可以证明最小化生产周期等价于从一条交互轨迹序列中最大化获得的累积回报R。证明如下：

(9)

式中Ti表示第i台机器在加工过程中的总空闲时间。由式(9)可知，生产周期越小，总回报越大。

2.2 深度时序差分强化学习算法

2.2.1 探索与利用

探索指在单步决策中，不局限于当前最优行为，也尝试其他可能获得较高行为值的行为；利用指采用当前已知的最优策略，获取最大回报。为了平衡智能体在单步环境交互过程中的探索与利用的分配，采用ε-贪心策略，即以ε概率随机选取候选行为，以1-ε概率选择当前已知最好行为。将状态s下采取组合行为a的概率记作p(s,a)，可得：

(10)

式中：|A(s)|为状态s下候选的组合行为集合的大小;a*(s)为相应状态下的贪婪行为，

(11)

2.2.2算法框架

本文提出一种深度时序差分强化学习(Deep Temporal Difference Network, DTDN)算法，算法框架如表4所示。

表4 基于状态值的时序差分强化学习算法

2.2.3 算法模型和实施

为简化起见，以规模为m=3，n=4的流水车间可视化说明算法实施过程。如图3所示，圆形表示机器，三角形表示工件，矩形表示容量足够大的等待队列。

在开始加工时刻，调度系统处于初始状态s0，此时所有工件位于第一个等候队列Q1，且所有机器处于空闲状态。然后第一台机器选择一个动作a(k)(1≤k≤27)，即选择队列Q1中某个工件加工。之后每当任意一台机器完成了一道工序的加工，系统转移到一个新的状态st,该状态下每台机器选择一个行为执行。当又有某一道工序完成时，系统转移到下一个状态st+1，智能体获得一次回报rt+1，rt+1可以通过两个状态之间的时间间隔计算。由于每个决策时刻，每个机器同时选择一个行为执行，实际上系统在状态st实施了一次由m个子行为组合而成的多维行为at+1=(a1,a2,…,am)。当系统到达终止状态sT时，意味着所有队列全为空，且所有工件全部加工完成，即获得一个调度方案。

DQN网络输出层用若干个节点对应有限个离散行为值，不能涵盖指数级的多维行为空间，并且异策略的Q学习在评价行为值时用最优值替代实际交互值造成过高估计，因此该方法不能直接适用于多维行为空间NPFS问题。本文提出采用同策略的TD学习代替Q学习，基于状态值间接计算行为值，适用于选取多维行为且缓解了值函数过高估计问题。二者不同之处体现在网络结构和其拟合的价值函数两方面，如图4所示。

DTDN算法的实施流程图如图5所示。实施过程主要包括两层循环：外层循环对应于图3中的加工周期(episode)，内层循环对应于图3中每一步状态转移(step)。

3 实例验证

3.1 标准测试集和实验平台

为了评估本文所提算法的有效性，分别在小规模和大规模问题上验证算法。小规模问题来自文献[28]，大规模问题采用Demirkol 等[29]建立的标准测试调度问题集，测试集包含600个随机产生的6个基本车间调度问题的实例。本文采用的是对应于Fm||Cmax问题的40个测试实例。所有作业在0时刻释放，加工时间服从1～200的离散均匀分布。测试实例规模是2类机器数目(m=15,20)和4类工件数目(n=20,30,40,50)的8个组合，总工序数目分布在300～1 000之间，n和m的比值介于1～3.3。由m和n的每个组合生成10个实例。

鉴于问题的规模和复杂性，实例无法求得精确解。文献[29]使用5个不同构建型启发式和3个版本的转移瓶颈工序启发式算法求解每个实例。所有算法在一台50 MHz处理器的SUN SPARC服务器多任务Unix操作系统上运行。每个实例的上界(UB)是算法发现的最优解，下界(LB)通过松弛容量约束条件等方法获得。为获得更紧凑和具有挑战性的测试集，文献[29]依据实例上下界间的百分距离将每个m和n的组合降序排列，只公布每个组合的前5个实例。因此，共获得40个Fm‖Cmax问题测试实例，每个实例以flcmax_n_m_Instance-Number标识。

用Python语言在Visual Studio Code上编码所提算法，于2.3 GHz Intel i5 处理器Linux操作系统PC平台运行。强化学习平台OpenAI Gym以框架形式规范了环境(Env)类的主要成员方法，包括构造(init)、重置(reset)、执行(step)、绘图(render)和结束(close)；执行算法的智能体与环境进行交互迭代；智能体深度神经网络模型利用后端TensorFlow实现。

参数选择可能影响求解质量，有一般性原则可以遵循。折扣因子γ衡量后续状态值对总回报的权重，因此一般取值接近1，设γ=0.95；为便于在迭代初始阶段充分探索策略空间，结束阶段利用最优策略，ε-贪心策略中设置初始ε=1，并以0.995的折扣率指数衰减；设学习率α=5×10-4，最大交互次数MAX_EPISODE=800，记忆体D容量N=6 000，采样批量BATCH_SIZE=64；智能体深度神经网络结构如图2b所示，网络参数采取随机初始化策略。

3.2 实验结果及分析

(1)小规模问题

以文献[28]中两个小规模测试实例说明采用DTDN算法进行调度决策的过程。两个问题的加工数据分别为：

(12)

对于式(12)问题1，DTDN与部分常见启发式算法求得的最优解如表5所示，可见该算法相比启发式算法能获得较优解，表中用黑体数字表示。其对应甘特图如图6所示，图6中竖直虚线表示状态转移分隔线，代表调度决策时间点。

表5 问题1测试结果对比表

NEH是当前解决Fm|prmu|Cmax问题最有效的启发式算法之一。DTDN算法和NEH及其改进算法NEH_KK在问题2上的测试对比结果如表6所示。DTDN算法得到的工件置换加工顺序为{1,3,5,4,6,2}，最优解相较于NEH和NEH_KK算法效率分别提升了4.5%和3.0%。

表6 问题2测试结果对比表

(2)大规模问题

本算法实验计算结果和两种SCH分配规则及文献[7]中蚁群算法(Ant Colony System，ACS)对比情况如表7所示。蚁群算法采用常量启发式期望(Constant Heuristic Desirability，CHD)策略，利用多阶段无环有向图模型，蚁群从模型初始节点到终止节点的一次遍历即为一次调度过程。

表7 实验结果对比

续表7

由表7可知，相较于SCH和CHD-ACS算法，本文提出的深度强化学习算法可以获得较优的解，部分解已经低于原实例的上界；由于算法采用框架性平台和解释性语言Python编写，因此算法时间对比没有在表7中列出，深度神经网络的训练过程需要一定时间，但训练好的网络可以针对调度问题实例在极短时间内输出较优策略。值得指出的是，相较于ACS算法10 000次以上的迭代过程，本算法在800代以内即可得到较优解。如图7所示为实例flcmax_20_15_6所求最优策略得到的甘特图。

如图8所示为实例flcmax_20_15_6生产周期随着迭代次数变化。由图8可知，生产周期随迭代过程显著减小，在800代以内达到较优值。

为了分析在实验所有实例所得最优策略中各个行为的利用率，得到如图9所示的启发式行为使用频数分布图。

由图9可以看出，使用次数超过150次的行为分别是Jonhson1，Jonshon2，SPT，LPT，SRM，LRM，SSO，LSO，SPT+SSO。这些行为对获得最优解有较大贡献度，因此也具有较大利用价值；其他行为频数分布相对比较均匀，表现并不突出。因此，可以考虑增添其他构建启发式行为到候选行为空间，淘汰一些利用率低的行为，从而精简行为集合。