面向柔性作业车间动态调度的双系统强化学习方法
A Dual-System Reinforcement Learning Method for Flexible Job Shop Dynamic Scheduling
通讯作者: 鲍劲松,男,教授,博士生导师,电话(Tel.):021-67792567;E-mail:bao@dhu.edu.cn.
责任编辑: 孙伟
收稿日期: 2021-06-22
基金资助: |
|
Received: 2021-06-22
作者简介 About authors
刘亚辉(1997-),女,河南省许昌市人,硕士生,从事认知制造、知识图谱、智能调度研究.
航天结构件生产过程中批产任务与研发任务并存,个性化小批量研发生产任务导致紧急插单现象频发.为了保障任务如期完成,解决柔性作业车间面临的动态调度问题,以最小化设备平均负载和最小化总完工时间为优化目标,提出了感知-认知双系统驱动的双环深度Q网络方法.感知系统基于知识图谱实现对车间知识的表示并生成多维信息矩阵;认知系统将调度过程分别抽象为资源配置智能体和工序排序智能体两个阶段,分别对应两个优化目标,设计了车间状态矩阵对问题和约束进行描述,调度决策中分步骤引入动作指令;最后分别设计奖励函数实现资源配置决策和工序排序决策的评价.经某动力所航天壳体加工的实例验证和算法对比分析,验证了所提方法的优越性.
关键词:
In the production process of aerospace structural parts, there coexist batch production tasks and research and development (R&D) tasks. Personalized small-batch R&D and production tasks lead to frequent emergency insertion orders. In order to ensure that the task is completed on schedule and to solve the flexible job shop dynamic scheduling problem, this paper takes minimization of equipment average load and total completion time as optimization goals, and proposes a dual-loop deep Q network (DL-DQN) method driven by a perception-cognition dual system. Based on the knowledge graph, the perception system realizes the representation of workshop knowledge and the generation of multi-dimensional information matrix. The cognitive system abstracts the scheduling process into two stages: resource allocation agent and process sequencing agent, corresponding to two optimization goals respectively. The workshop status matrix is designed to describe the problems and constraints. In scheduling decision, action instructions are introduced step by step. Finally, the reward function is designed to realize the evaluation of resource allocation decision and process sequence decision. Application of the proposed method in the aerospace shell processing of an aerospace institute and comparative analysis of different algorithms verify the superiority of the proposed method.
Keywords:
本文引用格式
刘亚辉, 申兴旺, 顾星海, 彭涛, 鲍劲松, 张丹.
LIU Yahui, SHEN Xingwang, GU Xinghai, PENG Tao, BAO Jinsong, ZHANG Dan.
航天结构件的加工过程具有多品种、小批量、工艺复杂多变的特征,每种工件由多道具有先后顺序约束的工序完成,是典型的作业车间调度问题.由于航天结构件紧急插单任务的扰动影响批量生产任务的生产进程,降低生产效率,所以车间调度方案需要动态变更.在传统作业车间调度的基础上,柔性作业车间调度可以面向更加动态、复杂的车间环境.根据柔性作业车间的特点,可以将该类调度问题拆分为资源配置和工序排序两个子问题,分别利用调度系统中存在的多类型知识,赋予系统自适应响应能力.
近年来,已有众多学者针对动态柔性作业车间调度问题[5]进行研究,主要在鲁棒式方法、重调度法、智能算法等方面展开.鲁棒式方法[6-7]对生产扰动事件的响应速度慢,历史信息无法得到重用;重调度方法[8]可以对扰动事件快速响应,但无法很好利用工艺信息之间的关系;相比之下智能算法[9-10]更适用于处理作业车间的动态调度问题.通过智能算法完成自适应车间调度问题的方法有优先级规则方法[11]、启发式算法[12]、遗传算法(Genetic Algorithm, GA)[13]、进化算法[14]、模拟退火[15]、禁忌搜索方法[16]等.在考虑插单任务的动态调度研究中,Kundakci等[17]针对动态作业车间调度问题中的插单任务、机器故障等,引入有效的混合遗传算法求解此类问题的最大完工时间;Shen等[18]针对柔性作业车间调度的新工件插入和机床故障等问题,提出了基于多目标进化算法的主动-被动调度方法;Wang等[19]提出了一种改进的粒子群算法用于工件随机到达的动态柔性作业车间调度问题的求解.为了实现多约束下调度问题的多目标优化,一些研究学者将调度过程进行分步骤处理.张洁等[20]提出针对调度过程的任务分派和任务排序两阶段,构建具有继承关系的两阶段蚁群并行搜索算法;周亚勤等[21]提出一种嵌套式蚁群-遗传混合算法解决关键设备和人员双资源约束下的航天结构件柔性作业车间调度问题;汪浩祥等[22]利用强化学习的实时性和知识化制造系统的自适应性,将航空发动机装配调度分为分派机器和工序调度两个阶段.现有的调度规则大多无法进行自适应调整以应对动态场景,但随着机器学习的快速发展,可通过学习生成复杂调度策略的强化学习方法已经产生,能赋予调度规则较强的自适应和学习能力.进一步,深度Q网络(Deep Q Network, DQN)结合了具有感知能力的深度学习和决策能力的强化学习,融合了深度神经网络能够利用历史数据在线学习和强化学习从而依据状态灵活选取决策行为的优点,更适用于柔性作业车间调度的决策过程[23].Wang等[24]在多智能体强化学习环境中运用DQN指导基础设施云上多工作流的调度,分别将最大完工时间和成本两个优化目标抽象成两个智能体.Luo[25]研究了用DQN解决以总延期最小为目标的新任务插入下的动态柔性作业车间调度问题.He等[26]针对纺织过程优化问题转化为随机博弈的新框架,在DQN网络算法中将多优化目标抽象成多智能体.林时敬等[27]针对炼钢车间天车动态调度事件,也运用DQN算法将多天车抽象成多智能体协同天车操作动作序列.但现在基于DQN的车间调度方法中,所需调度策略的优化过程与调度相关数据的关联度不够,因此考虑在调度算法中利用系统提供的语义知识优化车间动态调度能力.
为此,本文针对柔性作业车间调度问题,以最小化设备平均负载和最小化总完工时间为目标,在调度过程的资源配置和工序排序阶段,分别设置强化学习智能体,提出双系统强化学习框架.其中,基于感知系统获取知识图谱的知识,分别将资源配置和工序排序所需要的参数集成表示为多维信息矩阵的形式,为认知调度系统提供车间状态参数;认知调度过程中对两个智能体共同构建具有继承关系的双环深度Q网络(Dual-Loop Deep Q Network, DL-DQN)方法.
1 柔性作业车间调度模型
柔性作业生产车间调度问题可以描述为:总共有K个任务订单,其中包括批产任务和插单任务,每个任务包含n个待加工工件,即
表1 符号与变量
Tab.1
符号 | 符号描述 |
---|---|
J | 工件集合 |
G | 设备组集合 |
M | 设备集合 |
P | 人员集合 |
S | 物料集合 |
ok, i, j | 第k个任务中工件Ji的第j道工序 |
j | 工序索引j=1, 2, …, m |
Rk, i, j | 第k个任务中工件Ji的第j道工序配置资源,Rk, i, j={Mk, i, j, Pk, i, j, Sk, i, j} |
Mk, i, j | 工序ok, i, j的配置设备 |
Pk, i, j | 工序ok, i, j的配置操作人员 |
Sk, i, j | 工序ok, i, j的配置物料 |
第k个任务中工件Ji的到达时间 | |
工序ok, i, j的开始时间 | |
工序ok, i, j的结束时间 | |
工序ok, i, j与下道工序的准备时间 | |
第k个任务中工件Ji的总加工时间 | |
Wl, t(Wk, i) | 设备组Gl中设备Mt的加工负载(以设备为目标计算得到Wl,t,以工序为单位计算得到Wk,i) |
设备组Gl中设备Mt的最大加工负载 | |
0-1决策变量,取1时表示第k个任务中工件Ji在设备Mi, j上加工 | |
DP | 交付期 |
柔性作业车间调度模型需要满足如下基本假设:①批产任务中工件一定的情况下,插单任务的工件动态到达;②同一工件工序之间有优先级,需在前道工序加工完成后进行后道工序的加工;③工件某一道工序在加工过程中不能被中断;④ 工件在加工过程中的准备时间、工件转换时间等一同计入加工时间; ⑤同一设备在某一时刻只能加工一道工序;⑥ 同一设备前一工件未完成,后续安排工件需等待;⑦不存在撤单、设备故障等特殊情况.
建立如下数学模型:
式中:
并满足如下约束:
上述公式中,式(1)表示目标函数为最小化设备平均负载;式(2)表示目标函数为最小化总加工时间;式(3)表示插单任务需设备数目在可用设备数Nnum内;式(4)表示同一工件在同一时间只能进入一道工序;式(5)表示同一设备在同一时间只能加工一道工序;式(6)表示设备负荷约束,安排在设备上的总负荷不得超过该设备的最大负荷;式(7)定义了工件的首道工序开始时间;式(8)表示本道工序开始时间
2 双系统强化学习方法
为了实现柔性作业车间的动态调度,解决调度过程中的多阶段方案生成优化,本文提出了知识图谱驱动的车间动态调度过程中感知-认知双系统框架.如图1所示,系统I的感知是将各类型数据进行表示与集成,将调度信息转变成多维矩阵的形式分别表示资源配置和工序排序,输入到系统II.在紧急任务的触发下,系统II的认知利用DL-DQN强化学习方法进行车间排产优化——资源配置智能体以最小化设备平均负载为目标,首先进行该工件所需人员、设备、物料等资源匹配形成资源社群;工序排序智能体以最小化完工时间为目标,将资源社群以工序为单位实现工件顺序排产计划,分步进行调度策略生成,提高加工流的生产连续性和效率.
图1
本文将工作流调度过程看作是一个马尔科夫决策过程,调度目标为最小化设备总负载和最小化总完工时间,分别将优化目标抽象成两个智能体,智能体之间形成继承关系可以观察到对方的动作和奖励.在考虑双环强化过程的前提下,外环强化过程中资源配置状态处于一个状态的长期最优价值为
2.1 感知-调度参数表示与多维信息矩阵集成
利用知识图谱提供的调度参数,根据车间动态调度的两个子问题,分别将所需数据转化成多维信息矩阵输入到系统的强化学习模型中.
资源配置所需的数据为离散型数据,R为资源信息矩阵,每种任务需要由多位工人在多台设备上采用不同的资源进行加工,每种资源包含多种类型:
工序排序所需的数据由工艺序列和加工时间两组数据组成,Q为工序排序信息矩阵,各类型数据构建出排序涉及相关调度参数,以某时间段工位数据建模表示如下:
O为工艺参数矩阵,即任务加工工艺流程方法.加工车间每种设备组只能对应加工某一类型工艺:
T为时间参数矩阵,包括当前任务在某工序加工的开始时间
2.2 认知-DL-DQN调度算法
对感知数据利用DL-DQN算法实现认知应用.图2为本文提出的柔性作业车间动态调度流程.依据批产任务生产方案流程,对插单任务进行紧急程度的判别后分别应用不同的调度原则,当插单任务进入认知调度实现策略优化时,资源配置智能体形成以工件为核心的资源社群配置,工序排序智能体实现单个工序上的工件排序优化.
图2
本文提出的方法不同于传统调度优化方法,其基于优化目标赋予每个智能体不同的功能,然后与多个子环境交互,根据知识图谱提供的各类型信息和应用场景的协同反馈逐步调整策略实现优化.图3为DL-DQN强化学习方法框架,A1是资源配置智能体,A2是工序排序智能体.外环强化由A1根据当前加工资源的参数状态
图3
(1) 调度状态空间.
多智能体在进行车间调度时依赖车间的状态感知信息,分别设计不同的状态空间矩阵.结合车间调度约束和优化目标设计状态矩阵F,车间调度任务主要包括资源配置和工序排序两个阶段,因此用
表2 调度状态参数
Tab.2
调度状态 | 参数类型 | 表达式 | 含义 |
---|---|---|---|
资源配置状态 | 人员状态 | 人员类型 | |
物料状态 | 物料类型 | ||
设备状态 | 设备类型 | ||
设备状态 | |||
工序排序状态 | 工艺状态 | 工艺状态 | |
设备组状态 | |||
时间状态 | 开始时间 | ||
结束时间 | |||
运输时间 | |||
交付期 |
(2) 调度动作空间.
资源配置和工序排序智能体根据机器的加工状况以及工件的生产属性,分别为每一个工件设置调度优先值,本文分别针对两个智能体设置不同的决策动作空间.
资源配置决策空间:资源配置任务是对插单任务进行人员、设备、物料等资源的配置,合理选择能够最小化设备平均负载的最优资源,决策空间定义如表3所示.
表3 资源配置决策动作
Tab.3
决策方法 | 描述 |
---|---|
决策1 | 若人员、设备当前工作环境中空闲且资源配料充足,选择某工件所需人员、设备、物料等资源,然后将其组合为资源配置方案. |
决策2 | 若人员、设备当前工作环境中忙碌且资源配料不充足,分别判断人员已工作工时与技能参数、设备的负载量和资源的存储量,在满足设备负载量最优的情况下将其组合为资源配置方案. |
工序排序决策空间:工序排序是将配置好的资源社群,以最小化完工时间为目标分别在每个工位上进行排序,决策空间定义如表4所示.
表4 工序排序决策动作
Tab.4
符号 | 描述 | 量化方式 |
---|---|---|
FIFO | 先到先加工优先规则 | |
SPT | 工序加工时间最短优先规则 | |
EDD | 交货期最早加工优先规则 | |
SL | 松弛时间最短优先规则 | |
SRPT | 剩余加工时间最长优先规则 |
(3) 调度奖励函数.
通过设置合理的奖励机制,保证算法在多智能体设置下的收敛性,函数设计如下.
资源配置智能体奖励函数R1.
首先定义设备繁忙、空闲的示性函数
式中:
由式(15)和(16)可知,资源配置阶段的最大化奖励R1等价于最小化设备平均负载,证明定义的奖励函数有效.
工序排序智能体奖励函数R2.
首先定义ta时刻第k个任务的第i个工件中第j道工序状态的示性函数μok,i,j(ta),即:
式中:
由式(19)和(20)可知,工序排序阶段的最大化奖励R2等价于最小化总完工时间,证明定义的奖励函数有效.
为双目标奖励函数赋予权值转变为总奖励函数R,如下式:
式中:
(4) 模型更新.
本文模型在DQN基础上改进,两个智能体在训练时,在单位时间内,资源配置智能体根据知识图谱提供的资源相关离散型知识生成资源配置决策动作,随着状态变化以社群的形式传递给工序排序智能体,下一个排序动作以每一设备组为单位,对资源社群进行任务加工序列的安排.调度的两阶段过程不断更新迭代,直至任务完成,采用梯度下降法更新参数,实现策略函数的优化,算法的伪代码如算法1所示.
算法1:DL-DQN多智能体强化学习算法
1. 初始化记忆池 D1、D2;容量N
2. 用随机权重参数 θ1、θ2初始化函数Q1、Q2
3. 用随机权重参数 θ1-、θ2-初始化函数
4. For 迭代次数N = 1, M do
5. 重置资源配置计划并清除结果, 得到初始状态
6. For t=0, T do
7. 选择资源配置策略
8. 得到立即奖励
9. 将经历(
10. For N=1, M do
11. 重置工序排序计划,继承上一个状态
12. For t=0, T do
13. 选择工序排序策略
14. 得到立即奖励
15. 将经历(
16. 从记忆池D2中随机选择一个转换样本数据,用(
17.y2i={r2j,N 在 j+1 步是结束状态 r2j+γ2maxa2ˆQ2(s2j+1,a2;θ2−), 其他
18. 采用梯度下降法(
19. 每过C步迭代更新目标网络
20. End for
21. End for
22. 从记忆池D1中随机选择一个转换样本数据,用(
23.y1i={r1j,N 在 j+1 步是结束状态 r1j+γ1maxa1ˆQ1(s1j+1,a1;θ1−), 其他
24. 采用梯度下降法(
25. 每过C步迭代更新目标网络
26. End for
27. End for
28. 输出: Q1、Q2
3 案例与应用
对提出的双系统强化学习方法进行模型训练和实验.首先,对仿真参数进行说明并进行方法对比;然后利用某航天所薄壁壳体加工过程中紧急插单问题进行实例测试,并进行分析.
3.1 模型训练与对比
3.1.1 测试数据
表5 测试算例参数
Tab.5
算例 | 工件数目 | 工序数 | 设备数 | 工序加工时间/h |
---|---|---|---|---|
MK01 | 6 | 6 | 4 | [1, 10] |
MK02 | 6 | 6 | 6 | [3, 8] |
MK03 | 6 | 8 | 6 | [2, 6] |
MK04 | 8 | 6 | 4 | [1, 10] |
MK05 | 8 | 8 | 6 | [2, 9] |
MK06 | 10 | 6 | 4 | [1, 10] |
MK07 | 10 | 6 | 6 | [3, 8] |
MK08 | 10 | 8 | 6 | [2, 6] |
MK09 | 12 | 6 | 4 | [1, 10] |
MK10 | 12 | 8 | 6 | [2, 9] |
为验证本文提出的DL-DQN算法效果,将随机算法(Random Algorithm, RA)、GA、DQN作为对比算法进行分析比较.
3.1.2 时间复杂度分析
首先,将本文方法和对比算法的时间复杂度分析如下.
(1) RA[29].以先到先加工原则为约束,随机选择设备需加工工件并进行资源分配,设找到可行解需要的迭代次数为TRA,因此RA的时间复杂度可近似描述为O(TRAK).
(2) GA[30].遗传算法一般很难收敛到全局最优解,因此算法的停止根据设置的迭代次数,设GA的最大迭代次数为TGA,种群数量为λ,则GA的时间复杂度可近似描述为O(TGAλK).
(3) DQN.在DQN网络的运行阶段,运行回合数为TDQN,每回合中的步长为nt,因此在运行阶段的时间复杂度为O(TDQNntK).本文提出的DL-DQN算法的时间复杂度与DQN相同.表6为时间复杂度对比.
表6 时间复杂度对比
Tab.6
算法名称 | 时间复杂度 |
---|---|
RA | O (TRAK) |
GA | O (TGAλK) |
DQN | O (TDQNntK) |
DL-DQN | O (TDL-DQNntK) |
由表可见,本文算法和所提算法的时间复杂度和任务数成线性关系,不同的算法涉及参数不同会影响时间复杂度.
3.1.3 模拟结果
本研究以MK04算例进行实验评估,构建作业车间环境,并使用DL-DQN算法进行柔性作业车间调度,在迭代过程中记录参数变化,与DQN算法进行对比.训练过程参数变化如图4所示.
图4
图4
MK04算例模拟参数收敛曲线
Fig.4
Convergence curve of simulation parameters for Case MK04
根据测试算例MK01~MK10,分别用本文方法和对比方法求解总优化目标,结果如图5所示.
图5
图5
测试算例不同算法的总优化目标
Fig.5
Total optimization goals of different algorithms for test cases
3.2 实例测试
3.2.1 加工车间任务信息表
利用某动力所固体火箭发动机薄壁壳体生产模拟数据进行实例测试以验证所提方法的有效性.薄壁壳体的加工具有产研并存的特性,整理航天所生产原始数据后得到设备类型与相关信息如表7所示,不同的设备组对应不同的工序.
表7 车间工序对应多功能设备组
Tab.7
工序 | 设备组 | 设备组序列 |
---|---|---|
固溶 | 固溶炉组 | G1 |
旋压 | 旋压机组 | G2 |
s退火 | 退火炉组 | G3 |
时效 | 时效炉组 | G4 |
粗加工/精加工 | 数控机床组/加工中心组 | G5 |
电子束组焊/激光焊 | 焊机组 | G6 |
油淬 | 油淬炉组 | G7 |
氮气淬 | 氮气淬炉组 | G8 |
回火 | 回火炉组 | G9 |
表8 生产任务工序信息表
Tab.8
任务 | 工序1 | 工序2 | 工序3 | 工序4 | 工序5 | 工序6 | 工序7 | 工序8 |
---|---|---|---|---|---|---|---|---|
J1 | 固溶 | 旋压 | 时效 | 粗加工 | 焊接 | 氮气淬 | 回火 | 精加工 |
J2 | 旋压 | 退火 | 粗加工 | 焊接 | 氮气淬 | 回火 | 精加工 | |
J3 | 固溶 | 旋压 | 粗加工 | 焊接 | 油淬 | 回火 | 精加工 | |
J4 | 固溶 | 旋压 | 退火 | 粗加工 | 焊接 | 油淬 | 回火 | 精加工 |
J5 | 固溶 | 旋压 | 退火 | 粗加工 | 焊接 | 精加工 | ||
J6 | 固溶 | 旋压 | 时效 | 粗加工 | 焊接 | 氮气淬 | 回火 | 精加工 |
表9 生产任务工序时间表
Tab.9
任务 | 工时/h | 加工 数量 | 交货时间/h | |||||||
---|---|---|---|---|---|---|---|---|---|---|
工序1 | 工序2 | 工序3 | 工序4 | 工序5 | 工序6 | 工序7 | 工序8 | |||
J1 | 40 | 15 | 53 | 25 | 19 | 73 | 20 | 17 | 20 | 300 |
J2 | 10 | 43 | 24 | 11 | 38 | 13 | 12 | 10 | 200 | |
J3 | 33 | 33 | 26 | 17 | 103 | 22 | 20 | 18 | 280 | |
J4 | 13 | 5 | 4 | 5 | 5 | 17 | 4 | 5 | 3 | 300 |
J5 | 16 | 8 | 36 | 19 | 9 | 14 | 8 | 120 | ||
J6 | 9 | 3 | 23 | 8 | 6 | 28 | 11 | 10 | 5 | 120 |
3.2.2 感知系统知识表示与集成
根据本文提出的DL-DQN算法,分别为资源配置智能体和工序排序智能体提供多维信息矩阵,两阶段调度过程中所需的参数矩阵如图6所示.
图6
图6
多维信息矩阵实例化表示
Fig.6
Instantiated representation of multi-dimensional information matrix
3.2.3 认知系统车间调度策略生成
假设插单任务的触发时间节点位于批产任务初始化后的20 h和80 h处,针对插单任务导致的柔性作业车间动态调度事件,首先对其进行资源配置,然后以资源社群为单位进行工序排序,将插单任务排产到合适的工序位置.
在资源配置过程中,针对机加工车间的车床工作状况进行全方位的任务配置.以该车间某一时间段的车床加工任务作为分析基础,将车床按照类型划分,每种型号的车床设备各1台,其加工功能不同,针对插单过程中导致的设备平均负载变化,车间车床设备相关信息如表10所示.
表10 车间车床相关信息表
Tab.10
设备类别 | 设备型号 |
---|---|
普通卧式车床 | CDZ6140-1, CDZ6140-2 |
CD6140B-1 | |
数控卧式车床 | CK61200W-1 |
CK6146A-1 | |
CK64160-1, CK64160-2, CK64160-3 | |
CK64250-1 | |
CKD系列数控车床 | CKD6163-1 |
CKD6163K-1, CKD6163K-2 | |
CKD6140S-1 | |
CKD6180D-1, CKD6180D-2 | |
管螺纹车床 | QK1319A-1, QK1319A-2 |
为表明资源配置智能体生成配置策略的合理性,以设备利用率为参考得出调度前后车床设备利用率曲线图(见图7),可以直观地发现,车间车床利用率呈现整体上升趋势且变化平缓,较少出现某一设备负载突变的情况.
图7
图7
插单前后车床利用率信息
Fig.7
Lathe utilization information before and after order insertion
图8
图9
根据插单前后的甘特图得出不同任务交付时间与加工时长的对比.如表11所示(“空白”表示无此项),运用本文方法能够在满足插单任务交付期的前提下,在一定程度上缩短批产任务的总加工时长,特别是调度策略前后J4的总加工时间减少35.08%,交付时间减少13.67%.薄壁壳体制造过程中不同的加工工艺所需时间差异大,因此车间中工序排序引起的时间微小变化会更有利于调度.从设备利用率和加工时间变化来看,本文提出的双系统深度强化学习方法具有一定的可行性.
表11 插单前后任务交付时间与加工时长对比表
Tab.11
任务 | 插单前任务 交付期 | 插单后任务 交付期 | 插单前任务 加工时长/h | 插单后任务 加工时长/h | 交付期 变化率/% | 加工时长 变化率/% |
---|---|---|---|---|---|---|
J1 | 242 | 222 | 242 | 222 | 6.67 | 8.26 |
J2 | 161 | 157 | 151 | 147 | 2 | 2.65 |
J3 | 265 | 274 | 220 | 214 | -3.21 | 2.73 |
J4 | 271 | 230 | 191 | 124 | 13.67 | 35.08 |
J5 | 100 | 78 | ||||
J6 | 115 | 113 |
4 结论
本文对产研并存的柔性作业车间动态调度问题进行了研究,以最小化设备平均负载和最小化总完工时间为优化目标,提出感知-认知双系统与DL-DQN算法融合嵌入的方法,得出以下结论:
(1) 感知系统将知识图谱提供的数据转化成多维信息矩阵输入到认知系统,认知系统将调度过程分成资源配置和工序排序两部分,分别将两个优化目标抽象成具有继承关系的智能体.
(2) 采用DL-DQN算法,外环利用资源配置智能体生成以工件为单位的资源社群,内环利用工序排序智能体以资源社群为单位进行工序级别的工件排序优化.
(3) 对比不同的算法和进行某航天所的固体火箭发动机薄壁壳体加工车间的实例测试,证实提出的双环强化学习方法能更好地利用调度知识图谱提供的参数信息,实现柔性作业车间调度的多目标优化.
目前的研究将设备故障、突发撤单等不确定因素忽略,未来将探究多资源约束情况下的柔性作业车间自适应调度问题.
参考文献
A survey on knowledge graphs: Representation, acquisition, and applications
[J].DOI:10.1109/TNNLS.2021.3070843 URL [本文引用: 1]
Knowledge graph completeness: A systematic literature review
[J].DOI:10.1109/ACCESS.2021.3056622 URL [本文引用: 1]
Cognitive manufacturing in industry 4.0 toward cognitive load reduction: A conceptual framework
[J].DOI:10.3390/asi3040055 URL [本文引用: 1]
Smart manufacturing process and system automation: A critical review of the standards and envisioned scenarios
[J].DOI:10.1016/j.jmsy.2020.06.010 URL [本文引用: 1]
Review of job shop scheduling research and its new perspectives under Industry 4.0
[J].DOI:10.1007/s10845-017-1350-2 URL [本文引用: 1]
考虑机器故障的作业车间调度方案鲁棒测度方法
[J].
Robustness measurement approach of job shop scheduling with machine breakdowns
[J].
考虑设备故障的鲁棒调度计划模板的建模优化
[J].
Modeling and optimization of robust scheduling template considering equipment failure
[J].
Flexible job-shop rescheduling for new job insertion by using discrete jaya algorithm
[J].
DOI:10.1109/TCYB.2018.2817240
PMID:29993706
[本文引用: 1]
Rescheduling is a necessary procedure for a flexible job shop when newly arrived priority jobs must be inserted into an existing schedule. Instability measures the amount of change made to the existing schedule and is an important metrics to evaluate the quality of rescheduling solutions. This paper focuses on a flexible job-shop rescheduling problem (FJRP) for new job insertion. First, it formulates FJRP for new job insertion arising from pump remanufacturing. This paper deals with bi-objective FJRPs to minimize: 1) instability and 2) one of the following indices: a) makespan; b) total flow time; c) machine workload; and d) total machine workload. Next, it discretizes a novel and simple metaheuristic, named Jaya, resulting in DJaya and improves it to solve FJRP. Two simple heuristics are employed to initialize high-quality solutions. Finally, it proposes five objective-oriented local search operators and four ensembles of them to improve the performance of DJaya. Finally, it performs experiments on seven real-life cases with different scales from pump remanufacturing and compares DJaya with some state-of-the-art algorithms. The results show that DJaya is effective and efficient for solving the concerned FJRPs.
A novel knowledge graph-based optimization approach for resource allocation in discrete manufacturing workshops
[J].
Efficient priority rules for project scheduling under dynamic environments: A heuristic approach
[J].
基于混合蚁群算法的半导体生产线炉管区调度方法
[J].
Hybrid ant colony algorithm for batch scheduling in semiconductor furnace operation
[J].
考虑设备可用性约束的单机调度问题
[J].
A single machine scheduling problem considering machine availability constraints
[J].
聚类差分进化算法求解多目标工艺规划与调度集成问题
[J].
Clustering and differential evolution algorithm for solving multi-objectives IPPS problem
[J].
面向能耗的多工艺路线柔性作业车间分批优化调度模型
[J].
DOI:10.3901/JME.2017.05.012
[本文引用: 1]
合理的调度方案能有效降低柔性作业车间总能耗。针对柔性作业车间中加工工件种类多、单批工件数量大、加工工艺路线柔性大等问题,研究一种面向能耗的多工艺路线柔性作业车间分批优化调度模型。分析柔性作业车间中工件加工过程能耗特性,以车间总能耗最低和完工时间最小为优化目标建立了多工艺路线柔性作业车间分批优化调度模型,并采用多目标 模拟退火算法对模型进行优化求解。通过算法优化得到的调度方案与经验调度方案的对比分析,验证了该模型的有效性和实用性。
A batch splitting flexible job shop scheduling model for energy saving under alternative process plans
[J].
DOI:10.3901/JME.2017.05.012
[本文引用: 1]
Reasonable scheduling can significantly reduce total energy consumption in flexible job shops. A batch splitting flexible job shop scheduling model for energy saving under alternative process plans is proposed, in terms of flexible job shops with the characteristic of large variety of workpiece, large quantities of batch size and flexibility of process plans. The characteristic of energy consumption composition of workpiece machining is analyzed, and then the batch splitting flexible job shop scheduling model is established, with the optimization objectives of minimizing energy consumption and makespan. Finally the model is solved based on Multi-objective simulated algorithm, verifying the validity of the model by comparing the algorithm optimization scheduling with experimental scheduling.
Research on multi-agent genetic algorithm based on tabu search for the job shop scheduling problem
[J].
Hybrid genetic algorithms for minimizing makespan in dynamic job shop scheduling problem
[J].DOI:10.1016/j.cie.2016.03.011 URL [本文引用: 1]
Mathematical modeling and multi-objective evolutionary algorithms applied to dynamic flexible job shop scheduling problems
[J].DOI:10.1016/j.ins.2014.11.036 URL [本文引用: 1]
An improved particle swarm optimization algorithm for dynamic job shop scheduling problems with random job arrivals
[J].
基于两阶段蚁群算法的带非等效并行机的作业车间调度
[J].针对带非等效并行机的作业车间生产调度问题,以制造系统的生产成本、准时交货率等为目标,构建生产调度多目标模型。利用蚁群算法在求解复杂优化问题方面的优越性,建立调度问题与蚁群并行搜索的映射关系,将调度过程分成任务分派和任务排序两个阶段,每个阶段分别设计蚁群优化算法,并将两阶段寻优蚂蚁有机结合,构建一种具有继承关系的两阶段蚁群并行搜索算法,可以大大提高获得较优解的概率,并且压缩求解空间,快速获得较优解。通过均匀试验和统计分析确定算法的关键参数组合,将两阶段蚁群算法应用不同规模的8组算例。结果表明,无论是优化结果还是计算效率,两阶蚁群算法均优于改进的遗传算法。将所提出两阶段蚁群算法应用于实际车间的生产调度,减少了生产过程中工序间等待时间和缩短了产品交付周期。
Two-stage ant colony algorithm based job shop scheduling with unrelated parallel machines
[J].The job shop scheduling problem with unrelated parallel machines is investigated. Multiple objectives such as production cost and on time delivery rate for manufacturing system are taken into account in the proposed scheduling model. Considering the superiority of ant colony algorithm in solving the complex optimization problem, the mapping relationship between scheduling problem and ant colony parallel search is structured. The schedule process consists of two stages: tasks assignment and task sequencing. For each stage, the ant colony optimization is designed respectively so that a two-stage ant colony system(TSACS) with inheritance relationship is proposed. It can compress the solution space and improve the solving speed. Key parameters of TSACS are identified through the uniform experiment and statistical analysis. Computational experiments of 8 examples with different sizes are conducted. The results indicate that the proposed TSACA significantly outperforms the improved genetic algorithm in both optimization results and computational efficiency. The implementation of TSACS in real-life case also demonstrates that the waiting time between operations can be reduced and the product delivery cycle can be shortened.
双资源约束的航天结构件车间生产调度方法
[J].
Scheduling the production of aerospace structural parts with dual resource constraints
[J].
DOI:10.3901/JME.2018.09.055
[本文引用: 1]
The production scheduling method of aerospace structural parts with dual resource constraints of critical equipment and operator is investigated, where structural parts' processing time varies with the operator's ability, and the key components and processes have specific equipment and operator requirements constraints. A mathematical model of the flexible job shop scheduling with dual resource constraints (FJSSDR) is constructed to describe the equipment、operator and process information of the parts. A nested ant colony-genetic hybrid algorithm (NACGHA) is designed to solve the FJSSDR problem. Aiming at the dual resource selection problem, the mapping relationship between resource selection problem and ant colony parallel search is structured. Genetic algorithm is used to solve the optimal scheduling problem by taking the selected double resource constraints as the processing constraint information of the job. The equipment processing sequence is optimized with avoiding conflict of key operator resources, where the objectives of fullest utilization of critical equipment and makespan minimization are considered. The ant colony algorithm pheromones are updated by integrating the objective value obtained by ant colony and genetic algorithm to improve the performance. At last, a scheduling case of aerospace structural parts production shop is analyzed. The case study demonstrates that the proposed NACGHA method has good performance on FJSSDR in terms of reducing resource total load, avoiding resource conflict and improving the utilization of key equipment.
知识化制造环境中基于双层Q学习的航空发动机自适应装配调度
[J].
Adaptive assembly scheduling of aero-engine based on double-layer Q-learning in knowledgeable manufacturing
[J].
DRL-scheduling: An intelligent QoS-aware job scheduling framework for applications in clouds
[J].DOI:10.1109/ACCESS.2018.2872674 URL [本文引用: 1]
Multi-objective workflow scheduling with deep-Q-network-based multi-agent reinforcement learning
[J].DOI:10.1109/ACCESS.2019.2902846 URL [本文引用: 1]
Dynamic scheduling for flexible job shop with new job insertions by deep reinforcement learning
[J].
Multi-objective optimization of the textile manufacturing process using deep-Q-network based multi-agent reinforcement learning
[J].DOI:10.1016/j.jmsy.2021.03.017 URL [本文引用: 1]
基于深度强化学习的炼钢车间天车调度方法
[J].
Crane scheduling method in steelmaking workshop based on deep reinforcement learning
[J].
Routing and scheduling in a flexible job shop by tabu search
[J].DOI:10.1007/BF02023073 URL [本文引用: 1]
移动边缘网络中基于双深度Q学习的高能效资源分配方法
[J].
Energy-efficient resource allocation method in mobile edge network based on double deep Q-learning
[J].
/
〈 |
|
〉 |
