作业调度问题是研究利用有限的计算资源来计算大量的计算任务时碰到的问题。本文的工作是针对作业调度中的两个具体问题展开的。本文首先研究的是带容量约束的多机调度问题,包括它的均一性版本,一般性版本和推广的2维、k维版本问题。容量限制是指每台机器并不能处理任意多的作业,不同的机器可能具有容量上的约束,这时需要在多台机器上调度作业使得最晚完成时间最小并且满足容量约束。均一性版本问题中,单个作业在不同机器上的运行时间是一致的,本文利用线性规划上的迭代取整法给出了一个3-近似算法。这是第一次将迭代取整法应用到调度问题中。对于一般性版本,每台机器在不同机器上运行时间可能不同,本文利用放松判定过程给出了一个2-近似算法。在2维、k维容量限制调度问题中,本文将容量限制和运行时间优化推广成同一个概念：容量限制。本文分别给出了一个(4,4)-放松判定过程和一个(O(k),O(k),...,O(k)-放松判定过程。本文接下来研究带作业依赖的单机调度中的最小的最大作业延迟时间问题。本文研究了单台机器上不同作业之间带有依赖关系的模型,利用迭代取整法给出了一个2-近似算法。此算法也可以应用于构造一个适用于经典的带作业依赖的单机调度的最小带权完成时间和问题的2-近似算法。这一工作的另一个意义是再次印证了迭代取整法在解决难解问题中具有一定的一般性。