排序问题是一类研究比较活跃的组合最优化问题。本文讨论了一类带有交货期窗口和工件可拒绝的单机排序问题,主要研究内容如下:　　第一章介绍了一些关于排序问题的背景知识和本文所讨论的工作。　　第二章讨论了带有交货期窗口和工件可拒绝的单机排序问题,该问题是将所有的工件分成两个工件集,一个是被接受的工件集,另一个是被拒绝的工件集。对于被接受的工件集:每个工件都有一个固定的交货期窗口,且交货期窗口大小相同。如果某个工件的完成时间在交货期窗口的准许范围之内,则对于该工件来说,不产生任何其它惩罚费用;否则会产生提前或延误的费用。而对于拒绝工件而言,它的费用只与工件自身有关。问题的目标是确定被接受工件的最优排序,极小化这两个工件集产生的总费用。首先,在本章提出了一些重要的性质及相关的主要结论,并进行了一些最优解的讨论;其次证明了该问题是多项式时间可解的,同时针对该问题给出了一个动态规划算法,并给出数值例子加以验证。最后本文又将问题扩展到加工时间与位置相关的排序问题。通过将问题转化为一系列的指派问题,证明了该问题是多项式时间可解的。　　第三章是把第二章问题推广到带有维修活动的情况。考虑了带有交货期窗口、机器可维修和工件可拒绝的单机排序问题。其中维修活动分两种情况:维修活动从t?0时刻开始;维修活动的开始时间等于某个工件的完工时间。维修活动持续时间是一个固定值,排在维修活动之后的工件的加工时间将会减少。问题的目标是确定维修活动的位置和被接受工件的最优排序,极小化接受工件集和拒绝工件集产生的总费用。通过将该问题的两种情况都转化为指派问题,证明了该问题是多项式时间可解的,并给出数值例子加以验证。最后,总结了全文并提出了今后工作的研究方向。