一种基于Q学习的Flow shop问题调度算法研究  

A Scheduling Algorithm Based on Q-Learning for Flow Shop Problem

作　　者：李国昊[1] 李文超[2] LI Guo-hao LI Wen-chao(School of Management, Jiangsu University, Zhenjiang 212013, China School of Automobile and Traffic Engineering,Jiangsu University, Zhenjiang 212013,China)

机构地区：[1]江苏大学管理学院,江苏镇江212013 [2]江苏大学汽车与交通工程学院,江苏镇江212013

出　　处：《工业工程与管理》2016年第5期23-27,41,共6页Industrial Engineering and Management

基　　金：江苏省社会科学基金资助项目(14GLB008);江苏省高校自然科学研究资助项目(13KJB460005)

摘　　要：两台机器以上的Flow shop调度问题是一个强NP难的问题,目前为止尚未出现求解该类问题的有效算法。本文结合针此类问题的邻域操作特征,基于强化学习思想提出一种具备学习能力的调度算法。算法以Q学习作为训练方法,通过持续的离线训练学习该类问题寻优搜索知识,从而提高其调度寻优能力。算法采用高斯核函数支持向量机对Q函数进行拟合,以此克服在Q学习过程中遇到状态过多难题。数值仿真结果显示所提算法对Flow shop问题具有很好调度寻优能力。The flow shop problem with more than two machines is a strong NP difficult problem, and there is yet no valid scheduling algorithm for it. A scheduling algorithm with learning capacity is proposed on the basis of reinforcement learning by the use of its neighbor operation features. By using Q-learning as training method, the algorithm can obtain the knowledge of optimization for this kind problem to increase its searching ability in optimization process. The approximation of Q function is realized by the utility of the support vector machine （SVM） with a Gauss kernel function to solve the problem of overmuch state during the Q- learning process. The results of numerical simulation show that the proposed algorithm possesses excellent performance on scheduling and optimization.

关 键 词：调度 FLOW SHOP Q学习 支持向量机 

分 类 号：C935[经济管理—管理学]