关于两台恒同机器的排序问题,在分批排序和经典排序中,大多数文献都是考虑或者两台机器都是批处理机(批容量无界)或者两台机器都是正常机器(任何时刻最多只能加工一个工件,即批容量为1)。　　在本文中,我们考虑了两台恒同机器的在线排序问题,但是我们主要考虑第一台机器M1是平行批处理机,而第二台机器M2是正常机器。　　第二章我们研究的在线排序问题可以描述为:有两台恒同机;工件信息(到达时间和加工时间)在排序之初未知,而是随着时间的推移而逐个到达;目标是最小化两台机器上工件的最大完工时间。采用Graham等人[21]提出的排序问题的一般记号,这个问题记为我们首先利用对手法构造一个实例证明了该问题竞争比的下界为1+α。接着提供了一个竞争比为2在线算法。　　第三章我们研究的在线排序问题可以描述为:有两台恒同机;工件之间的序约束关系是平行链;工件链一旦到达,该链上所有工件的信息才可知;所有工件的长度都相同(即为p);目标是最小化两台机器上工件的最大完工时间。采用Graham等人[21]提出的排序问题的一般记号,这个问题记为我们首先利用对手法构造一个实例证明了该问题竞争比的下界为1+α。接着我们给出该问题一个最好可能的在线算法。