第3期 王国磊，等：面向多机动态调度问题的两层Q学习算法 241 5+1下可采取的动作；显然mrx(Q(s+1,b)表示的 习还有2种虚状态，即缓冲区内没有作亚或者只有 是状态5+1下采用不同动作所能得到的最优奖励 一道作业，这种情况下无须进行调度规则的选取. 值.Q学习的步骤如表2所示. 1)设备利用率因子F.即t时刻前设备占用 表2Q学习步骤 时间和总可用时间的比值，如式(3)所示. Table 2 Steps of Q-learning FIR =1/t. (3) 步骤 方法 式中：。表示t时刻前设备的有效利用时间 初始化聚类中心向量以及所有状态-动 2)作业紧张程度因子T.即t时刻缓冲区内 作对的Q值 作业的平均拖期期望，如式(4)所示， 2 观察当前系统状态sr m=(e+)-, N台 (4) 3 根据&-e6dy策略选择动作a, 式中：N。表示缓冲区内作亚数目.而每个状态的范 执行动作a,观察奖惩值r(s,a,)和下 4 围则由缓冲区内的作业平均加工时间 一个状态3+ N 根据式(2)更新状态-动作对值 1∑4 T-N.t (5) 令s,=3+1并返回步骤2，直到该episode 乘以系数x确定， 结束。 100 重复执行一定数量的episode,直到学习 S13)S14)S15)S16S17)S18) 7 过程完成 9(0 2.2底层强化学习 S7) 58) S9)S10:S11)S12) 底层Q学习的目的是使MA能够根据缓冲区 装 80 状态选择最优的调度策略，从而达到最小化机器空 S1) S72) S3) S4S5)S6) 闲和作业平均流经时间的局部目标。 2.2.1动作集 2 为此，文中选用了常见的3种调度规则作为设 平的证迟期望MPT 备Agent的动作集，如表3所示. 图2底层Q学习的状态空间划分 表3设备Agent的动作集 Fig.2 State space division of bottom level Q-learning Table 3 Action set of equipment agent 2.2.3奖惩函数设计 规则 说明 综合考虑设备利用率和作亚业拖期2项因素，奖 EDD 最小交货期原则，即选择缓冲区 励函数设计如表4所示.以奖励类别1为例，其含义 (earliest due date) 内具有min(T)的作业 为如果当前状态s,的设备利用率小于0.8，并且A get动作使缓冲区内剩余工序的平均延迟期望增 SPT 最短加工时间原则，即选择缓冲 大，设备利用率提高，那么该动作的立即奖惩为5. (shortest processing time)区内具有min(L:)的作业 表4底层Q学习奖惩函数 FIFO 先到先服务原则，即选择缓冲区 Table 4 Reward function of bottom level O-learning (first in first out) 内具有min(Tr)的作业 奖励类别 判别标准 奖惩 2.2.2状态划分 1 F<0.8 F才，EFm入 r=5 状态空间的划分是合理选择调度规则的基础， 2 <0.8 Fm万，5mr=10 状态范围的划分应尽可能细化，且尽可能使系统所 Fm<0.8 Fm,Fn不 r=-10 4 F<0.8 FR,FT=-5 处的状态在各个范围分布比较均衡.通过大量仿真 0.8≤F<0.9 F不，Fn才r=-1 试验，本文确定了基于两种特性指标的状态划分策 0.8≤Fm<0.9 Fm才，FT=10 略，如图2所示，共分为18种状态此外，底层Q学