本文主要研究与due date相关的一些排序问题。我们在第一章中首先介绍排序问题的基本概念，排序算法的性能分析，以及随机性排序问题及其排序策略。 第二章讨论两台平行机排序极大化按期完工工件数问题，由于它的一个子问题等价于划分问题，因而该问题是一个NP-难的问题。我们提出了一个绝对性能比为3／4的近似算法A2-1。对机器带准备时间的问题，近似算法A2-1的渐近性能比为2／3。第二章所讨论的另一个问题是带提前和延误惩罚的两台机排序极大化just in time完工工件数问题，当提前惩罚大于或等于延误惩罚时，本文提出了该问题的一个多项式时间最优算法A2-2，从而证明了该问题是一个P问题，当提前惩罚小于延误惩罚时，我们证明了该问题是一个NP难的问题。 第三章是两个装箱算法应用于NP-难平行机排序问题的近似算法。第一个算法利用装箱问题中的FF（First Fit）算法求解极大化按期完工工件数的平行机排序问题Pm／／dj=d／n-∑uj，该近似算法具有渐近性能比下界。第二个近似算法利用二维装箱中strip packing问题的算法求解以极小化makespan为目标的带并行工件的平行机排序问题，该算法的渐近性能比具有下界1.5和上界1.6。 第四章讨论交工期可指定的单台机排序问题的online算法，目标仍为极大化按期完工工件数。对于允许中断（preemptive）问题1／prmp，d[j]／n-∑uj，本文提出了一个多项式时间最优算法，而对可中断—重新加工（preemption-restart）问题，我们给出了一个竞争比为1／2的online算法，并且证明了对于不允许中断问题不存在竞争比大于零的online算法。 第五章研究两台机器超载实时系统online算法，目标为极大化按期完工工件总加工机时。文中提出了一个NSR算法，其竞争比为2／5，有效地改进了近年来Wang等人提出的竞争比为1／3的SR算法。 第六章研究工件的加工时间为随机变量的排序问题。对极大化期望按划完工工件数为目标的单台机排序问题，给出了一系列启发式算法Gα（0＜α＜1），该算法直观可行，适合用计算机处理，具有一定的实际应用价值。