论文部分内容阅读
置换流水车间调度问题(Permutation Flow Shop Scheduling Problem,PFSP)是车间调度中具有代表性的一个子问题,是经典的具有排列性质的组合优化问题。同时,PFSP在现实中存在多个相互冲突的目标需要同时被优化,因此该问题也是多目标优化问题,对该问题进行深入研究具有重要的理论意义和实用价值。 论文针对单目标置换流水车间调度问题的最大完工时间目标提出了混合蚁群算法。针对多目标置换流水车间调度问题,利用了三种经典多目标进化算法,包括NSGA2、SPEA2、MOEA/D求解该问题,首次在该问题上分析了这三个算法的性能。以下是论文的主要工作: 介绍了PFSP产生的背景和研究意义,总结了当前PFSP和多目标进化算法的研究现状,对当前求解该问题的算法进行了分类。分析了针对求解PFSP的构造式启发式算法NEH、SPIRIT和蚁群算法各自的优缺点,鉴于此,将蚁群算法分别与这两个启发式算法混合,提出了混合蚁群算法用于优化最大完工时间,同时加入了局部搜索使得在其邻域中能获取更好的解。另外,引入了协调度概念作为启发式信息与混合蚁群算法作比较。通过在标准测试用例上进行仿真实验,实验结果表明混合蚁群算法在提高解质量上有较大的改进。 针对多目标置换流水车间调度问题,采用三种多目标进化算法对其求解,优化了两组相互冲突的目标。论文在PFSP标准测试用例上进行仿真实验,从Pareto覆盖率、算法的收敛性和算法运行时间三方面分析了这三个算法在解置换流水车间调度问题上的性能和对不同问题规模三个算法的适应性。