排序论是运筹学与组合最优化的重要分支.分批排序是人们十分关注的现代排序模型;其特点是可将工件分批进行加工,每一批工件具有相同的开工时间和相同的完工时间.在本文研究的平行分批排序模型中,每一批的加工时间等于该批中工件的最长加工时间.按照每一批可以加工的工件数目b的限制(称为批容量),平行分批排序又可分为批容量有限(b<∞)和批容量无限(b=∞)两种情形.在线排序问题是近年来排序论研究的热点方向;其特点是工件的信息事先并不确定,决策者在没有获得所有工件信息之前就必须对已有工件进行排序.本文所研究的在线排序是工件实时到达(over time)的情形,即工件是随着时间逐渐到达的.工件的所有信息在其到达时刻才能获知.针对在线优化问题设计的算法称为在线算法.　　人们常用竞争比来衡量在线算法性能的好坏.对于一个极小化目标函数的优化问题,我们称一个在线算法是ρ-竞争的,如果对于该问题的任意实例,算法所产生的目标函数值不大于最优离线算法所产生的目标函数值的ρ倍.在线算法 A的竞争比定义为ρA= inf{ρ: A是ρ-竞争的}.不难看出,ρA总是大于等于1的.由于信息的缺乏,ρA=1的情形只有在很特殊的问题上才会出现.一般而言,ρA越是接近于1,在线算法A的性能越好.如果不存在竞争比小于ρA的其他在线算法,就称算法A是该问题的最好可能的的在线算法.　　为了得到性能更好的在线算法,人们常常允许工件重启.这里的“重启”指的是:我们可以中断正在加工的工件或工件批,中断加工的工件被重新释放出来(以前的加工作废)再重新安排加工.允许工件重启给了我们纠正错误的机会,但重启次数过多很容易造成资源的浪费和工件的损坏.因此,在线算法的设计中,有限重启也是人们采用的策略.本文中,有限重启指的是:每个工件最多只能重启一次,相应地,如果一个正在加工的批里面包含有被中断重启过的工件,这个批就不能被中断了.　　本学位论文研究工件允许重启或有限重启的在线平行分批排序问题.对所研究的四个在线排序问题,均给出了最好可能的在线算法.学位论文的结构如下.　　第一章介绍了排序论中的基本概念,常用符号和相关的研究进展.　　第二章研究了等长工件在 m台容量无限的平行批处理机上加工,工件允许有限重启,目标函数是最小化最大完工时间的在线排序问题.对于该问题我们设计出了一个竞争比为1+αm的最好可能的在线算法.不同于已有文献中的竞争比的显式表达式,这里的1+αm是由一个算法确定的.　　第三章研究了等长工件在一台容量有限的平行批处理机上加工,工件允许有限重启,目标函数是最小化最大完工时间的在线排序问题.令α是方程(1+x)(2x2+4x+1)=3的正根.β是方程 x(1+x)2=1的正根.当批容量为2时,我们给出了一个竞争比为(1+α)的最好可能的在线算法.当批容量大于等于3时,我们给出了一个竞争比为(1+β)的最好可能的在线算法.　　第四章研究了等长工件在一台容量有限的平行批处理机上加工,工件允许重启,目标函数是最小化最大完工时间的在线排序问题.令γ是方程x(x+1)(2x+3)=2的正根.?是方程x(x+1)(2x+1)=1的正根.当批容量为2时,我们证明了第三章中允许有限重启时批容量为2的情形的最好可能的在线算法也是允许重启时的最好可能的在线算法.当批容量为3时,我们给出了一个竞争比为(1+γ)的最好可能的在线算法.当批容量大于等于4时,我们给出了一个竞争比为(1+?)的最好可能的在线算法.　　第五章研究了等长工件在一台容量有限的平行批处理机上加工,工件允许有限重启且目标函数是最小化最大运输完工时间的在线排序问题.令α是方程2x(1+x)=1的正根.β是方程x(1+x)2=1的正根.当批容量为2时,我们给出了一个竞争比为(1+α)的最好可能的在线算法.当批容量大于等于3时,我们给出了一个竞争比为(1+β)的最好可能的在线算法.