Dynamic Scheduling Strategy of RGV in Ring Intelligent Processing System
袁梦婷 YUAN Meng-ting；杨碧容 YANG Bi-rong；孙瑞 SUN Rui；吕平 LYU Ping
（杭州师范大学理学院，杭州 311100）
（School of Science，Hangzhou Normal University，Hangzhou 311100，China）
摘要：基于MDP理论，将“RGV执行并完成任务所需时间”构建为动态优先级，引入随机变量“CNC发生故障和排除故障的时间”，结合RGV、CNC、物料的状态变化情况，建立基于MDP理论的状态转移模型。并在数值迭代算法的基础上设计了MDP迭代寻优算法对三组系统进行求解，从而得到一道工序物料加工过程中，CNC有1%的概率发生故障的情形下环形智能加工系统在未知动态环境下的最优调度策略。
Abstract: Basing on the MDP theory, we construct the time of RGV to execute and complete the task as the dynamic priority, and introduce two random variables, the time when the CNC is faulty and the fault is removed. At the meanwhile, combining with the state changes of RGV, CNC and materials, we establish a state transition model based on MDP theory. Then, based on the numerical iterative algorithm, the MDP iterative optimization algorithm is designed to solve the three groups of systems, so that the optimal scheduling strategy of the intelligent processing system in an unknown dynamic environment during the processing of a process material with a 1% probability of failure in the CNC is obtained.
关键词：MDP理论；动态优先级；迭代寻优算法；动态调度最优策略
Key words: MDP theory；dynamic priority；iterative optimization algorithm；dynamic scheduling optimal strategy
中图分类号：TP273 文献标识码：A 文章编号：1006-4311（2019）27-0043-03
0 引言
随着当今世界科学技术的蓬勃发展，现代物流观念渐渐深入人心。为解决庞杂的物流问题，自动化物流系统开始兴起，然而如何合理地设计智能加工系统的调度策略从而提高效率是自动化系统的核心。如今，已有大量研究者致力于解决RGV的动态调度策略。张桂琴等[1]设计了RGV的智能调度算法和避碰防撞算法，解决了2辆RGV的相向碰撞和同向追尾问题；沈艳等[2]针对网络控制系统中采样周期时变不确定性对控制和运行性能的影响，提出了基于反馈控制原理和预测机理的动态调度策略；查振元等[3]着重分析了RGV的应用。这些虽然给出了很多解决各种情况下的调度策略，但是没有对实际加工情境进行分析。因此本文主要以图1所示的环形智能加工系统为例（RGV固定逆时针移动），研究一道工序物料加工过程中，CNC有1%的概率发生故障的情形下环形智能加工系统在未知动态环境下的最优调度策略。
1 基于MDP理论的状态转移模型
1.1 状态分析
本文将系统端视为观察者，RGV视为决策者，以RGV执行并完成任务所需时间为动态优先级，时间越短优先级越高为决策依据，使RGV做出决策并执行任务，从而使各CNC的运转状态发生改变。并以RGV位于CNC1#和CNC2#正中间，所有CNC都处于空闲状态为初始状态，分别对物料、CNC及RGV的状态进行分析。
1.1.1 物料在t时刻的状态信息
首先，对物料按加工顺序进行编号，记为Tj，j=1，2，…，n，则物料Tj在t时刻的状态信息可表示为■。其中，uj为物料Tj上料的时刻，dj为物料Tj下料的时刻。
1.1.2 CNC在t时刻的状态信息
■，i=1，2，…，8
其中，ei为第i个CNC的加工时间；wi为第i个CNC一次上下料所需时间；Pi为第i个CNC的工作状态，Pi=1表示正在加工物料，Pi=0表示Ci处于空闲状态；gi为第i号CNC的机器状态，gi=1表示CNC运转出现故障，gi=0表示CNC运转状态良好。
1.1.3 RGV在t时刻的状态信息
RGV在t时刻的状态信息可表示为■。其中，A为RGV的位置矩阵，表示RGV所处的位置，若RGV处于CNC1#和CNC2#正中间，则记A=（1 0 0 0）；φ为完成一个物料的清洗作业所需时间，是一个定值；xi为RGV的机床选择决策变量，xi=1表示RGV选择机床Ci加工，xi=0表示RGV不选择机床Ci。
由于在加工过程中，我们无法判断CNC何时出现故障，因此对它设定随机变量ε1，其范围为0到对应CNC加工一个物料所需时间，使CNC在加工过程中的某个时刻出现概率为1%的故障，无法正常加工。同理，由于故障排除时间在10~20分钟内，我们无法确定每次故障排除的准确时间，因此再设定随机变量ε2，其范围为600s至1200s，使CNC发生故障后的10~20分钟的某个时刻恢复正常运转状态。
1.2 建立模型
1.2.1 动态优先级的构建
为提高系统工作的效率，本文建立RGV执行并完成任务所需时间T为其决策的动态优先级，RGV将在发出信号的CNC数量大于1时根据动态优先级进行判断，并做出决策，T越小，优先级越高，任务越先被执行。
其中，T由RGV与任务点间的距离及对应CNC所需上下料时间wi所决定。而RGV与任务点间的距离通过RGV与发出信号Ci相距的单元数h来体现，RGV连续移动不同单元数对应着不同时间。于是，我们建立映射关系f，将距离转化为时间，
■
H={0，1，2，3}为RGV与发出信号Ci相距单元数的集合，即在环形结构中，RGV从两CNC正中间的位置逆时针移动到相邻两CNC正中间的位置为1个单元数，M为RGV连续移动相应单元数所需时间ti的集合，进而有
■
最终我们便可建立RGV决策的动态优先级：T=ti+wi。
1.2.2 状态转移模型
结合实际情况，我们假设RGV一旦做出决策，在执行完此任务前决策不会发生改变。同时，假设从开始作业至t时刻已加工物料（包括正在加工物料）的数量为n，根据MDP理论，可将任务分配策略矩阵D（t）表示为一个8×n的矩阵[4]，该矩阵体现了每个CNC相对于每个物料的策略选择：
■
其中，δij为第j个物料在机床Ci上的加工情况，δij=0表示第j个物料不在Ci上加工，δij=1表示j个物料在Ci上加工。同时，由于一个任务只可能被一台机床加工，故矩0阵的每一列仅可能有一个数值为1，其余数值为0，进而存在约束条件■。基于约束条件，结合动态优先级和任务分配策略矩阵，便可通过一定的算法求解得到智能加工系统的RGV最优动态调度策略。
1.3 模型求解
1.3.1 模型的求解算法——MDP迭代寻优算法
由于智能加工系统处于一个动态变化的过程，因此每一次决策的任务分配都会影响到整个系统的总体效率，为了满足加工系统动态任务分配的快速性要求，根据MDP最优策略的存在性判定定理[5]，我们所建立的基于MDP理论的状态转移模型一定存在最优策略，可用数值迭代算法进行求解。结合本文实际情况，我们在数值迭代算法的基础上进行优化，设计了MDP迭代寻优算法。此算法在迭代的过程中可计算出在可能发生故障的情况下，RGV每次分配任务后整个系统的状态，最终求解出最优动态调度策略。
1.3.2 求解结果
考虑CNC可能会发生故障的情况，依据基于MDP理论的状态转移模型，结合MDP迭代寻优算法，利用相关系统作业参数，我们通过MATLAB软件，求解得到一道工序物料在有故障情形下RGV的最优动态调度策略。（表1）
1.3.3 敏感性分析
由于CNC发生故障情形中存在随机变量，使得结果在每次算法的运行后都不一样，因此本节主要分析本文中基于MDP理论的状态转移模型的敏感性。又由于不同故障数对结果影响大致相同，故在此我们以第1组为例进行具体分析。
给予清洗时间在[-1，1]范围内以0.1为间隔的误差，运用MATLAB软件，将结果绘制成折线图，从而更清晰得反映结果的变化，如图2所示。
观察图2可以发现，参数的误差对模型的结果有一定的影响，但是影响程度较小，即模型的敏感性较低，从而证明了基于MDP理论的状态转移模型具有较高的可靠性。
2 结论
对比智能加工系统实际应用情况[3]，可以发现我们求解得到的结果具有一定的实际性和正确性，证明了建立的基于MDP理论的状态转移模型的实用性及MDP迭代寻优算法的有效性。
本文的特色与创新点在于，巧妙地利用了MDP马尔可夫周期性和连续性的性质，并在此基础上构建动态优先级，建立状态转移模型，同时结合迭代寻优算法对问题进行求解。
参考文献：
[1]张桂琴，张仰森.直线往复式轨道自动导引车智能调度算法[J].计算机工程，2009，35（15）：176-178，181.
[2]沈艳，郭兵.网络控制系统变采样周期智能动态调度策略[J].四川大学学报（工程科学版），2010，42（01）：162-167.
[3]查振元，李计星，绳润涛，张丰华，李昌臣.智能平移轨道导引车的应用[J].机器人技术与应用，2017（05）：42-43.
[4]陈明，周云龙，刘晋飞，靳文瑞.基于MDP的多Agent生产线动态调度策略[J].机电一体化，2017，23（11）：15-19，56.
[5]郑少慧.一类连续时间平均马氏决策平稳最优策略的存在性[J].应用数学学报，1989（02）：250-256. |
