论文部分内容阅读
本文研究了两种排序问题：两台机上成组加工的流水作业排序问题和单台机有维护时段的排序问题.
全文共分三章.第一章简要介绍了组合优化问题、排序问题的基本概念与算法和最坏情况分析的简要介绍.在第二章中，详细介绍了两台机上成组加工的流水作业排序问题，从一组工件到另一组工件之间需要调整时间.首先对NP-难的F2|S，GT|∑i,jWijCij离线排序，给出了一个近似算法，证明了它的最坏情况界为2.然后讨论了F2|S，GT|Cmax在线排序，并给出了一个竞争比为2的近似算法，并证明不可能存在竞争比小于2的在线近似算法.第三章研究了单台机器有维护时段的排序问题，目标为极小化总完工时间.对该问题，文献中最好的近似算法MSPT的最坏情况界为20/17.本文将文献中基于邻域搜索思想的2-OPT操作推广为k，k-交换操作，利用此操作，给出了一个多项式时间近似方案，从而大大改进了文献中的结果.