论文部分内容阅读
同时加工排序和可控排序是两类很重要的现代排序模型，本文把这两类排序模型结合起来，讨论加工时间离散可控的单机同时加工排序问题：所有工件都具有相同的可控加工时间和控制费用，每一批工件的加工时间等于这批工件中所有工件加工时问的最大者，分别考虑了不带就绪时间和带就绪时间两种情况。在不带就绪时间的情况下，分别使总延误，加权误工和以及最大延误加上加工时间可控所需费用的总和为最小作为优化的目标，讨论了这三个问题的最优解的性质，并在此基础上提出了相应的动态规划算法。在带就绪时间的情况下，分别讨论了带两个就绪时间和不同的就绪时间的最大完工时间问题，给出了这两个问题的最优解的一些性质，并在此基础上给出了相应的动态规划算法。对带不同就绪时间的问题，给出了一个FPTAS算法。