LSO 改进 CGA 解决多目标作业车间调度问题

摘要

针对传统方法在处理作业车间调度问题时很难将库存容量考虑在内的问题，提出了基于局部搜索算子（LSO）改进交叉遗传算法（CGA）的多目标作业车间调度模型。为了提高所提模型的效率，首先设计一种基于关键路径的交叉遗传算子；然后，设计一种新的局部搜索算子来提高遗传算法的局部搜索能力；最后，基于这两种算子，设计混合遗传算法框架，在考虑调度总完成时间的同时将库存容量作为目标进行优化。所提算法的有效性在 FT10、LA01、LA06、LA11、LA21和 LA36等基准问题测试中得到验证。仿真结果表明，与较为先进的非劣分层遗传算法（NSGA-II）相比，使用所提算法获得了更好的非支配解，从而更好地解决了多目标作业车间调度问题。%For the issue that it is difficult for traditional methods to take inventory capacity into account when processing job shop scheduling,we propose the multiple-objective job shop scheduling model which is based on improving crossover genetic algorithm (CGA) with local search operator (LSO).In order to improve the efficiency of the model addressed,first we design a critical path-based crossover genetic operator.Then,we design a new local search operator to improve local search ability of genetic algorithm.Finally,we design the hybrid genetic algorithm frame based on the two designed operators,while considering overall completion time of scheduling,we optimise inventory capacity as the objective.The effectiveness of the proposed algorithm is verified by testing of a series of benchmark problems such as FT10,LA01,LA06,LA11,LA21 and LA36.Simulation result shows that it gets better non-dominated solution by using the proposed algorithm compared with the rather advanced non-dominated sorting genetic algorithm-II,so that it can solve multi-objective job shop scheduling problem better.