基于强化学习的批处理机随机调度问题研究
发布时间：2022-02-12 08:52
批处理机是一类在满足约束的前提下可以同时处理多个工件的设备,目前已广泛应用于制造业中,例如金属加工、半导体生产、纺织品染整作业等相关领域。近年来,随着研究的深入,随机批调度问题也引起了众多学者的关注,本文主要研究差异工件随机到达情况下的单批处理机调度问题。首先依据系统物理模型和工作机制,建立了问题的数学模型,根据加工时间固定和随机两种情况将问题分别建模为半马尔科夫决策过程和连续时间马尔科夫决策过程。并利用基于数学模型的策略迭代算法求得最优调度策略,使系统的生产代价最小化。其次考虑到实际生产系统可能存在建模难和策略迭代算法求解时间过长的原因,引入了强化学习中的Q学习算法对问题进行求解。针对求解过程中Q学习出现的行动空间过大问题,提出了一种行动集删减策略,实验结果表明改进后的Q学习算法要比原始算法求解效果更好。然后针对规模较大的问题,提出了一种基于规则学习的调度方法,该方法在底层使用启发式规则调度工件,在上层使用Q学习为系统的每个状态选择合适的启发式规则。为此,根据系统特性设计了两类共九种启发式规则组成系统的规则库供Q学习搜索。仿真实验表明该方法相比于传统Q学习在优化能力和计算效率上有更好...
【文章来源】：合肥工业大学安徽省211工程院校教育部直属院校
【文章页数】：80 页
【学位级别】：硕士
【部分图文】：
差异工件随机到达Fig2.1Systemmodelofbatchprocessingmach本文的建模背景是半导体生产线中的
合肥工业大学硕士学位论文26件参数下ASR-Q对于原Q学习算法的优化情况，最后在第四部分对ASR算法是否会将系统最优行动删除的情况进行了分析。本节仿真实验均通过MATLABR2016a实现，实验中的系统参数设置与第二章中相同。3.3.1系统优化效果Q学习和ASR-Q每迭代一次，即对当前学到的调度策略的性能进行一轮仿真评估，每轮评估利用当前学到的策略独立进行10次50万步的仿真，取平均值作为当前策略对应的系统代价，同时为了体现系统的随机性，每次仿真数据均根据分布函数随机生成。在上述参数设置下，针对系统加工时间确定和随机两种情况，Q学习和ASR-Q对应的系统平均代价优化曲线如图3.2，3.3所示。图3.2加工时间确定时系统平均代价优化曲线Fig3.2Optimizationcurveofaveragecostsincertainprocessingtime如图3.2所示，Q学习在前期不断的试错探索，曲线波动较为明显，随着学习步数的增加，系统代价逐渐收敛并稳定。学习后期的小幅波动是由于在每次评估中，工件的到达时间和加工时间均是按照分布函数随机生成的，因此每次评估生成的数据都有所不同，这也使得相同策略得到的代价评估会在一定范围内小幅波动。由于使用ASR方法有效缩减了行动空间，可以看出ASR-Q在刚开始就可以得到质量较高的解，因此ASR-Q的收敛速率要明显快于原始算法。同时，随着学习步数的增加，在加工时间确定情况下Q学习最终得到的系统代价在0.3952附近波动，而ASR-Q最终收敛在0.3866左右。相比之下，ASR-Q得到的最终代价更接近第二章中策略迭代算出的理论最优值0.3755。
第三章随机批调度问题的Q学习方法研究27图3.3加工时间随机时系统平均代价优化曲线Fig3.3Optimizationcurveofaveragecostsinstochasticprocessingtime从图3.3可以看出，在加工时间随机情况下，Q学习与ASR-Q的差距明显加大，ASR-Q最终收敛于0.9075左右，而Q学习最终得到的代价却只有0.9632左右，同样是ASR-Q算法最终得到的值更加接近于第二章中策略迭代算出的理论最优解。这中情况是由于当系统不确定性增加后，环境反馈的随机性增大，导致算法学习能力出现一定程度上的下降，如果这时在较大的行动集合中搜索，很容易陷入到较差的局部最优解中。同时可以看出，无论是在随机还是确定加工时间环境下，ASR都能效剔除系统中性能较差的行动，加快算法搜索速度，这种方法使得Q学习对缩减后的行动空间探索更加充分有效的提升了求解质量。因此，ASR-Q算法相比于比原始Q学习算法，其效果更好，收敛速率更快，得到的系统平均代价也更低。将ASR-Q与策略迭代算法对比可以发现，策略迭代可以求得系统的最优调度策略，但是这种方法需要在对MDP问题精确建模的前提下使用，而且需要对系统中的所有可选动作计算系统矩阵，对于规模较大的问题，这种计算将耗费大量时间。此外，复杂不确定的现实环境也使建立问题精确数学模型的工作变的具有挑战性。然而与模型无关的ASR-Q算法可以有效克服“建模难”的问题，虽然没有像策略迭代那样得到最优解，但是通过不断的学习优化可以得到一个良好的近优调度策略。同时，在当前规模下策略迭代算法的计算耗时极长达到了90分钟以上，而ASR-Q在确定性加工时间算例的学习步数设定下，完成2000次迭代所需时间仅为80秒左右，在加工时间随机情形下，学习步数变大，所需时间也只要210秒左右。接下来比较Q学习和ASR-Q在系统加工率上的
【参考文献】：
期刊论文
[1]批处理机上具有两类释放时间的工件集竞争调度问题[J]. 赵晓丽,宫华,车平. 自动化学报. 2020(01)
[2]对工业4.0背景下的智能制造的回顾[J]. 钟润阳,徐旬,Eberhard Klotz,Stephen T.Newman. Engineering. 2017(05)
[3]差异容量平行批机器环境下基于弱选择约束的调度算法[J]. 贾兆红,杨洋,张以文. 控制与决策. 2018(08)
[4]两类品种工件混流的多站点CSPS系统优化控制[J]. 唐昊,李博川,王彬,谭琦. 控制与决策. 2017(09)
[5]带退化效应多态生产系统调度与维护集成优化[J]. 杨宏兵,沈露,成明,陶来发. 计算机集成制造系统. 2018(01)
[6]深度强化学习综述[J]. 刘全,翟建伟,章宗长,钟珊,周倩,章鹏,徐进. 计算机学报. 2018(01)
[7]智能制造——“中国制造2025”的主攻方向[J]. 周济. 中国机械工程. 2015(17)
[8]基于强化学习的订单生产型企业的订单接受策略[J]. 王晓欢,王宁宁,樊治平. 系统工程理论与实践. 2014(12)
[9]基于数据的生产过程调度方法研究综述[J]. 刘民. 自动化学报. 2009(06)
[10]极小化最大完工时间的单机连续型批调度问题[J]. 赵玉芳,唐立新. 自动化学报. 2006(05)
本文编号：3621419
【文章来源】：合肥工业大学安徽省211工程院校教育部直属院校
【文章页数】：80 页
【学位级别】：硕士
【部分图文】：
差异工件随机到达Fig2.1Systemmodelofbatchprocessingmach本文的建模背景是半导体生产线中的
合肥工业大学硕士学位论文26件参数下ASR-Q对于原Q学习算法的优化情况，最后在第四部分对ASR算法是否会将系统最优行动删除的情况进行了分析。本节仿真实验均通过MATLABR2016a实现，实验中的系统参数设置与第二章中相同。3.3.1系统优化效果Q学习和ASR-Q每迭代一次，即对当前学到的调度策略的性能进行一轮仿真评估，每轮评估利用当前学到的策略独立进行10次50万步的仿真，取平均值作为当前策略对应的系统代价，同时为了体现系统的随机性，每次仿真数据均根据分布函数随机生成。在上述参数设置下，针对系统加工时间确定和随机两种情况，Q学习和ASR-Q对应的系统平均代价优化曲线如图3.2，3.3所示。图3.2加工时间确定时系统平均代价优化曲线Fig3.2Optimizationcurveofaveragecostsincertainprocessingtime如图3.2所示，Q学习在前期不断的试错探索，曲线波动较为明显，随着学习步数的增加，系统代价逐渐收敛并稳定。学习后期的小幅波动是由于在每次评估中，工件的到达时间和加工时间均是按照分布函数随机生成的，因此每次评估生成的数据都有所不同，这也使得相同策略得到的代价评估会在一定范围内小幅波动。由于使用ASR方法有效缩减了行动空间，可以看出ASR-Q在刚开始就可以得到质量较高的解，因此ASR-Q的收敛速率要明显快于原始算法。同时，随着学习步数的增加，在加工时间确定情况下Q学习最终得到的系统代价在0.3952附近波动，而ASR-Q最终收敛在0.3866左右。相比之下，ASR-Q得到的最终代价更接近第二章中策略迭代算出的理论最优值0.3755。
第三章随机批调度问题的Q学习方法研究27图3.3加工时间随机时系统平均代价优化曲线Fig3.3Optimizationcurveofaveragecostsinstochasticprocessingtime从图3.3可以看出，在加工时间随机情况下，Q学习与ASR-Q的差距明显加大，ASR-Q最终收敛于0.9075左右，而Q学习最终得到的代价却只有0.9632左右，同样是ASR-Q算法最终得到的值更加接近于第二章中策略迭代算出的理论最优解。这中情况是由于当系统不确定性增加后，环境反馈的随机性增大，导致算法学习能力出现一定程度上的下降，如果这时在较大的行动集合中搜索，很容易陷入到较差的局部最优解中。同时可以看出，无论是在随机还是确定加工时间环境下，ASR都能效剔除系统中性能较差的行动，加快算法搜索速度，这种方法使得Q学习对缩减后的行动空间探索更加充分有效的提升了求解质量。因此，ASR-Q算法相比于比原始Q学习算法，其效果更好，收敛速率更快，得到的系统平均代价也更低。将ASR-Q与策略迭代算法对比可以发现，策略迭代可以求得系统的最优调度策略，但是这种方法需要在对MDP问题精确建模的前提下使用，而且需要对系统中的所有可选动作计算系统矩阵，对于规模较大的问题，这种计算将耗费大量时间。此外，复杂不确定的现实环境也使建立问题精确数学模型的工作变的具有挑战性。然而与模型无关的ASR-Q算法可以有效克服“建模难”的问题，虽然没有像策略迭代那样得到最优解，但是通过不断的学习优化可以得到一个良好的近优调度策略。同时，在当前规模下策略迭代算法的计算耗时极长达到了90分钟以上，而ASR-Q在确定性加工时间算例的学习步数设定下，完成2000次迭代所需时间仅为80秒左右，在加工时间随机情形下，学习步数变大，所需时间也只要210秒左右。接下来比较Q学习和ASR-Q在系统加工率上的
【参考文献】：
期刊论文
[1]批处理机上具有两类释放时间的工件集竞争调度问题[J]. 赵晓丽,宫华,车平. 自动化学报. 2020(01)
[2]对工业4.0背景下的智能制造的回顾[J]. 钟润阳,徐旬,Eberhard Klotz,Stephen T.Newman. Engineering. 2017(05)
[3]差异容量平行批机器环境下基于弱选择约束的调度算法[J]. 贾兆红,杨洋,张以文. 控制与决策. 2018(08)
[4]两类品种工件混流的多站点CSPS系统优化控制[J]. 唐昊,李博川,王彬,谭琦. 控制与决策. 2017(09)
[5]带退化效应多态生产系统调度与维护集成优化[J]. 杨宏兵,沈露,成明,陶来发. 计算机集成制造系统. 2018(01)
[6]深度强化学习综述[J]. 刘全,翟建伟,章宗长,钟珊,周倩,章鹏,徐进. 计算机学报. 2018(01)
[7]智能制造——“中国制造2025”的主攻方向[J]. 周济. 中国机械工程. 2015(17)
[8]基于强化学习的订单生产型企业的订单接受策略[J]. 王晓欢,王宁宁,樊治平. 系统工程理论与实践. 2014(12)
[9]基于数据的生产过程调度方法研究综述[J]. 刘民. 自动化学报. 2009(06)
[10]极小化最大完工时间的单机连续型批调度问题[J]. 赵玉芳,唐立新. 自动化学报. 2006(05)
本文编号：3621419
本文链接：https://www.wllwen.com/guanlilunwen/lindaojc/3621419.html
