排序问题是运筹学与组合优化领域中的一类重要问题.对排序理论的研究具有重要的理论意义和广阔的实际应用前景.数十年来,人们对此专题进行了深入地研究,并提出了大量的模型和优秀的算法.在排序论的大部分文献中,排序问题分为离线和在线排序两种.所谓“离线”是指所有工件的信息都事先已知.而“在线”是指事先不知道工件的信息,工件的信息是逐个释放的.工件只有在到达后才知道它的信息.在决定当前工件的加工时,对其后面到达的工件的信息是一无所知的,并且工件一旦分给某台机器加工就不允许改变.随着排序理论和应用的发展,上面的分类已不足以包含所有的排序问题.大量问题的情况往往介于两者之间.从而“半在线”模型由于其在实践中的广泛应用引起了大家的重视.所谓“半在线”即所知道的工件信息介于离线和在线之间.或者说在半在线模型中人们知道未来工件的部分信息,但仍然要求工件一旦分给某台机器加工就不允许改变.人们试图利用某些部分信息设计出比已有最好在线算法更好的算法.　　本文研究的模型是带有机器准备时间的两台恒同平行机半在线排序问题.用三参数表示为,P2,ri|sum&decr|Cmax.也就是说,有两台恒同机且机器具有准备时间.已知所有工件的加工时间总和(sum)并且工件按加工时间递减顺序(decr)在线到达.目标为极小化最大完工时间(makespan).在第一章中,我们主要向大家介绍了排序问题的一些基础知识和相关的文献.在第二章中,我们研究了P2,ri|sum&decr|Cmax(M)和P2,ri|sum&decr|Cmax(J).对上述两个问题,我们给出了竞争比为7/6的半在线算法,并进行了严格的证明.