解多目标同顺序流水作业的局部搜索算法

针对求解最小化最大完工时间和总流程时间的多目标同顺序流水作业问题，提出了一个多目标局部搜索算法。针对两个目标，用现有的构造性算法生成两个解，作为该算法的初始解，然后从这两个初始解出发，以贪婪的方式求出新的Pareto最优解集，持续改进Pareto前沿。选择新的Pareto解的条件是该解既不被原解支配，也不被产生原解的解所支配，同时对某个目标改进最大。当所有的解都陷入局部极小时，扰动已得到的Pareto解集，然后从扰动后的解集出发重新搜索。初始解和选择新的Pareto解的方法对算法性能有显著的影响。在基准问题上，与已有文献中的算法比较，结果表明所提出算法的总体性能更优，特别是对较大规模的问题，此差异更具有显著性。