论文摘要
排序问题是一类重要的组合优化问题，它广泛应用于管理科学、计算机科学、工农业生产、交通运输等许多领域，一直受到国内外学术界的重视。而其中的分批排序问题以及工件可拒绝的排序问题，因其具有明显的实际应用背景，更是吸引了国内外许多学者。特别是对于工件可拒绝的排序问题，这一方面的研究结果还比较少，本文主要研究工件可拒绝的分批排序问题。论文共分三章。第一章主要介绍了排序的产生背景、发展及其一些符号等相关的基本知识。第二章讨论的是工件可拒绝同时到达时的单机分批排序问题，目标函数是极小化最大完工时间加上被拒绝工件的拒绝费用之和。本文通过动态规划算法给出了多项式时间的精确算法，借助于数据结构中的堆排序，我们将算法复杂性降低为O（n2 log B）。所研究的问题若用三参数法应表示为1|rej，B|Cmax+∑j∈Rej。第三章主要研究了工件可拒绝且不同时到达时的单机分批排序问题，即问题1|rj，rej，B|Cmax+∑j∈Rej，给出了PTAS算法。