机器覆盖问题是组合优化领域研究的热点问题之一,在资源的公平分配、公共服务行业以及团队业绩考核等方面有着广泛的应用。本文研究了等级约束下两台机器的机器覆盖问题,其定义为:给定n项工件和两台机器,每一项工件都有一个处理时间Pi和服务等级gi∈｛1,2｝;第一台机器能处理所有的工件,第二台机器只能处理服务等级为2的工件,目标是最小的机器负载达到尽可能大。第三章提出了工件具有离散处理时间的两台机器的半在线机器覆盖问题,即在处理工件之前,已知所有工件的处理时间属于｛1,2,...,2k｝。利用反证法证明了不存在竞争比小于为2k的在线算法。对于≥2,设计了一个竞争比为2k的最优半在线算法。第四章提出了已知部分工件处理时间之和的两台机器的半在线机器覆盖问题。当已知服务等级为1的工件处理时间之和时,证明了不存在竞争比小于2的在线算法,并设计了一个竞争比为2的最优半在线算法;当服务等级为1与服务等级为2的工件处理时间之和同时已知时,证明了不存在竞争比小于3/2的在线算法,并设计了一个竞争比为3/2的最优半在线算法。在最后一章概括了本文所得到的研究结果,并提出未来可以研究的问题。