计算机工程 ›› 2009, Vol. 35 ›› Issue (16): 25-28.doi: 10.3969/j.issn.1000-3428.2009.16.009

• 博士论文 • 上一篇    下一篇

Job-shop排序问题的遗传强化学习算法

潘燕春1,周 泓2   

  1. (1. 深圳大学管理学院,深圳 518060;2. 北京航空航天大学经济管理学院,北京 100083)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2009-08-20 发布日期:2009-08-20

Genetic Reinforcement Learning Algorithm for Job-shop Scheduling Problem

PAN Yan-chun1, ZHOU Hong2   

  1. (1. College of Management, Shenzhen University, Shenzhen 518060;2. School of Economics and Management, Beihang University, Beijing 100083)
  • Received:1900-01-01 Revised:1900-01-01 Online:2009-08-20 Published:2009-08-20

摘要: 针对Job-shop排序问题的复杂性,提出一种遗传强化学习算法对其求解。通过引入多个随机变量,把Job-shop排序问题转换成多阶段决策问题,通过仿真手段构建作业排序问题模型环境,求取系统性能指标并保证解的可行性。设计一个多智能体Q-Learning算法和遗传算法相结合的算法用于解决Job-shop排序问题。仿真优化实验结果验证了该算法的有效性。

关键词: 遗传强化学习, Job-shop排序, 多阶段决策, 仿真

Abstract: Aiming at Considering the complexity of Job-shop scheduling problem, this paper proposes Genetic Reinforcement Leaning(GRL) algorithm to solve it. Several stochastic variables are introduced to transform the Job-shop scheduling problem into sequential decision-making problem, and the model environment is built through simulation to obtain system performance indices and ensure the feasibility of solution. An algorithm integrating multi-Agent Q-Learning algorithm with Genetic Algorithm(GA) is designed to solve Job-shop scheduling problem. GRL algorithm is validated by simulation and optimization experiment results.

Key words: Genetic Reinforcement Learning(GRL), Job-shop scheduling, sequential decision-making, simulation

中图分类号: