排序问题是一类非常重要的组合最优化问题,排序是在一定的约束条件下对工件和机器按时间进行分配和安排次序。在经典的排序问题中,大多数情况都是研究仅一个目标函数的单目标排序问题。然而在生产管理实践中有些情况不仅仅只需要考虑一个方面的性能指标,而是需要综合考虑多个性能指标,即需要求解多个目标函数的最优或近似最优或在某目标函数约束范围下求其它一些函数的最优或近似最优解的排序。多目标排序问题被广泛应用于计算机系统、生产管理等其它各个领域,具有广泛的生产实践背景和应用价值。本论文共分为五个章节:第一章简述排序问题的基本理论。第二章介绍本文主要研究的两类多目标排序问题的研究成果和发展现状。第三章研究以工件总误工数为第一目标,以最小加权总提前完工时间为第二目标的双目标函数排序问题。对该排序问题,在文献[1]的基础上提出分支定界算法,并给出几种特殊情况下的多项式算法;进一步,将单机排序中的所得结论推广到m台平行机的排序中,得到该排序问题在平行机中的相应算法与相关结论。第四章研究以最大延误不超过某个特定值为第一目标,以加权总完工时间为第二目标的约束性双目标函数排序问题。在单机排序中,找到该问题最优解并证明其最优性;在平行机排序中,研究了两台平行机及设定权重恒为一的条件下,找出其相应的算法,最后把该问题推广到m台平行机上,找出其优势条件。第五章是对本论文内容的总结,并提出了对未来的工作设想和努力的方向。