工件可预处理排序中的若干问题和半杂交流水作业问题的研究

摘要

本文研究了两类排序问题，一类是要求在所有工件能够按时完工的前提下，使得预处理工件的费用最小的工件可预处理的排序问题，一类是特殊的杂交流水作业问题，本文称之为半杂交流水作业问题.并且对这两类问题都研究了他们的计算复杂性并给出了最优算法或者多项式时间近似算法.全文共分为三章. 第一章是绪论部分，主要介绍排序问题相关的一些概念和预备知识. 第二章考虑一个工件可预处理的单机排序问题.要求在所有工件能够按时完工的前提下，使得预处理工件的费用最小.证明了对于一般情况，该问题是NP-难的，并给出了动态规划算法.进一步，得到当每个工件的预处理费用都相同时该问题是多项式可解的，并给出了强多项式时间算法. 第三章考虑一个在图形处理中遇到的两阶段的半杂交流水作业问题.这个问题根据两个阶段间是否允许等待又可以分为可等待和不可等待两个问题，对于可等待的模型本文证明它是NP-难的，并且给出了动态规划算法和一个最坏情况界为3/2+1/10的近似算法；对于不可等待的情况证明了它是强NP-难的，并给出了动态规划算法和一个最坏情况界为3/5的近似算法.

目录

文摘

英文文摘

第一章绪论

第二章工件可预处理的单台机排序问题

第三章半杂交流水作业

参考文献

致谢

在学期间完成的论文