博文

2025年度优秀论文奖 | 深度强化学习算法求解动态流水车间实时调度问题

已有 976 次阅读 2026-9-7 09:29 |个人分类:论文推荐|系统分类:博客资讯

编辑荐语

本期将给大家分享2025年度优秀论文奖获奖文章"深度强化学习算法求解动态流水车间实时调度问题(Deep reinforcement learning algorithm for dynamic flow shop real-time scheduling problem)". 如您对本期相关内容有好的理解与建议, 欢迎评论区留言.

本文聚焦于动态流水车间实时调度场景下现有深度强化学习方法存在的状态特征冗余、动作收益随机、状态与动作匹配度低三大核心短板, 提出一种融合深度双Q网络的自适应深度强化学习算法ADRLA求解以最小化最大完工时间为目标的动态流水车间调度问题DFSP. 研究首先采用泊松过程刻画新工件动态到达规律, 依托马尔可夫决策过程完成调度问题序贯决策转化, 基于工件跨机器相对完工时间指标构建低冗余、强泛化的单一类别状态特征向量, 同步设计5类以压缩机器空闲间隙为共同目标的调度规则构成关联匹配的动作空间, 并搭建以全机器空闲时间和为评价依据的分段奖励函数, 完整形成适配DFSP特性的强化学习三要素体系. 在此基础上, 创新性选用DDQN作为调度智能体, 通过主、目标双Q网络分离动作选择与价值估计, 从根源解决传统DQN存在的Q值过估计问题, 配合梯度下降参数迭代与周期性网络同步策略完成模型训练; 该智能体仅依靠小规模调度数据集训练, 即可自适应适配同机器数量下不同工件规模、不同工件到达速率的动态调度场景. 仿真对比实验从最优混合动作策略有效性、多类型基准算法性能两维度开展验证, 箱线图与多组算例指标结果表明, ADRLA所得最大完工时间均值更优、求解稳定性更强, 且随问题规模增大相比传统启发式、经典强化学习及同类深度强化学习调度算法的实时性与优化优势持续扩大. 研究揭示不同规模流水车间调度具备相近内在结构特征, 为小样本训练通用型智能调度网络提供新思路, 后续可拓展至节能与运输集成调度场景, 为动态生产环境下智能制造实时智能调度提供兼具理论支撑与工程落地价值的新型求解框架.

论文介绍

深度强化学习算法求解动态流水车间实时调度问题

Deep reinforcement learning algorithm for dynamic flow shop real-time scheduling problem

杨媛媛1,2, 胡蓉1,2†, 钱斌1,2, 张长胜1, 金怀平1

机构: 1. 昆明理工大学信息工程与自动化学院; 2. 昆明理工大学云南省人工智能重点实验室

引用:

杨媛媛, 胡蓉, 钱斌, 等. 深度强化学习算法求解动态流水车间实时调度问题. 控制理论与应用, 2024, 41(6): 1047 – 1055

DOI: 10.7641/CTA.2023.20916

全文链接:

https://jcta.ijournals.cn/cta_cn/ch/reader/create_pdf.aspx?file_no=ccta220916&flag=1&journal_id=cta_cn&year_id=2024

摘要

本文针对动态流水车间调度问题(DFSP), 以最小化最大完工时间为优化目标, 提出一种自适应深度强化学习算法(ADRLA)进行求解. 首先, 将DFSP的新工件动态到达过程模拟为泊松过程, 进而采用马尔科夫决策过程(MDP)对DFSP的求解过程进行描述, 将DFSP转化为可由强化学习求解的序贯决策问题. 然后, 根据DFSP的排序模型特点, 设计具有较好状态特征区分度和泛化性的状态特征向量, 并依此提出5种特定动作(即调度规则)来选择当前需加工的工件, 同时构造基于问题特性的奖励函数以获取动作执行效果的评价值(即奖励值), 从而确定ADRLA的3类基本要素. 进而, 以深度双Q网络(DDQN)作为ADRLA中的智能体, 用于进行调度决策. 该智能体采用由少量小规模DFSP确定的数据集(即3类基本要素在不同问题上的数据)训练后, 可较准确刻画不同规模DFSP的状态特征向量与Q值向量(由各动作的Q值组成)间的非线性关系, 从而能对各种规模DFSP进行自适应实时调度. 最后, 通过在不同测试问题上的仿真实验和与算法比较, 验证了所提ADRLA求解DFSP的有效性和实时性.

引言

车间调度问题是制造行业中非常重要的组合优化问题, 大量存在于机械､钢铁､石化和电信等行业[1–4]. 流水车间调度问题(flow shop scheduling problem, FSP)是目前研究最多的一类车间调度问题, 属于典型的NP-hard问题. 现有文献中针对FSP的研究主要考虑静态和确定环境[5]. 然而, 随着市场竞争日益激烈, 为确保效益,企业不仅要为重要客户提供紧急插单加工服务, 还需积极在国内外市场不断争抢临时订单. 在此背景下, 订单或工件动态到达的FSP(dynamic FSP, DFSP)已成为当前企业生产必须面临的一类重要问题.

现有DFSP的研究主要采用订单事件驱动的重调度策略或周期性重调度策略, 将DFSP分解为一系列静态的FSP, 然后设计启发式算法或智能优化算法进行求解. 譬如贪婪迭代算法[6]､混合重调度算法[7]､启发式方法(即GSH方法)[8]､混合遗传算法–粒子群算法[9]､重调度遗传算法[10]等. 上述文献主要通过重调度策略结合启发式或智能算法的方式处理和求解DFSP, 但每次重调度时均是简单地重启算法来求解当前的新FSP, 故往往耗时较长.

深度强化学习(deep reinforcement learning, DRL)算法是近年的研究热点[11].该算法将具有感知能力的深度学习(deep learning, DL)和具有决策能力的强化学习(reinforcement learning, RL)有机结合, 已在Atari[12], AlphaGo Zero[13]等复杂场景中表现出强大的学习能力和优化决策能力. DRL算法不依赖环境模型和历史先验知识, 仅需通过与环境交互即可学习当前经验来训练神经网络. 这既能解决DL算法训练过程中需要大量优质先验知识的困难, 也克服了RL算法容易陷入的“维度爆炸”问题[14]. 近年来, DRL算法已被设计用于求解生产调度问题, 并取得良好效果[15–16].

目前, DRL算法求解动态生产调度问题的研究还较为有限. 在动态流水车间调度方面, Yang等[17]针对优化目标为最小化拖期的DFSP以DRL算法中的优势演员–评论家网络作为智能调度网络(intelligent decision-making network, IDMNET)进行求解. Yang等[18]针对优化目标为最小化总延误的动态分布式FSP提出一种实时调度网络(real-time scheduling network, RTSNET)进行求解. 同时, DRL算法求解动态FSP的策略被用于求解静态FSP(相当于对所有工件执行1次动态调度). 譬如, Ren等[19]针对优化目标为最小化最大完工时间的FSP提出一种状态动作网络(state and action network, SANET)进行求解. Gil等[20]针对物料调度的混合FSP以近似策略优化(proximal policy optimization, PPO)网络进行求解. 在动态作业车间调度方面, Luo[21]针对优化目标为最小化总拖期的动态柔性作业车间问题(job-shop scheduling problem, JSP)以深度Q网络(deep Q network, DQN)作为智能体进行求解. Zhao等[22]针对优化目标为最小化总拖期问题的动态JSP以DQN作为智能体进行求解. Chang等[23]针对优化目标为最小化拖期的具有随机任务到达的动态JSP以深度DQN(double DQN, DDQN)作为智能体进行求解. Wang等[24]针对动态多目标柔性JSP以一种DDQN作为智能体进行求解. 此外, DRL算法也开始被用于求解生产车间中的动态智能小车调度问题. Hu等[25]针对优化目标为最小化完工时间和延迟率的动态自动导引运输车调度问题, 以一种新的DQN作为智能体进行求解.

上述算法均取得了较好的调度效果, 但仍存在如下不足: 首先, 现有研究往往选定数个不同指标来确定多个不同类别的状态特征(通常1个指标对应1类特征), 进而以此构成状态向量. 由于这些指标间存在复杂的相关性, 容易使得整个状态向量的内部关系复杂且冗余特征信息较多, 从而降低其表征的泛化能力. 这不利于智能体合理区分相似和不同状态, 会增加网络(即智能体)收敛的难度, 进而影响智能体的决策能力. 此外, 现有研究基本采用简单的贪心启发式规则作为动作, 并将多个动作组成动作向量(即动作空间).这些动作单独执行时速度较快, 但执行效果一般. 同时, 由于缺乏共同的特点或目标, 这些动作多次被智能体选中执行后的累积效果较为随机, 会导致问题最终解的质量不高. 此外,现有状态向量和动作向量基本都是独立设计的, 两者间无明显的相关性. 这增加了网络训练的难度, 也会降低网络的拟合精度, 从而限制智能体的性能.

针对上述研究现状, 本文提出一种自适应深度强化学习算法(adaptive DRLA algorithm, ADRLA)对DFSP进行有效求解. 首先, 以泊松过程描述有新工件到达的动态流水车间问题. 其次, 根据DFSP排序模型特点, 提出工件在各机器上的相对完工时间指标, 并基于该指标设计仅包含同一类特征的状态向量. 该状态向量可较全面刻画和区分不同状态特征, 也具有较好泛化性. 同时, 根据上述状态向量的特点, 设计5个具有共同目标的调度规则作为动作, 并以此构成动作空间. 由于每个动作均试图从某一方面来缩短各机器上相邻工件间的间隙, 智能体在多次选定并执行这些动作的过程中能持续保持工件间较紧的衔接, 有利于获取较高质量的问题最终解. 所设计的状态向量和动作向量间存在明显相关关系, 即后者的执行可减小前者中各元素的值. 这有助于快速获取具有较高拟合精度的网络, 从而能确保智能体的性能. 然后, 设计基于DDQN智能体, 利用主Q网络和目标Q网络协同可解决常规DQN容易出现的Q值过高估计的问题. 最后, 通过在不同规模测试问题上的仿真实验和算法比较, 验证了ADRLA在由中等规模数据集训练后, 可对相同机器数下具有不同工件规模的FSP进行快速有效求解, 从而能在工件到达顺序和到达速率均不同的动态FSP环境中实现自适应实时调度.

微信截图_20260723170058.png

结论

本文提出一种自适应深度强化学习算法ADRLA, 用于求解以最小化最大完工时间为优化目标的动态流水车间调度问题DFSP. 在ADRLA中, 设计基于问题特征的状态特征向量､动作和动作奖励评价等3类基本要素, 以深度双Q网络DDQN作为智能体或调度器对问题进行求解. 仿真实验和算法对比表明, ADRLA内部训练好的DDQN可根据不同规模测试问题的当前状态特征向量来快速合理地确定各动作的Q值, 从而能最终获取较高质量的问题解.

对于生产调度这类非凸优化问题, 虽然已知其解空间地貌整体呈现出极为扁平和粗糙的形态[30], 但其内在几何结构和最优解间的显式关系仍属开放问题, 故目前还无法直接获取两者间的定量关系. 本文所提ADRLA利用DDQN的网络结构和非线性变换, 组合训练数据集的底层特征形成更为抽象的高层特征, 以发现DFSP的隐式内在结构特征, 进而利用所发现的特征指导问题解的生成, 取得了良好效果. 这对智能算法如何合理挖掘和利用调度问题的共性结构信息具有借鉴意义. 此外, 现有的深度强化学习算法在求解各类调度问题时, 训练数据集和测试数据集对应问题的规模基本都相同, 而ADRLA只采用少量小规模DFSP数据集来训练DDQN, 但训练后的DDQN却能在不同规模DFSP上均表现良好. 这表明不同规模DFSP应具有相近的结构特征, 也对如何选取训练数据集来快速训练高质量网络具有一定指导作用. 后续研究将把ADRLA扩展用于求解节能生产与运输集成调度问题.

作者简介

杨媛媛博士研究生, 目前研究方向为智能算法与优化调度;

胡蓉博士生导师, 教授, 目前研究方向为优化方法及决策支持系统;

钱斌博士生导师, 教授, 目前研究方向为智能优化调度理论与方法;

张长胜硕士生导师, 副教授, 目前研究方向为光纤传感器技术与应用;

金怀平硕士生导师, 副教授, 目前研究方向为复杂过程建模与机器学习.

期刊介绍

《控制理论与应用》(Control Theory & Applications)是经国家科学技术部批准, 教育部主管, 由华南理工大学和中国科学院数学与系统科学研究院联合主办的全国性一级学术刊物, 1984年创刊, 月刊, 国内外公开发行. 《控制理论与应用》是中国科学引文数据库首批统计源期刊之一，中文核心期刊，入选中国精品科技期刊顶尖学术论文F5000项目，中国科协自动化学科领域高质量科技期刊目录以及中国科协百篇优秀科技论文遴选计划，2021年入选广东省高质量科技期刊建设项目，2022-2024年连续获得基金委资助（科技活动专项）。

期刊封面2.jpg 目录2.jpg