排序调度问题是组合优化领域里最受关注的问题之一,应用于工业生产,物流调度,设施选址等生活领域中。在大多数关于排序调度问题的文献里,要求所有的任务必须被安排在机器上加工,目标是寻找合适的调度方案,使得最大完工时间最小。随后,许多研究人员提出并研究了带惩罚费用的排序调度问题。带惩罚费用的排序调度问题与经典的排序调度问题的区别在于,所有的任务不要求全部被安排在机器上,每项任务或者被接受并安排在机器上加工,或者被拒绝并产生相应的惩罚费用,目标是寻找合适的调度方案,使得机器上的最大完工时间与所有被拒绝任务的惩罚费用之和达到最小。在带惩罚费用的排序调度问题的研究基础上,第三章提出在单机上的带惩罚费用的多维任务调度问题,使用2-划分问题证明此问题是一个NP困难性问题,并且提出一个运行时间为O（nd）的d-近似算法。当维数d为固定常数时,设计了一个运行时间为O(n^d+1（d/ε）^d)的全多项式时间近似方案。引入随机舍入思想,提出一个近似比为1.585的随机算法。当多维任务的信息未知时,提出一个竞争比为d的在线算法。第四章提出带惩罚费用的多重任务调度问题,设计了一个运行时间为O（n²logn）的2-近似算法。当机器数为固定常数时,给出一个运行时间为O(（4/ε）^m（ntmax）^m+1)的全多项式时间近似方案,其中tmax为所有用户提交任务最多数值,ε为任意正数。当用户信息未知时,提出一个竞争为2.618的在线算法,当机器数为2时,给出一个竞争比为1.618的最优在线算法。用Matlab编程实现两个章节中算法得到输出解,用Cplex计算相应实例的最优解,比较两个函数值,实验结果用条形图表示。最后一章总结了本文所有的研究成果,并提出未来值得研究方向。