Abstract: To solve the low accuracy problem for solving the job shop scheduling with cache constraints applied by existing heuristic algorithm,the solution extended from the job level to the process level was proposed,and the genetic algorithm was used to get a higher precision solution.To avoid premature convergence and falling into local optimum of traditional genetic algorithm,the algorithm was improved by combining the adaptive crossover mutation probability with improved crossover operator.The experimental results showed that the proposed algorithm could obtain higher precision solutions with the same buffer capacity.

Key words: buffer constraints, job shop scheduling, genetic algorithms, prescision

摘要： 针对已有的启发式算法在应用于带有缓存约束的作业车间调度时求解精度不高的问题,提出将解决方案从工件层级扩展到工序层级,并采用遗传算法对问题进行求解,以得到精度更高的解。同时,为避免传统遗传算法过早收敛和陷入局部最优,结合自适应交叉变异概率和良种交叉算子对算法进行改进。最后,通过实验计算结果,验证了算法能在同等缓存容量下获得精度更高的解。

关键词: 缓存约束, 作业车间调度, 遗传算法, 求解精度