近年来,调度问题越来越受到研究人员的关注,而且调度问题被广泛应用于工程管理、物流管理、服务产业等生产生活领域。一般来说,调度问题的目标是寻找合适的调度方法,以使得机器的最大完工时间尽可能小。根据实际问题,研究人员相继提出了带惩罚费用的调度问题和带等级约束的调度问题。带惩罚费用的调度问题和最初的调度问题不同点是有的任务被机器接受、有的任务被机器拒绝,如果某项任务被接受则被分配给某台机器加工,如果被拒绝则需要支付惩罚费用。带惩罚费用的调度问题的目标为最小化机器的最大完工时间与所有被拒绝任务的惩罚费用之和。根据带惩罚费用的调度问题的相关理论,本文在第三章提出了两台平行机上的带惩罚费用的多维调度问题,设计了一个近似算法,算法的近似比为3;在任务的维数d为固定常数的情况下,利用动态规划算法得到一个时间复杂度为O(n2d+1(1/ε)2d)的完全多项式时间近似方案;根据随机舍入方法,设计了一个近似算法,算法的近似比为2.54;在不知道多维任务的信息的情况下,设计了一个在线算法,在线算法的竞争比为2.618d。根据带等级约束的调度问题的相关理论,带等级约束的调度问题和最初的调度问题的不同点是每一项任务有一个等级、每一台机器也有一个等级,每台机器只能加工等级不低于它的任务。带等级约束的调度问题的目标为最小化机器的最大完工时间。本文在第四章提出了两台平行机上的带等级约束的多重调度问题,当已知最优值COPT时,设计了一个半在线算法,算法的竞争比为3/2;当已知所有任务的最大加工时间时,设计了一个半在线算法,算法的竞争比为((?)+1)/2。在结论中,总结了本文的研究结果以及未来有价值的研究方向。