在线排序研究具有重要的理论意义和实际应用价值。近二十年来,在线排序得到国内外同行的广泛关注和深入研究,并促使其成为现代排序领域中发展最为迅速的方向之一。本文所说的“在线”是指时间在线(online over time)。也就是说,工件是随着时间依次到达的,并且事先不知道它的一切信息。求解在线问题的算法称为在线算法。对一个最小化目标函数的在线排序问题,在线算法A的竞争比定义为ρA=sup{A(I)/OPT(I):I是满足OPT(I)>0的任一实例}.由此可见,竞争比越接近于1,就表明在线算法的性能越优良。如果不存在其他的竞争比小于A的竞争比的在线算法,就称在线算法A是最好可能的(best possible)。工件的加权完工时间和是排序的主要优化指标之一。本学位论文研究了若干与最小化工件的加权完工时间和相关的在线排序问题。学位论文共有六章:第一章主要介绍了一些与组合最优化以及排序问题相关的概念,并介绍了在线排序的研究现状,特别是最小化加权完工时间和的在线排序的研究现状。第二章研究了工件可拒绝的在线排序,其中每个工件Jj或者被拒绝加工并支付拒绝费用ej,或者被机器接收并加工。目标是最小化接收工件的加权完工时间和加上被拒绝工件的拒绝费用和。?对于一台机器工件有相同的权重且加工时间和拒绝费用满足一致性条件的情形,给出了一个竞争比为2的最好可能的在线算法DSPTR。?对于一台机器上问题的一般情形,给出了一个竞争比为2的最好可能的在线算法DSWPTR,推广了Anderson和Potts发表于《Mathematics of Operations Research,2004》的结果。该结果也是本章上一个结果的推广,但是论证技巧上截然不同。我们首先将在线算法柔性化,然后采用实例归结的技巧进行论证。?在多台恒同机(identical machines)上,我们给出了一个竞争比至多为4+的在线算法,在多台无关机(unrelated machines)上,我们给出了一个竞争比至多为8的在线算法。第三章研究了一台机器最小化时间表长和加权完工时间和的在线折衷排序问题。我们引入了最小化f1和f2的在线折衷排序。称一个在线算法A是(ρ1,ρ2)-竞争的,如果最小化f1时A是ρ1-竞争的而最小化f2时A是ρ2-竞争的。对于一个(ρ1,ρ2)-竞争的在线算法A,如果不存在(ρ1,ρ2)-竞争的在线算法A满足(ρ1,ρ2)≤(ρ1,ρ2)并且有ρ1<ρ1或者ρ2<ρ2,则在线算法A被称为是不可支配的(nondominated).?对于该问题,我们给出了一个参数在线算法,并利用两种不同的方法分别证明了该算法对于满足0<α≤1的任意α是一个竞争比为(1+α,1+1/α)的不可支配的在线算法。此结果推广了Anderson和Potts发表于《Mathematics of Operations Research,2004》的结果。第四章研究了多台平行批机器上批容量有限目标函数为最小化加权完工时间和的在线排序问题。?在一致机(uniform machines)上,当机器台数m为常数时,我们得到了一个竞争比至多为4+的在线算法。?在恒同机上,当机器台数m任意时,我们也得到了一个竞争比至多为4+的在线算法。该项工作改进了Zhang等人发表于《Journal of Industrial and Management Optimization,2007》对此问题给出的竞争比至多为8的在线算法。第五章研究了一台机器上工件加工时间可退化的最小化加权完工时间和的在线排序问题。在该问题中,工件Jj的加工时间为pj=αj(A+Bsj),其中A≥0,B≥0,A和B至少有一个非零,αj≥0是工件Jj的退化率,sj≥0是工件Jj的开工时间。?我们给出了一个竞争比为1+λ(A)+αmaxB的最好可能的在线算法,其中αmax=max1≤j≤nαj,而λ(A)=0或λ(A)=1取决于A=0或A>0。该项工作将Liu等人发表于《Theoretical Computer Science,2012》的简单线性退化并且工件权重都相等时的结果推广到了线性退化并且工件权重不同的更一般的情形。第六章总结了本学位论文所研究的主要内容和取得的一些主要结果,并指出了存在的一些问题以及未来的一些研究方向。