论文摘要
本文研究加工时间恶化的单机排序问题。所研究的模型包含两类：工件加工时间由于开工时间的延迟而恶化的排序问题被称为第一类加工时间恶化问题；工件加工时间由于加工顺序的延后而恶化的排序问题被称为第二类加工时间恶化问题。对于第一类加工时间恶化问题，本文讨论了加工时间随开工时间线性增加的情形。我们证明，在某些特殊情况下，这类问题是多项式时间可解的。在无法证明是否为多项式时间可解时，我们也给出了相应的多项式时间近似算法。第二类加工时间恶化的最大完工时间和总完工时间问题是多项式时间可解的。我们证明，这类问题等价于指派问题，从而可用匈牙利算法加以解决。