调度理论起源于生产系统,后来广泛应用于信息科学、供应链管理、数据处理等各类服务系统中,同时它与理论计算机科学和离散组合数学存在密切的联系。调度理论是指在一定的约束条件下,对资源和任务进行合理分配,使得某一个或几个与时间相关的目标达到最优。本文主要研究了等级机器上带重排的半在线问题。第二章研究三台等级机器上带重排的调度问题,所有工件都被分配后,在等级约束下,仅重排机器M3的最后一个工件,目标是最小化最大机器完工时间。基于两种不同的分配模型,当第一台机器的等级为1,后两台机器的等级为2,给出了该问题的下界3/2,设计了一个竞争比至多为5/3的在线算法;当前两台机器的等级为1,最后一台机器的等级为2,给出了该问题的下界3/2,设计了一个竞争比至多为12/7的在线算法。对于上述两个模型,分别给出发生重排和不发生重排的实例,以检验算法的可行性。第三章研究等级机器上带重排的机器覆盖问题,所有工件都被分配后,在等级约束下,仅重排一台机器的最后一个工件,目标是最大化最小机器完工时间。对于两台等级机器上的重排模型,只重排机器M2的最后一个工件,设计了一个竞争比为2的最优在线算法,并给出实例验证算法的可行性。对于三台等级机器上带重排的两种不同分配模型,重排机器M3的最后一个工件,证明了这两个问题的下界分别为2、无穷大。最后总结全文各章节的研究结果,结合当下重排模型的发展趋势,提出未来值得继续研究、探讨的几个问题。