第4卷第3期 智能系统学报 Vol.4 No.3 2009年6月 CAAI Transactions on Intelligent Systems Jn.2009 doi:10.3969/j.issn.16734785.2009.03.008 面向多机动态调度问题的两层Q学习算法 王国磊，钟诗胜，林琳 (哈尔滨工业大学机电工程学院，黑龙江哈尔滨150001) 摘要：对于单机动态调度问题十分有效的Q学习，在多机动态调度环境下却由于峡乏全局眼光而效果欠佳，因此 提出了一种双层Q学习算法.底层Q学习着眼于局部，以最小化设备空闲和作业平均流经时间为目标，学习单机调 度策略；而顶层Q学习则若眼于全局，以平衡机器负载、最小化整体拖期值为目标，学习如何分配作业到合适机器. 文中分别给出了两层Q学习的动作集、状态空间划分方式和奖惩函数设计，并通过对多机动态调度问题的仿真实验 表明，提出的双层Q学习能够很好地解决改善动态环境下多机调度问题. 关键词：动态多机调度；Q学习；动作集；状态空间划分；奖惩函数 中图分类号：TP273文献标识码：A文章编号：16734785(2009)03023906 Bi-level Q-learning algorithm for dynamic multi-machine scheduling problems WANG Guo-lei,ZHONG Shi-sheng,LINLin (School of Mechanical Engineering,Harbin Institute of Technology,Harbin 150001,China) Abstract:Traditional Q-learning is very effective in dynamic single-machine scheduling problems,yet sometimes it cannot get optimal results for dynamic multi-machine scheduling problems due to its lack of global vision.To re- solve this,a two-layer Q-leaming algorithm was put forward.The bottom-level of Q-learning was focused on local- ized targets in order to leam the optimal scheduling policy which can minimize machine idleness and the mean flow time of single machines.On the other hand,the top-level of Q-learing was focused on global targets in order to find the dispatching policy which can balance machine loads and minimize the overall tardiness of all jobs.The scheduling and dispatching rules of agents,the method for dividing state space and the reward functions were all ex- amined.Simulation results showed that the proposed two-layer Q-learning algorithm can improve the results of dy- namic multi-machine scheduling problems. Keywords:dynamic multi-machine scheduling;Q-learning;action set;state space division;reward function Q学习是一种典型的强化学习方法，它不需要应用于车间动态作业调度[6]，其后王世进等人也分 建立任何领域模型，而是直接优化一个可迭代计算 别对利用Q学习算法实时选择调度规则进行了研 的Q函数，获得最优控制策略.近年来，Q学习得到 究7).这些研究表明，Q学习能够使智能体从给定 了研究人员的广泛重视)，但其应用目前还主要集 的调度规则中选择出较好的调度规则， 中在游戏比赛、控制系统和机器人领域，在作亚排序 但是，这些研究还都仅限于单机调度问题.对于 问题上的应用尚不多见2.比较经典的研究有： 多于多机动态调度问题，如果仍然将每台机器视为 Aydin等人利用Q-Ⅲ算法训练智能体动态选择调 Agent,.利用Q学习根据各自的局部目标选择调度策 度规则3)，Wag等人将强化学习应用于动态单机 略，那么往往会因为缺乏全局眼光而不能达到最优 调度研究4国内学者中魏英姿最早将强化学习 效果.因此，本文进一步设计了符合多机动态调度问 题特点的双层Q学习机制，以保证整个系统的行为 收痛日期：2008-10-03. 能朝着预期的方向演化. 基金项目：国家“863”计划资助项目(2008AA04Z401), 通信作者：王国磊.E-mail:Wan阳l_hit@163.com
·240 智能系统学报 第4卷 机器Agent(machine Agent,MA)按照某种优先规则 1自适应多Agent动态调度模型 对缓冲中的作业进行加工，并且每完成一道工序都 1.1多机动态调度问题 要向JA报完工，以便JA将其后续工序添加到全局 动态多机调度问题可以描述为：某车间或工厂 缓冲中；如果发生设备故障等异常，MA将其缓冲中 有加工设备若干台，生产作业随机到达，当某时刻调 待加工作业退回给JA,由JA将其置于全局缓冲中 度环境变化导致需要进行动态调度时，则生成新的 重新分配. 预调度方案，并根据新的方案生产直到新的随机事 外部动态满度环境 件发生或者所有加工任务结束. 作业 选择 添加 到达 为了便于描述，某车间的加工设备集合为{M1, 作业 作业 分Agent 缓冲 作业Agent M2,…,Mm},生产作业集合为{J,J2,…,Jn}.作业 分配 完工 J:到达的时间为T,截止时间为T,拖期完成时单 机器 报微障 位时间的拖期惩罚为C.作业J:包含n:道工序，由 机器 机器 于实际生产中加工设备具有一定的可替换性；因此 缓冲 缓冲 工序Og有若干台可用机器集合，在机器M。上的加 选择作业 选择作业 选择作业 安排加T 安排加上 事安排加下 工时间用1表示.此外，工序O的时间要素可以用 机器Agent 机器Agt 机器Agent 六元组[會，，，，，]表示，其中：會表示 由作业到达时间推算出的工序最早可能开始时间， 图1基于Q学习的多Aget动态调度机制 T表示由作业截止时间推算出的工序最迟必须结束 Fig.1 Q-learning based multi-agent dynamic scheduling 时间，T为每次预调度中工序的开始时间，T为每 mechanism 次预调度中工序的结束时间，为工序的实际开始 2 双层强化学习机制 时间，T为工序的实际结束时间. 1.2建模 针对上述调度机制，提出了一种基于Q学习的 针对前述多机动态调度问题，建立了一个多A 双层强化学习机制，用于指导DA的机器分配和MA gent动态调度模型，模型中包括的几种主要Agent 的作业选择 及其功能如表1所示。 2.1Q学习算法 表1 Agent定义 Q学习算法最早由Watkins在1989年提出，是 Table 1 Agent definition 目前最有效的模型无关强化学习算法之一，其基 Agent种类 功能 本形式如式(1)~(2)所示： 以最小化设备空闲、平均流经时间为 机器Agent Q(s,a,)=r(s,a,）+y∑P(a)· 目标，调度缓冲区内任务 41后5 max(Q(s1,6)), (1) 以平衡设备使用、最小化作业的整体 分配Agent Q(s,a,)=(1-a)Q(s,a)+a(r(s,a)+ 拖期值为目标，分配作业到合适机器 y max((s1,6)). (2) 管理作业，根据报完工情况和设备故 作业Agent 式中：Q(s,a,)表示Agent在状态s,下采用动作a, 障情况调度后续工序进人全局缓冲 所获得的总计期望奖惩，也称为状态-动作对值； 如图1所示，这个动态调度模型的工作原理是： r(s,a,)表示Agent在状态s,下采用动作a,所获得 如果某时刻有新作业到来，则动态生成非永久型的 的即时奖惩；P41(a)表示在状态s,下采用动作a: 作业Agent(job Agent,JA),JA将作业的首工序添 转入状态s,+1的概率；y为未来奖惩的折扣系数，有 加到全局缓冲中；分配Agent(dispatching Agent, 0≤y≤1，y越接近于0，Agent越不考虑长远，更趋 DA)感知到全局缓冲中有工序进人则立即开始调 于接收即时奖惩，y越接近于1，Agent则越具有远 度，根据某种规则将作业分配到合适机器的缓冲中； 见，能减少即时奖惩对学习策略的影响；b为状态
第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学
242. 智能系统学报 第4卷 续表4 可用机器上的最短可能加工时间和最长可能加工时 奖励类别 判别标准 奖惩 间的比值.此外顶层Q学习还有一种虚状态，即对 7 0.8≤Fm<0.9 F,Fm入 r=-10 于某道作业来说，其可用机器只有1种. 96 0.8≤Fm<0.9 Fin,FT r=1 2.3.3奖惩函数设计 9 0.9≤Fm Fm才，Fm入 r=-5 DA着眼于提高系统的整体性能，因此本文提 10 0.9≤Fm 万，m￥r=l0 出了2种特性指标衡量Agct的动作奖惩，以便综 11 0.9≤Fm F,FT才 r=-10 合考虑所有机器上任务的拖期完成情况以及所有机 12 0.9≤Fm FB,FEACT T=5 器的负载平衡情况， 1)平均作业拖期期望FT.即DA动作后，所有 2.3 顶层强化学习 机器都按照当前最优原则，将缓冲区内的作业安排 由于设备可替换性的存在，DA的主要任务是 加工后所有作业的平均拖期期望，如式(6)所示， 将全局缓冲中的任务分配到合适的机器，因此顶层 Q学习的设计就是为了使DA能够根据当前作业的 特征以及各可用机器的负荷合理选择加工机器. max(对-，0)). (6) 2.3.1动作集 2)负载平衡因子F.即所有机器的利用率的 DA的动作集采用表5所示的3种调度规则. 方差，如式(7)所示. 表5分配Agent的动作集 Table 5 Action set of dispatching agent F=1.(E-F). Nm (7) 规则 说明 式中F表示机器利用率均值。 ML 最小负载原则，即选择缓冲区内 基于以上2种指标，设定DA的奖惩值如表6 minimum load) 作业最少的机器 所示.以奖励类别1为例，如果DA的动作使负载平 SPT 最短加工时间原则，即选择使任 衡因子变大，并且平均作业拖期期望减小，那么DA (shortestpctime)务加工时间最短的机器 收到的立即奖惩为1. MFR 最小故障率原则，即选择故障率 表6顶层Q学习奖惩函数 (minimm failure rate) 最低的机器 Table 6 Reward function of top level Q-learning 2.3.2状态划分 奖励类别 判别标准 奖惩 1.00 FRB FEMT r=1 S(13) S(14) : S(15) S(16) … 2 Fm为 FBMT 0.75 r=-2 S(9) 7 S(10) (11) S(12) F4 FEMT r=2 0.50 7” 8 FEMT r=-1 S(5》 S(6) S(7) S(8) 0.25 …月 3 仿真实验 S(1) S(2) S(3) S(4) 为了对提出的双层Q学习算法进行验证，构建 0.25 0.50 0.75 1.00 了如下动态调度仿真模型.系统由M台不同机器组 Lwn/Lax 成，从0时刻开始，作业随机进入系统缓冲区，每完 图3顶层Q学习的状态空间划分 成N个作业称为1个episode..相邻2个作业到达系 Fig.3 State space division of top level Q-learning 统的时间间隔服从均值为I的指数分布，每个作业 如图3所示，顶层Q学习的状态空间以L 包含的工序数目从[a1,a2]之间随机选取，每道工序 Lmm和F/F为横纵坐标划分为16种，其中： 的加工时间从[b1,b2]之间随机选取，每道工序随机 F/F表示该作业的可用机器集中机器的最小负 选择[c1,c2]种可用加工设备，作业的拖期惩罚金C 载和最大负载的比值；Ln/Lr表示该作业在所有 服从均匀分布U(d,d2).每个作业的交货期为
第3期 王国磊，等：面向多机动态调度问题的两层Q学习算法 .243 T母=+f: (8) 分配的顶层Q学习后，系统性能得到了进一步的改 式中：为交货因子，服从均匀分布U(e,e2).作业 善.究其原因，是因为顶层Q学习的引入使得分配 的最早开始时间为 到各加工机器的作业更合理、平衡，从而避免了不同 T=+f: (9) 机器的忙闲不均.为了说明这一现象，以案例1为例 式中：为开始因子，服从均匀分布U(2) 对单层Q学习和双层Q学习在调度过程中的机器 表7仿真实验参数 负载分布情况进行比较.即对10O0个episode进行 Table 7 Parameters of simulation experiment 仿真，每10个episode对机器利用率的方差进行计 取值 算，结果如图4所示.可以看出，双层Q学习算法使 参 数 案例1 案例2 案例3 案例4 得机器利用率的方差减小，也就是说各机器的利用 意义 HL/TD HL/LD LL/TD LL/LD 率更加接近、更加均衡 M 10 10 10 10 0.042 ·双层0此习 N 1000 1000 1000 1000 0学为 0.04 11 11 12 12 [a1,a2] [6,10] [6,10] [6,10] [6,10] 0.040 [b1,b2] [10,20] [10,20] [10,20] [10,20] .39 [c1,9] [1,4] [1,41 [1,4] [1,4] 0.038: [d,d] [1,3] [1,3] [1,3] [1,3] 0.037 [e1,82] [2,2.5] [2,3.5] [2,2.5] [2,3.5] 0.03 [f6] 「0.0.51 「0.0.51 [0,0.51 「0.0.51 0 10*10 cpisode数 a 0.1 0.1 0.1 0.1 2 0.9 0.9 0.9 0.9 图4单层Q学习和双层Q学习的机器利用率对比 0.1 0.1 0.1 0.1 Fig.4 Machine utilization comparison of single-layer Q- 仿真实验中采用了4个案例以便比较全面地反 learning and two-layer Q-learning 映实际生产中常见的动态调度情形，各参数取值如 4 结束语 表7所示.表中HL的含义是高负载，即任务到来的 间隔较小，L的含义是轻负载，即任务到来的间隔 在单机动态调度问题中，Q学习已被证明可以 较大，TD的含义是交货期较紧，LD的含义是交货期 根据缓冲区状态自适应地选择合适的调度规则：但 较松.为了避免随机因素影响，对每个案例重复仿真 是在多机动态调度环境下，不但需要关注单个机器 实验10次，每次对1000个episode进行仿真，并将 的调度性能，还需要从全局角度考虑整体性能，否则 不同调度策略下得到的作业平均施期惩罚值列于 难以取得良好的调度效果.因此构建了包含机器A 表8之中 gent和分配Agent的多Agent动态调度模型，并提出 表8不同调度方法的平均拖期惩罚比较 了相应的两层Q学习算法.机器Agct利用底层Q Table 8 Average tardiness penalty comparison of different 学习优化局部调度性能，分配Aget利用顶层Q学 scheduling methods 习优化任务分配，从而达到优化整体调度性能的目 平均拖期惩罚 的.仿真试验表明，提出的两层Q学习算法能够明 机器选择/调度算法 案例1案例2案例3案例4 显地改善多机动态环境下的调度效果。 随机选择/SPT规则 94.178.482.268.9 将Q学习应用于动态调度还有许多问题值得 随机选择/EDD规则 103.775.370.859.7 进一步的研究和深入探讨，例如更合理状态特征的 随机选择/FIFO规则 112.586.469.362.7 提取、更有效的动作集、信息不完全情况下的强化学 随机选择/Q学习调度92.374.968.353.6 习，以及多Aget的合作强化学习等等 Q学习选择/Q学习调度84.470.364.148.1 参考文献： 可以看出，采用Q学习机制后，调度效果明显 强于采用某一固定的调度规则；而加入了面向机器 [1]严浙平，李锋，黄宇峰.多智能体Q学习在多AUV协
244 智能系统学报 第4卷 调中的应用研究[J].应用科技，2008,35(1)：5760. 策略研究[J].控制与决策，2007,22(12)：1335-1340. YAN Zheping,LI Feng,HUANG Yufeng.Research on ap- YANG Hongbing,YAN Hongsen.Adaptive strategy of dy- plication of multi-agent Q-learling in multiAUV coordina- namic scheduling in knowledgeable manufacturing system tion[J].Applied Science and Technology,2008,35(1): [J].Control and Decision,2007,22(12):1335-1340. 5760. [9]WATKINS C,DAYAN P.Technical note:Q-leaming[J]. [2]潘燕春，冯允成，周泓，等.强化学习和仿真相结合的 Machine Leaming,1992,8(3/4):279-292. 车间作业排序系统[J].控制与决策，2007,22(6)： 作者简介： 675-679 王国磊，男，1982年生，博士研究 PAN Yanchun,FENG Yuncheng,ZHOU Hong,et al.Re- 生，主要研究方向为生产计划和车间调 inforcement learning integrated with simulation for job-shop 度等，发表学术论文10余篇. scheduling system [J].Control and Decision,2007,22 (6):675679 [3]AYDIN M E,OZTEMEL E.Dynamic job-shop scheduling u- sing reinforcement learning agents[J].Robotics and Auton- 钟诗胜，男，1964年生，教授，博士 omous Systems,2000,33(2/3):169-178. 生导师.哈尔滨工业大学威海分校副校 [4]WANG Y C,USHER J M.Application of reinforcement 长、中国机械工程学会机械设计分会理 learning for agent-based production scheduling[J].Engi- 事、中国人工智能学会可拓学专业委员 neering Applications of Artificial Intelligence,2005,18 会常务理事、中国工程图学学会应用图 (1):73-82. 学专业委员会委员、全画工业自动化系 [5]WANG Y C,USHER J M.Learning policies for single ma- 统与集成标准化技术委员会委员、国防科工委信息技术应用 chine job dispatching[J].Robotics and Computer Integrat- 标准化技术委员会委员.主要研究方向为数字化设计与制 ed Manufacturing,2004,20(6):553-562. 造、人工智能理论与应用、数控设备研发等.国家863/CMS [6]魏英姿，赵明扬.强化学习算法中启发式回报函数的设 重大应用示范工程项目一“HEC-CMSⅡ工程”的副总设 计及其收敛性分析[J].计算机科学，2005,32(3)：190- 计师，主持国家自然科学基金项目2项、国家863计划项目2 193. 项，参与国家863计划项目1项、国家自然科学基金项目1 WEI Yingzi,ZHAO Mingyang.Design and convergence a- 项，承担欧盟科技计划项目（英国、中国、西班牙联合承担）1 nalysis of a heuristic reward function for reinforcement leam- 项，多项省（部）级科技项目和企业横向项目.曾获省部级科 ing algorithms[J].Computer Science,2005,32(3):190- 技进步二等奖1项、三等奖2项，专利1个和国家自主版权 193. 登记软件3套，被评为黑龙江省CIMS应用示范先进个人.发 [7]王世进，孙展，周炳海，等.基于Q学习的动态单机调 表学术论文140余篇，出版专著1部. 度[J].上海交通大学学报，2007,41(8)：1227-1232. 林琳，女，1973年生，副教授，硕士 WANG Shijin,SUN Sheng,ZHOU Binghai,et al.Q-leamn- 生导师.主要研究方向为智能设计和产品 ing based dynamic single machine scheduling[J].Journal 数据管理等发表学术论文20余篇。 of Shanghai Jiaotong University,2007,41(8):1227-1232. [8]杨宏兵，严洪森.知识化制造系统中动态调度的自适应