Abstract: In solving Flexible Job-Shop Scheduling Problem (FJSP) with traditional Polychromatic Sets Theory (PST) of Improved Genetic algorithm (GA),a large amount of invalid data were contained in constraint model and chromosomes contains,and the solution speed and accuracy was unsatisfied.Aiming at these deficiencies,an improved GA based on PST hierarchical structure was proposed.Through setting equipment datum,the original process-machine contour matrix was divided into the relationship matrix of equipment datum-equipment type and equipment type-Asset number,which could effectively reduce the data sizes of constraints model.By optimizing the length of chromosome and setting a reasonable bench datum to operation together,the time and space complexity of chromosome were reduced effectively.Through comparing the result of different examples with traditional algorithm,the superiority of proposed algorithm was verified.

Key words: polychromatic sets theory, hierachical stracture, genetic algorithms, constraint model

摘要： 针对传统多色集合理论改进的遗传算法在求解柔性作业车间调度问题所呈现出的约束模型和染色体中无效信息较多,以及求解速度和精度不够理想的不足,提出基于多色集合层次结构的改进遗传算法。通过设置设备基准,将原来的工序—机床围道矩阵分割为基准与设备型号、设备型号与资产编号的关系矩阵,有效地降低了约束模型的数据量;对染色体长度的合理优化和设置批量基准的合批操作,有效地降低了染色体的时间和空间复杂度。通过对不同实例的仿真结果分析,验证了所提算法的优越性。

关键词: 多色集合, 层次结构, 遗传算法, 约束模型