机器排序和机器覆盖经常在实际运用中出现，比如在网络通信中通道分配均衡问题，大型的并行计算问题，柔性生产系统中任务排序问题，等等．这篇论文主要研究了m台平行机的复合半在线排序问题．考虑了半在线机器覆盖问题，这个问题最先由Deuermeyer等提出．应用于维持飞行器燃气涡轮发动机的运转和基于提高网络服务质量(quality of service，简称QoS)而产生的带宽分配．同时还考虑了最先由Azar和Regev提出的在线Bin Stretching问题，以及机器带准备时间的半在线排序问题．这些问题都具有着一定的现实背景，针对每个问题都分析了下界并设计了相应的半在线算法，有的算法是最优算法．全文共分为七章．　　 第一章是绪论部分，主要介绍一些组合优化以及算法设计与分析方面相关的概念和预备知识．　　 第二章简要综述了近年来与本文相关的在线与半在线平行机排序问题的若干成果，并简单说明了一下本文的一些主要结果．　　 第三章研究了两台同型平行机半在线排序问题，也即事先预知复合信息：所有工件大小总和和最大工件大小的半在线排序问题(P2∣sum＆max∣Cmax)．尽管P2∣sum＆max∣Cmax具有竞争比为6/5的最优算法，但这是针对最坏情况进行分析所得到的结果，并不理想，其实很多时候能够得到竞争比更好的算法．因此这章主要分析了P2∣sum＆max∣Cmax当参数r＝2pmax/T取不同的值时间题的下界并设计了相应的算法，下界与算法的竞争比均是关于r的函数．当r=1/2时有竞争比为7/6的最优算法．当7/13≤r≤1时给出了最优算法，算法的竞争比为　　 第四章主要研究了预知工件大小按非增排列到达，目标为极小化stretchfactor的半在线Bin Stretching问题．也即预知工件大小按非增排列到达和离线状态下最优目标值C*，目标为Gmax(makespan)的平行机排序问题．对于m台机器的情形，证明了问题的下界至少是10/9，并设计了竞争比至多为1+m—1/4m—2的半在线算法．对于P3∣opt＆decr∣Cmax，则改进了算法，给出竞争比至多为7/6的算法．　　 第五章主要研究了已知工件大小上界为C*/k的平行机排序问题，根据是否已知最优目标值的不同模型，分别针对两个目标Gmax和Cmin进行了分析．对于Pm∣k—bounded∣Cmax，证明了当m≤k+1时LS算法为最优算法，竞争比为1+m—1/mk，当m＞k+1时下界至少为1+1/k+1．对于Pm∣opt＆k—bounded∣Cmax，证明了下界至少为1+1/2k+1．同时针对两台机的情况设计了竞争比为1+1/2k+1的最优算法OB2．对于Pm∣k—bounded∣Cmin，证明了LS算法为最优算法，竞争比为mk/mk—m+1．对于Pm∣opt＆k—bounded∣Cmin，证明了下界至少为1+1/2k，并设计了竞争比为1+m—1/mk的算法．　　 第六章研究了三台机机器带准备时间的半在线Machine Covering问题P3，ri‖Cmin．对于预知所有工件加工时间总和和最大工件加工时间的复合半在线问题，给出了竞争比为3/2的最优算法．　　 第七章为后记，简要总结了本文的工作，讨论了将来可以进行的研究方向以及一些有待研究的公开问题与模型．