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

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

同顺序流水作业排序问题的一个启发式算法

本文主要给出了同顺序ｍ×ｎ排序问题初始序的选取方法以及通过计算可避免出现高重循环的初始序的排序算法，然后又给出了利用矩阵可行线性质将初始序调试成较优序的可行方法．利用该文方法对ｎ＝１５，ｍ＝ ３～１４的１４４个例题计算，得出平均相对误差为 ３．１４５％的结果，对于ｍ＝ ３与ｍ＝ ４的 １２８个例题计算，得出平均相对误差为 ０．６３０６％．统计结果表明该方法可在实际中进行应用．

关于“Fm|prmu|C_(max)问题”的算法

Fm|prmu|Cmax,即m(m>2)台机器同顺序加工n个工件问题是一类重要的车间作业排序问题.对于给定加工顺序的n个工件的排列排序,排序时间表长即任务的最后完工时间的计算可以通过与问题对应的有向图的关键路的计算得到.本文从关键路的结构特点和性质出发,提出了在关键路的基础上将前后相邻的两个工件的加工时间进行比较,然后择优排序的方法,使Johnson SM算法可以在多台机器上得到一定程度的推广,从而使该问题的解法得到明显简化.