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

IMPROVING CGA BY LSO FOR MULTIPLE-OBJECTIVE JOB SHOP SCHEDULING PROBLEM

作　　者：任晓莉[1] 

机构地区：[1]宝鸡文理学院计算机科学系,陕西宝鸡721007

出　　处：《计算机应用与软件》2015年第3期60-64,共5页Computer Applications and Software

基　　金：国家自然科学基金项目(61075022;61379030);陕西省自然科学基金重大专项(BK2012026);陕西省教育厅项目(2013JK1198);宝鸡文理学院教改项目(JG11050)

摘　　要：针对传统方法在处理作业车间调度问题时很难将库存容量考虑在内的问题,提出了基于局部搜索算子(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.

关 键 词：多目标作业车间 调度问题 库存容量 混合遗传算法 交叉遗传算子 局部搜索算子 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]