• CN:11-2187/TH
  • ISSN:0577-6686

›› 2014, Vol. 50 ›› Issue (8): 156-164.

• 论文 • 上一篇    下一篇



  1. 东南大学自动化学院;江苏大学交通运输系;东南大学复杂工程系统测量与控制教育部重点实验室
  • 出版日期:2014-04-20 发布日期:2014-04-20

Self-evolution Algorithm with Multi-objective for Scheduling a Job-shop-like Knowledgeable Manufacturing Cell

LI Wenchao; YAN Hongsen   

  1. School of Automation, Southeast University, Nanjing 210096;Department of Transportation, Jiangsu University, Zhenjiang 212013;Key Laboratory of Measurement and Control of Complex Systems Engineering of Ministry of Education, Southeast University, Nanjing 210096
  • Online:2014-04-20 Published:2014-04-20

摘要: 对于多目标的Job-shop问题很难找到其绝对意义上的最优解,通常找到的是其Pareto意义上最优解。建立一种类Job-shop结构的知识化制造单元多目标调度优化模型,并分析模型中多目标间关系。通过对其析取图模型分析,发现各任务的关键弧的特性,指出改变中间关键弧方向无助于优化目标函数,并在此基础上提出一种缩减邻域,该缩减领域极大减少要搜索的可行解数目。基于该缩减邻域特性,应用自适应启发评价方法提出一种多目标调度问题自进化算法,算法的联想搜索模块通过学习训练后能够为当前解匹配一个最佳动作以得到一个更好的解,模块这种功能随着训练增加不断改善。数值仿真结果表明所提算法通过学习对所提调度问题具备良好寻优能力和明显学习进化能力。

关键词: 自进化;多目标调度;知识化制造单元;Job-shop

Abstract: It is difficult to find the global optimal solution for the multi-objective job-shop scheduling problem and the solutions obtained usually belong to the Pareto optimal ones. A multi-objective scheduling optimization model is given for the Job-shop-like knowledgeable manufacturing cell and the relationship between the multi objectives is analyzed. The properties of key arcs of tasks are presented through the analysis of its disjunctive graph and the conclusion is obtained that it is helpless to improve the function value by changing the direction of the middle key arc of job. A simplified neighborhood is proposed based on the conclusion which can reduce greatly the number of feasible solutions to be searched. A self-evolution algorithm for multi-objective scheduling problem is proposed based on the properties of the simplified neighborhood by the use of adaptive heuristic critic method whose associate search module can find the best action for the concurrent solution to obtain a better solution by learning and training, and such ability of the module will be improved continuously with the training increasing. The numerical simulation results show that the algorithm proposed has the excellent ability to search the optimal solution for the proposed scheduling problem and possesses obvious evolution capacities through learning.

Key words: self-evolution;multi-objective scheduling;knowledgeable manufacturing cell;Job-shop