本文研究单机上的在线继列分批和离线混合分批排序.在线继列分批排序中,一个工件的信息只有当它到达后才被释放出来.一台批处理机可以同时将多个工件作为一个继列批进行加工,每个工件都有它自己的安装时间,批的加工时间为这一批里的所有工件的加工时间之和,批安装时间为这一批里工件的最大的安装时间,目标是最小化时间表长.利用排序问题的三参数表示法,该问题可表示为1｜s-batch,on-line,b=+∞,ri≤rj→si≥sj｜Cmax.　　 混合分批排序中,我们有两组工件JA和JB,分别称为A工件和B工件.这两组工件要在同一台可以对工件进行分批的机器上进行排序.但是,A工件和B工件不能放在同一批内进行加工.此外,A工件批为平行批,容量为b(A)；B工件批为继列批,容量为6(B),安装时间为s(B).利用排序问题的三参数表示法,该问题可表示为1｜s—p-batch,s(B),(b(A),b(B))｜γ.其中,γ∈{Cmax,Lmax,∑Gj,∑wjCj,fmax).　　 本文的主要内容如下:　　 第一章介绍了排序问题的背景和本文所研究问题的相关发展,并给出了相关排序问题的术语和记号.　　 第二章研究在线继列分批排序,给出排序问题1｜s-batch,on-line,b=+∞,ri≤rj→si≥sj｜Cmax的一个最好可能的在线算法,其竞争比为(√5+1)／2.　　 第三章研究单机两组工件继列分批与平行分批混合排序.主要结果如下:　　 ·排序问题1｜s-p-batch,s(B),(∞,∞)｜Lmax在O(nAnBn)时间可解.　　 ·排序问题1｜s-p-batch,s(B),(∞,b(B))｜∑Cj在O(nAnBn)时间可解.　　 ·排序问题1｜s-p-batch,pj=1,s(B),(b(A),b(B))｜∑wjCj在O(nAnBn)时间可解.　　 ·排序问题1｜s-p-batch,s(B),(∞,b(B))｜fmax可以在时间界为O(log(maxj fj(M))×(nlog M+nAnBn))内可解.其中,M是工件完工时间的一个上界.　　 文章最后总结了全文内容并提出了下一步需要做的问题.