2018-B2：基于多原则比较和蒙特卡洛模拟的 RGV 动态调度模型

杨利霞

2018-B2：基于多原则比较和蒙特卡洛模拟的 RGV 动态调度模型

本文从规划模型、多原则求解的角度，综合了蒙特卡洛模拟与机器学习的思
" f. J3 r1 L& b/ R' P( i8 b8 N想，研究了由 8 台 CNC、1 辆 RGV 以及其他附属设备组成的智能加工系统的动
态调度问题，并给出了不同工序情况下的具体调度方案。
* Q8 J$ W& \0 _1 T9 B: t8 p8 b针对情况一：单工序的作业流程较为简单。首先，利用规划的各个约束条件，
$ l) w4 h" q2 h4 N4 S刻画了 RGV 在 CNC 之间的运动过程、单个物料的加工过程、“上下料”时 RGV
, K% n( h8 F& |6 x2 ]+ I手爪的旋转过程、清洗作业的过程、RGV 移动至下一个机床进行加工的过程等
2 Q/ B- C0 x, j: K7 q8 w' L等。此外，还刻画了物料加工与运送的“唯一性”，以及利用 0-1 变量构造的目
/ R. [, \9 y1 i. C$ ~5 k标函数。规划的目的是，在给定的时间内，使得加工出的物料数量最多。然而，
" [- _4 j7 [# J- y; [2 ?8 N% K这样的规划是一个 NP 问题，无法通过传统的方法求解，所以进而寻求模拟的方
5 j/ N0 ?4 ^) u- {& @' c% Q9 n- g, F法求得局部最优解。
本文选取了“就近原则”——构造时间代价函数，“FIFO 原则”——考虑各
台 CNC 的等待时间，以及“HRRN 原则”——将时间代价与等待时间进行综合
: S0 |& k- U$ P考虑，分别对情况一进行了模拟。事实上，每种原则的结果相同：第一组数据加
9 x" a* A3 a9 ~4 M3 C$ o% _4 A工完成了 383 件物料，第二组数据加工完成了 360 件物料，第三组数据加工完成
0 r- i9 P' t$ _% Y3 \% X; ?- s了 393 件物料。并且，调度的方案全部为 1→2→…→8→1→… 此外，第三组数
据的系统效率最高，为 49.125 件/h.
- C  x# S7 ]- Z: o6 _9 B! |7 |" p3 P针对情况二：双工序的作业流程十分复杂。首先，在情况一的基础上，对规
& M/ |9 l; |7 m$ M: q! h  p( J8 z划的各个约束条件进行修正；并着重刻画了 RGV 移动至下一个机床进行加工的
过程。
3 J" ^8 m! d( R此外，双工序流程中各台 CNC 所负责的工序也是不确定的；因此，本文对
/ B& E% ?$ d. t# R256 种工序布局方案，结合三种选取原则，进行了遍历。得到的结果是：第一组
$ ]: g; `5 F! {0 W$ n, Z+ U8 D数据的各台 CNC 最优工序分配为 1-2-1-2-1-2-1-2，三种原则结果一致，最终加工
( E5 K# ^* \2 L" [出 253 件物料；第二组数据的各台 CNC 最优工序分配为 2-1-2-1-2-1-2-1，“FIFO
3 m- J* f7 u; w( A' j原则”和“HRRN 原则”更优，最终加工出 212 件物料；第三组数据的各台 CNC
最优工序分配为 1-1-2-1-2-1-1-2，“就近原则”最优，最终加工出 241 件物料。此
7 X8 f0 t# e  k" ]% Q2 b外，所有的调度方案均呈现有规律的循环状态。
, H* I1 e3 Y+ }然后，利用“基于蒙特卡洛的学习算法”，在构造正反馈的前提下“随机”
地尝试以获得更优解。结果反映了，三种原则中的最优原则，已非常接近全局最
# V. i+ U- d, G! t) d优。此外，第一组数据和第三组数据的作业效率一样高，均为 30.125 件/h.
针对情况三：同时考虑单工序流程与双工序流程。构造了随机变量“是否故
障”、“故障发生时间”和“故障排除时间”，并将它们融合进入规划模型。求解
+ d+ Y8 O$ k0 s) X+ `8 ^+ c结果显示，遭遇故障后，单工序流程系统效率最多下降了 2.25 件/h，而双工序流
程系统效率最多下降了 1.875 件/h.
) ]" V/ y, Y9 p) @- C本文的亮点在于：首先，利用一般化的公式对系统调度进行了较为细致的机
) [/ \+ E4 v2 R! V5 d理分析，使得模型具有普适性；其次，给出了多个调度原则相互比较，从而有利
于结果更优；最后，将蒙特卡洛模拟与机器学习的思想相结合，对上述调度原则
2 V6 J# @& M: X7 e' F  p% J的有效性进行验证，增强了模型的说服力。

8 X8 x+ y! L/ c' U4 W
- w  x  m( Y6 e0 d
% d2 }  w( O9 P$ r( y! |, f4 Q