第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