加工时间恶化的排序问题的讨论

摘要

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

目录

文摘

英文文摘

第一章引言

1.1排序问题概述

1.2本文所研究的问题

第二章第一类加工时间恶化问题

2.1概述

2.2异件异速恶化问题

2.3异件同速恶化问题

第三章第二类加工时间恶化问题

3.1概述

3.2函数p(q,j)的一般形式

3.3函数p(ai,j)的特殊形式

参考文献

致谢