Abstract: The Job-shop scheduling problem with make-span as goal belongs to the NP complete problem and the valid algorithm for its solution hasn't been given until now.Through analyzing the characteristics of Job Shop knowledgeable manufacturing cell structure, the link constraint model was constructed, and feasible scheduling was obtained by adding constraint to its link-path graph. On these bases, a self-evolution algorithm with learning ability was proposed. Through adopting the q-function of reinforcement learning in algorithm, the needed knowledge was obtained from its environment to improve its search ability. The approximation of q function was implemented by using Radial Basis-Function(RBF)network to avoid too many states in learning process. Numerical simulation results showed that the proposed algorithm had excellent learning and evolution ability for this kind of problems.

Key words: self-evolution, reinforcement learning, knowledgeable manufacturing cell, radial basis-function networks

摘要： 以最大完工周期为目标的Job-shop调度问题是一类NP完全问题,迄今仍未发现其求解的有效算法。通过Job-shop型知识化制造单元自身结构特性分析，构建其链约束模型，并通过对其链路图添加约束获得可行调度。在此基础上提出一种自进化算法，该算法在运行中通过q学习能够不断从环境中获取所需知识，使其搜索能力逐步提高。对于学习过程中系统状态过多的问题，采用径向基函数网络对q函数进行逼近。通过仿真计算表明了所提算法对该类问题具备明显的学习进化能力。

关键词: 自进化算法, 强化学习, 知识化制造单元, 径向基函数网络