排序问题是一类重要的组合最优化问题。工件带强制工期,指工件必须在已给定的工期内完工,不得延迟。这种环境在实际应用中随处可见。如果工件过早提前完工,意味着工件还需要保管,将会产生额外费用。本文分别在单机,同型机和车间的机器环境下,以最大提前完工时间或提前完工时间和为目标函数,对一系列工件带强制工期的排序问题进行了研究,取得了以下成果：1.在单机环境,分别研究了以下几个问题并取得了相应的成果：(1)极小化最大提前完工时间。本文讨论了该问题的可行性,并针对可行问题设计了最优算法。(2)工件可中断,极小化最大提前完工费用。本文首先针对强制工期相等和不存在优先约束这两种特殊情形,分别设计了相应的最优算法,而后针对一般情形,设计了最优算法。(3)工件有到达时间,极小化最大提前完工时间。本文首先证明了它是强NP-hard问题,而后,设计了在加工时间相等这种特殊情形下的最优算法。(4)工件有到达时间且可中断,极小化最大提前完工时间。本文讨论了该问题的可行性,并针对可行问题设计了最优算法。(5)工件有到达时间且可中断,极小化提前完工时间和。本文证明了该问题是NP-complete问题,并设计了加工时间相等这种特殊情形下的最优算法。2.在同型机环境,分别研究了以下几个问题并取得了相应的成果：(1)极小化最大提前完工时间。本文证明了判断该问题的可行性是一个NP-complete问题,也证明了甚至在强制工期相等时该问题也是一个NP-complete问题,此外,设计了加工时间相等这种特殊情形下的最优算法。(2)工件可中断,极小化提前完工时间和。本文证明了该问题是强NP-hard问题,并设计了加工时间相等这种特殊情形下的最优算法。3.在流水车间和开放车间环境,分别研究了工件强制工期相等,极小化最大提前完工时间的双机排序问题。本文分别讨论了它们的可行性,并针对可行问题设计了最优算法。