本文我们主要研究的是一类在线平行分批排序问题，并且批工件是允许重启(重新启动)的。用三参数法表示我们的模型即是： 1|on-line,rj；p-batch,b=∞；restarts|Cmax。所谓在线，这里我们指的是工件集是随时到达的，工件的所有性质(包括到达时间)在它到来之前都是未知的，工件在到来之前不能被安排作业，工件到达了也没有必要立即安排，一旦被安排就不能再改变。模型中平行分批是同时加工排序的一种情形，指的是若干工件可以放在一起作为一批在一台机器上同时加工，批中所有工件的开工时间相等，完工时间也认为相等，批的加工长度等于批中所有工件中最长的加工长度，批的完工时间也就等于工件中最大的完工时间。平行分批排序又可分为批容量无界和批容量有界两种类型，本文研究的是批容量无限制的情形，即一台机器可以同时加工任意多个工件。 下面我们对“重新启动”(简称重启)给出定义。所谓工件允许重启是指工件在加工过程中可以被打断让机器加工其他的工件，稍后再从头开始加工被打断的工件。也就说该工件中断前所消耗的时间都浪费了。而一批允许重启又与单个工件的重启有所不同，一批允许重启是指，我们可以打断当前正在加工的批，已经加工的部分全部作废，批中工件被释放出来，各自成为独立的未加工工件，它们可以与其它已经到达的未加工的工件重新组合成一批，再被加工。排序中允许重启可以降低错误的决策造成的损失。在实践中，操作需要重启的事情经常见到。比如冶金、集成电路产品的耐温性检测、程序的运行、网上下载文件等都是一次性完成的，如果被打断，必须从头开始操作。在一些排序模型中，重启起着很大的作用。例如在文献[13]中，重启对单机在线最小化最大运输时间的排序问题是有帮助的，M.V.D.Akker等作者给出一个竞争比是3/2的在线算法并且证明此算法是最具竞争性的，而相应的不允许工件重启的单机在线最小化最大运输时间的排序问题，最好的在线算法的竞争比是(√5+1)/2。文献[8]中，G.Zhang等人对问题1|on-line,rj；p-batch,b=∞|Cmax给出性能比为(√5+1)/2的在线算法，并且证明了它是最好可能的。我们在此模型的基础上加上批允许重启，即得到了本文所论述问题的模型：1|on-line,rj；p-batch,b=∞；restarts|Cmax。我们将证明此排序问题的任意在线算法的下界不小于(5-√5)/2≈1.3820，并给出一个竞争比不大于3/2的在线算法。