在线排序是现代排序的一个重要组成部分.在经典的离线排序问题中，我们总是假设决策者在做决策之前已经获知所有工件的信息.事实上，在实际生产过程中很多时候决策者在没有获得所有工件信息之前就必须做出决策.于是出现了在线排序.人们通常把在线排序问题分为三类：　　 列表在线（online-list）：工件是排成一个序列到达的.前面的工件必须被安排到机器上后面的工件才会被释放出来.工件一旦被释放，工件的信息即被获知.工件的安排方式一旦确定就不可以再改变.　　 时间在线（online-time）：工件是随着时间到达的.前面到达的工件即使没有被安排也不会影响后面工件的到来.工件的信息在工件的到达时刻才能获知，工件在到达之前不可以被安排.工件被安排之后不能再改变.　　 不可预测的时间在线（online-time-nclv）：工件是随着时间到达的.工件的加工时间只有在工件完工之后才可获知，而在工件的到达时刻无法得知或预测（nonclairvoyance）.工件在到达之前不可以被安排，一旦安排就不可以改变.　　 在本学位论文中，我们主要研究的是时间在线排序问题.我们考虑一台或两台平行批处理机的排序模型.平行批处理问题起源于半导体制作工业、制平行批鞋业、金属铸造工业等方面.在后文中我们将会详细叙述.一台平行批处理机在不超过批容量的情形下，可以同时加工多个工件.批的加工时间是由该批中最长的工件确定的.同一批的工件具有相同的开工时间和相同的完工时间.在本文所研究的排序模型中，我们均假设批容量是无界的，即机器可以同时加工任意多个工件.同时，我们还假设存在多个不可相容的工件组或者假设批是允许有限次重启的.　　 不可相容的工件组是指，每个工件可能属于不同的组，组与组之间是不可相容的（比如，不同的组具有不同的化学性质）.因此，不同组的工件不可以被安排在同一批加工.　　 考虑到重启是一种有限的资源或者重启会带来一定的负面影响，因此我们提出了有限次重启的概念.批允许有限次重启是指，如果一批中不包含有已经被重启过的工件，就可以被重启.批重启之后，批中的工件被释放出来，成为各自独立的未加工工件.再次加工被重启过的工件时必须重新开始加工，并且加工过程不可以被打断直到其完工.　　 重启与中断是两个不同的概念.中断的工件再次被加工时是接着已经被加工的部分继续加工的；而重启的工件再次被加工时是从头开始加工的，前面已经加工的部分全部作废.重启只有在在线排序问题中才有意义.因为在离线排序中，我们完全可以等到适当的时候再加工工件，而不用做无用功.而在在线排序中，因为缺乏未来工件的信息，所以利用重启可以帮助决策者得到更优良的在线算法.　　 我们用竞争比来衡量一个在线算法的优良程度.对于一个最小化目标函数的在线排序问题，我们说在线算法A是ρ-竞争的（ρ>1），如果对于任意的实例Ⅰ，都有A（Ⅰ）≤ρ.opt（Ⅰ），其中A（Ⅰ）是在线算法A生成的目标函数值，opt（Ⅰ）是最优的离线算法生成的目标函数值.（对最大化目标函数的在线排序问题，如果A是ρ-竞争的（ρ<1），则有A（Ⅰ）≥ρ.opt（Ⅰ）.）由此可见，ρ的值越趋于1，则在线算法得到的目标函数值就越趋于离线情形下最优的目标函数值，在线算法也更优良.对某个在线排序问题来说，如果它的一个在线算法的竞争比与该问题的竞争比的下界相吻合，那么我们就说该算法是最好可能的在线算法，这也就意味着该在线排序问题彻底被解决.　　 本学位论文中我们主要考虑了六个问题.第二章和第三章研究的是单台平行批处理机带有不可相容的工件组的在线排序问题；第四章和第五章研究的是两台平行批处理机的问题；后面两章我们主要探讨了允许有限次重启的平行批排序问题，包括单机和平行机.具体地，主要结果如下：　　 1.在第二章中，我们研究了带有两个不可相容的工件组的单台平行批处理机在线排序问题.目标函数是最小化最大完工时间.我们首先证明了该问题任意在线算法的竞争比的下界是√17+3/4≈1.7808，然后我们给出了一个竞争比是√17+3/4的最好可能的在线算法.　　 2.在第三章中，在第二章研究的基础上我们扩展了已有的结果.我们假设不可相容的工件组的个数f是一个输入的数.我们找到了最好可能的在线算法的竞争比是f的一个表达式，即1+√4f+1-1/2f.当f≤2时，得到的结果与已知结果相同.需要说明的是，本章我们给出的算法是一个有别于已知的新的在线算法.　　 3.在第四章中，对于两台平行批处理机，目标函数是最小化最大完工时间的在线排序问题，我们首先证明了问题的竞争比的下界是√2，然后我们给出了一个最好可能的新的在线算法，证明了算法的竞争比与下界吻合.　　 4.在第五章中，我们探讨了带有两个工件组的两台平行批处理机在线排序问题.目标函数足最小化最大完工时间.我们用对手策略证明了该问题任意在线算法的竞争比的下界是√5+1/2≈1.618.继而，我们给出了一个最好可能的在线算法，证明的算法的竞争比就是√5+1/2.　　 5.在第六章中，我们主要研究的是单台平行批处理机，批允许有限次重启的最小化最大完工时间的在线排序问题.我们首先证明该问题竞争比的下界是3/2，然后给出了个竞争比是3/2的最好可能的在线算法.在不允许重启的情形下，最好可能的在线算法是√5+1/2-竞争的.因此批允许重启使得我们得到了史好可能的在线算法.　　 6.在第七章中，我们研究的是允许有限次重启的两台半行批处理机在线排序问题.目标函数是最小化最大完工时间.在不允许重启的情形下，最好可能的在线算法是√2-竞争的.我们证明当批允许有限次重启时，任意在线算法竞争比的下界约为1.298，在second-restart的假设下（即只有两台机器都忙碌的时候才会考虑利用重启，并且每次都是重启开工时刻较晚的正在运行的一批），问题的下界是√3+1/2.接着，我们给出了一个竞争比是√3+1/2的在线算法.在second-restart的假设下，该算法是最好可能的.