一类类Job-shop结构的知识化制造单元多目标调度自进化算法

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

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

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.