Abstract: A new multi-objective job shop scheduling method was proposed based on hybrid evolutionary algorithm and knowledge, the better non-dominant Pareto solutions might be obtained for production scheduling with limited time or iterations. The knowledge mining attributes were determined by the optimized objects and attribute-oriented induction and deduction method. Then, the rule-based initial population was acquired by the priority weight. The proposed addition-deletion sorting method overcame the problems of insufficient or oversaturated operations by re-assigning the positions in the initial population locally. Finally, a benchmark and non-dominated sorted genetic algorithm-Ⅱ (NSGA-Ⅱ) hybrid simulated annealing algorithm were used to verify the proposed scheduling method. The results obtained are superior to the traditional stochastic evolutionary method in terms of the optimized function values or the distribution of solution set under different iterations and initial population sizes.

Key words: multi-objective job shop scheduling, knowledge mining, initial population, evolutionary algorithm

摘要： 提出了一种结合混合进化算法和知识的新型多目标车间调度方法，在有限的时间或迭代次数下可以得到更好的非支配Pareto解以服务于生产调度。由优化目标和属性归纳演绎法确定了知识挖掘的工件属性，通过优先级权重得到了规则初始种群。所提出的增减排序方法通过重新局部排序初始种群中工序的位置来克服优先级下工序不足或过饱和的问题。最后由一标准案例和非支配排序遗传算法-Ⅱ（NSGA-Ⅱ）混合模拟退火算法对所提调度方法进行了验证，得到的结果无论是优化目标值还是解集的分布在不同迭代次数和初始种群尺寸下都要优于传统随机进化方法。

关键词: 多目标车间调度, 知识挖掘, 初始种群, 进化算法