一种解决分布式混合流水车间总延迟时间优化的强化学习蛙跳算法

摘要

本发明公开了一种解决分布式混合流水车间总延迟时间优化问题的强化学习蛙跳算法，主要为了改善传统调度优化方法解决分布式混合流水车间调度问题上的不足。其主要步骤如下：(1)设计问题的三串表示方法。(2)将Q‑学习嵌入到蛙跳算法的模因组搜索过程中，Q‑学习算法包括由全局搜索、邻域搜索和解的接收准则组成的动作集合和基于种群精英解和离散度而构建的6种状态。(3)在算法运行的过程中，根据种群的状态，利用Q‑学习动态的选择执行的模因组搜索策略。本发明提高了分布式混合流水车间调度方案的质量，可为车间生产过程提供高效的调度方案。

说明书

技术领域

本发明涉及车间调度领域，具体是一种解决分布式混合流水车间总延迟时间优化的强化学习蛙跳算法。

背景技术

混合流水车间调度问题是一类广泛存在于化工、冶金、纺织、钢铁、半导体等工业过程的典型调度问题，是流水车间调度问题和并行机调度问题的综合。随着经济全球化的不断深入发展以及市场竞争的日益加剧，企业之间的并购、合作生产和协作生产越来越多，分布式生产成为一种常见的生产制造模式。分布式生产系统能够充分利用多个工厂(车间)或者加工中心的生产制造资源，通过对资源的合理规划和共享，实现以合理的成本快速高效地完成产品的加工制造。在分布式制造环境下，多个工厂的调度都包含混合流水车间调度问题，这类问题称为分布式混合流水车间调度问题。与混合流水车间调度问题相比，分布式混合流水车间调度问题往往包括机器分配、工厂分配和调度三个子问题，其子问题更多，且子问题之间耦合关系更加复杂，如工厂分配直接影响机器分配和调度的优化内容，如果工件在所分配的工厂无法得到最优的机器分配和调度，即使工厂分配达到最优，整个问题的解也难以达到最优。另外，在实际的生产过程中，产品往往需要由多种部件装配而成，现有关分布式混合流水车间调度问题的研究只考虑了加工阶段而忽略了运输和装配阶段。

发明内容

本发明的目的就是为了克服现有技术的不足，提供一种解决分布式混合流水车间总延迟时间优化的强化学习蛙跳算法。

本发明采用的技术方案是：

一种解决分布式混合流水车间总延迟时间优化的强化学习蛙跳算法，包括以下步骤：

(1)Q-学习算法

Q-学习的计算形式如下：

其中α表示学习比例，γ是折扣因子，r

动作选择依赖于Q值，最初，所有Q值都是0，说明agent没有任何可供使用的学习经验，ε-greedy选择是一种常用的动作选择策略，其描述如下：如果随机数rand＜ε，随机选择一个动作；否则，选择当前状态下Q值最大的动作a，即

(2)编码和解码

采用三串编码方式表达一个解，对于一个具有n个工件和F个工厂且考虑运输和装配的DHFSP，编码方案包括三个部分：工厂分配串[θ

解码过程如下：

1)根据工厂分配串将工件分配到各个工厂，由工件排列和部件排列确定每个工厂中工件和部件的排列；

2)根据工件和部件的排列，依次执行加工、运输和装配。当部件在第l个阶段加工时，选择m

初始种群P由随机产生的N个解组成；

(3)邻域搜索

动作a

应用了12种邻域结构N

N

假设工厂f是完成时间最大的工厂，在邻域结构N

当上述工厂f的最大完成时间减少时，最大完成时间很可能会降低；N

利用上述邻域结构，设计两种邻域搜索NS

对于NS

(4)全局搜索

一个解由三个串组成，针对解x,z，设计三种交叉操作，解z的工件排列中位置k和l之间的工件的集合定义为

(5)Q-学习过程

Q-学习算法主要包括状态s

种群P的状态由种群最好解x

其中

Im用于描述x

由于利用贪婪方式更新x

通常利用贪婪接收准则确定能否接收新解，即当新解y优于解x时，新解y替换x，给出了概率接收准则：如果新解y优于x，则利用y替换即x＝y；否则，若随机数rand＜β，则利用y替换x，其中β＝0.1；动作集A包含4种动作，每种动作表示一种模因组搜索策略，A＝[a(1),a(2),a(3),a(4)]，全局搜索过程采用贪婪接受准则或概率接收准则，NS

模因组M

模因组搜索过程中，一旦选择一个动作，该动作作为模因组的搜索策略一直存在直到模因组搜索次数μ达到；

6种状态的序号为1,2,3,4,5,6，显然，状态1最好，状态6最差，因为状态1中不仅x

动作选择采用ε-greedy选择策略；

(6)算法描述

强化学习蛙跳算法是蛙跳算法和Q-学习的集成，初始种群P随机产生，然后划分为s个模因组，模因组搜索过程利用Q-学习动态选择搜索策略，模因组搜索结束后，利用所有模因重新构建种群P，基于Q-学习的DSFLA的流程图如附图5所示；

强化学习蛙跳算法描述如下：

1)随机产生包含N个解的种群P，Q-表的初始值设为0，gen＝1；

2)执行种群划分；

3)利用Q-学习动态选择一个动作；

4)根据选择的动作，对每一个模因组执行模因组搜索；

5)进行种群重构，更新Q-表，gen＝gen+1；

6)若不满足终止条件，重复2)～5)，否则，输出结果。

本发明的有益效果：本方法以蛙跳算法为框架，设计三串表示方法对分布式混合流水车间调度问题进行编码，利用强化学习蛙跳算法解决该问题。将Q-学习嵌入到蛙跳算法的模因组搜索过程中，Q-学习算法包括由全局搜索、邻域搜索和解的接收准则组成的动作集合和基于种群精英解和离散度而构建的6种状态。在算法运行的过程中，根据种群的状态，利用Q-学习动态的选择执行的模因组搜索策略。本发明提高了分布式混合流水车间调度方案的质量，可为车间生产过程提供高效的调度方案。

附图说明

图1是实例的调度甘特图；

图2是六个邻域结构的过程；

图3是三个交叉操作的过程；

图4是Im和ΔD的的每种状态发生的比例；

图5是基于Q-学习的DSFLA的流程图；

图6是6个算法关于指标的计算结果箱线图；

图7是6个算法关于指标的计算结果箱线图；

图8是6个算法关于指标的计算结果箱线图；

图9是案例的调度甘特图。

具体实施方式：

下面结合附图对发明进一步说明：

(1)问题描述

考虑运输和装配的DHFSP描述如下：存在n个工件J

存在F个同构工厂，每个工厂为一个装配混合流水车间，每个工厂包含加工、运输和装配三个过程。存在S个加工阶段，第l个加工阶段由m

问题存在如下工件约束和机器约束：加工机器在同一时刻只能加工一个部件，运输机器和装配机器同一时刻只能运输和装配一个工件；部件在同一时刻只能在一台机器加工，属于同一工件的部件同一时刻只能在一台机器上运输或装配；加工、运输或装配不能中断；所有机器在任意时刻都可用。

考虑运输和装配的DHFSP由工厂分配、机器分配和调度三个子问题组成。三个子问题之间存在强耦合关系。另外，调度子问题还包含工件调度和部件调度。工件调度决定工件的加工顺序，部件调度确定部件的加工顺序。

在满足所有约束的条件下最小化最大完成时间。

其中C

一个实例的加工信息如表1和表2所示，该实例包含5个工件、2个工厂和2个加工阶段，每个加工阶段都有2台并行机。附图1给出了该实例的甘特图。

表1 5个工件的实例信息

表2p

(2)Q-学习算法

Q-学习的计算形式如下：

其中α表示学习比例，γ是折扣因子，r

动作选择依赖于Q值。最初，所有Q值都是0，说明agent没有任何可供使用的学习经验。ε-greedy选择是一种常用的动作选择策略，其描述如下：如果随机数rand＜ε，随机选择一个动作；否则，选择当前状态下Q值最大的动作a，即

(3)编码和解码

采用三串编码方式表达一个解。对于一个具有n个工件和F个工厂且考虑运输和装配的DHFSP，编码方案包括三个部分：工厂分配串[θ

解码过程如下：

1)根据工厂分配串将工件分配到各个工厂，由工件排列和部件排列确定每个工厂中工件和部件的排列；

2)根据工件和部件的排列，依次执行加工、运输和装配。当部件在第l个阶段加工时，选择m

对于问题描述中的给出的实例，一个可能解为工件排列[4,2,3,1,5]，部件排列[4,2,3,1,5,6,8,9,7,11,10,12,13,15,14]和工厂分配串[1,2,1,2,2]。工件1和工件3在工厂1中加工，工件排列为3,1，对应的部件排列为8,9,7,4,2,3,1。附图1给出了该解的调度甘特图。

初始种群P由随机产生的N个解组成。

(4)邻域搜索

动作a

应用了12种邻域结构N

N

假设工厂f是完成时间最大的工厂。在邻域结构N

当上述工厂f的最大完成时间减少时，最大完成时间很可能会降低。N

利用上述邻域结构，设计两种邻域搜索NS

对于NS

(5)全局搜索

一个解由三个串组成，针对解x,z，设计三种交叉操作。解z的工件排列中位置k和l之间的工件的集合定义为

(6)Q-学习过程

Q-学习算法主要包括状态s

种群P的状态由种群最好解x

其中

Im用于描述x

根据Im和ΔD定义6种状态，如表3所示。

表3状态集

由于利用贪婪方式更新x

附图4给出了Im和ΔD关于实例60×3×8和100×5×8在DSFLA的整个搜索过程中每种情况发生的比例。由附图4可知，两个指标的每种情况都会发生，6种状态都出现了，因此，有必要设置6种状态。

通常利用贪婪接收准则确定能否接收新解，即当新解y优于解x时，新解y替换x。给出了概率接收准则：如果新解y优于x，则利用y替换即x＝y；否则，若随机数rand＜β，则利用y替换x。其中β＝0.1。动作集A包含4种动作，每种动作表示一种模因组搜索策略。A＝[a(1),a(2),a(3),a(4)]，全局搜索过程采用贪婪接受准则或概率接收准则，NS

模因组M

模因组搜索过程中，一旦选择一个动作，该动作作为模因组的搜索策略一直存在直到模因组搜索次数μ达到。

6种状态的序号为1,2,3,4,5,6。显然，状态1最好，状态6最差。因为状态1中不仅x

动作选择采用ε-greedy选择策略。

为了展示Q-表的更新过程给出一个示例，共有6种状态和4种动作。假设当前状态S

表4Q-表的更新过程

(7)算法描述

强化学习蛙跳算法是蛙跳算法和Q-学习的集成。初始种群P随机产生，然后划分为s个模因组。模因组搜索过程利用Q-学习动态选择搜索策略。模因组搜索结束后，利用所有模因重新构建种群P。基于Q-学习的DSFLA的流程图如附图5所示。

强化学习蛙跳算法描述如下：

1)随机产生包含N个解的种群P，Q-表的初始值设为0，gen＝1。

2)执行种群划分。

3)利用Q-学习动态选择一个动作。

4)根据选择的动作，对每一个模因组执行模因组搜索。

5)进行种群重构，更新Q-表，gen＝gen+1。

6)若不满足终止条件，重复2)～5)，否则，输出结果。

(8)实验验证

随机产生80个实例，其中p

RPD

RPD

MIN

从表5、表6、表7、附图6、附图7和附图8的计算结果可以看出，本发明涉及的一种解决分布式混合流水车间总延迟时间优化问题的强化学习蛙跳算法具有显著优势。其中，QSFLA、SFLA、CMA、HPSO、HVNS和IDCOA分别表示强化学习蛙跳算法、基本的蛙跳算法、竞争文化基因算法、混合粒子群优化算法、混合变邻域搜索算法和改进的离散布谷鸟优化算法。

表5六种算法关于MIN的部分计算结果

表6六种算法关于AVG的部分计算结果

表7六种算法关于MAX的部分计算结果

(9)实际案例

给出一个家具厂的实际案例，该公司生产多种家具，如不同类型的抽屉式卧式介质储物柜，每个储存柜由一些部件装配而成，这些部件会在加工完成后运输到装配车间装配。每个部件的加工包含冲压阶段、钣金阶段、焊接阶段、电动压紧阶段和钻孔阶段。

混合流水车间包含4个产品、2个工厂和5个阶段。表8和表9给出了实例的加工数据。强化学习蛙跳算法获得的调度方案如附图9所示，其中C

因此本发明涉及的一种解决分布式混合流水车间总延迟时间优化问题的强化学习蛙跳算法可以很好的解决实际问题。

表8加工信息

表9加工数据