基于深度时序差分强化学习的非置换流水车间调度问题研究

发布时间：2021-10-12 14:13

　　流水线是制造系统中广泛采用的一类生产模式。业已证明机器数超过三台的流水车间调度问题为NP难问题,对该问题的研究有重要的理论和工程价值。传统调度问题解决方法包括数学建模、启发式和元启发式算法等,能在较短时间内获得较优解,但难以应对任务、资源等不确定因素的动态变化。深度强化学习直接依据输入状态进行行为策略选取,更贴近实际制造系统加工状态响应式的生产调度过程。因此,本文首次提出一种深度时序差分强化学习方法,用于求解非置换流水车间单目标、多目标和动态调度问题。首先,介绍深度学习和强化学习的基础理论,包括基于神经网络的深度学习、基于马尔科夫决策过程的强化学习,在此基础上给出深度时序差分强化学习算法框架,创新性地将深度Q学习网络中异策略的Q学习替换为同策略的基于状态值的TD学习。其次,首次运用深度时序差分强化学习算法求解最小化最大完工时间的非置换流水车间调度问题。每台机器定义15个加工状态特征,设置28个启发式算法和分配规则组成的候选行为集,依据优化目标定义状态转移报酬函数,将调度问题转化为多阶段决策过程。应用提出算法求解基准问题集flcmax的40个实例,与构造启发式算法和蚁群算法对比测试,解的... 

【文章来源】：华中科技大学湖北省 211工程院校 985工程院校 教育部直属院校

【文章页数】：70 页

【学位级别】：硕士

【部分图文】：

小规模问题1最优调度甘特图

flcmax_50_15_2 6531 7750 8712 8835 8206 8104flcmax_50_20_2 6740 8838 9809 9858 9412 9115flcmax_50_20_1 6736 8539 9023 9124 8557 8460flcmax_50_20_7 6756 8417 9360 9168 9369 8823flcmax_50_20_8 6897 8590 9290 9109 8905 8805flcmax_50_20_4 6830 8493 9436 9615 8815 8841由表 3-5 可知，相较于 SCH 和 CHD-ACS 算法，本文提出的深度强化学习算法可以获得较优的解，部分解已经低于原实例的上界；由于算法采用框架性平台和解释性语言 Python 编写，因此算法时间对比没有在表 3-5 中列出，深度神经网络的训练过程需要一定时间，但训练好的网络可以针对调度问题实例在极短时间内输出较优策略。值得指出的是，相较于 ACS 算法 10000 次以上的迭代过程，本算法在 800 代以内即可得到较优解。如图 3-4 所示为实例 flcmax_20_15_6 所求最优策略得到的甘特图。图中红色竖直虚线表示状态转移分隔线，代表调度决策时间点。

图 3-5 实例 flcmax_20_15_6 生产周期迭代下降曲线为了分析在实验所有实例所得最优策略中各个行为的利用率，得到如图 3-6 所示的启发式行为使用频数分布图。图 3-6 启发式行为使用频次分布图由图 3-6 可以看出，使用次数超过 150 次的行为分别是 Jonhson1，Jonshon2，

【参考文献】：
期刊论文
[1]基于滚动窗口的多目标动态调度优化研究[J]. 张超勇,李新宇,王晓娟,刘琼,高亮.  中国机械工程. 2009(18)

博士论文
[1]机械加工置换流水线节能性多目标优化调度方法研究[D]. 李顺江.重庆大学 2016
[2]基于自然启发式算法的作业车间调度问题理论与应用研究[D]. 张超勇.华中科技大学 2007

硕士论文
[1]基于遗传算法的车间动态调度研究[D]. 张富生.山东大学 2013



本文编号：3432736