本文考虑了最小化最大加权完工时间的单机在线排序问题, 要求工件的权重在工件加工时间一定范围之内且工件的权重和工件加工时间具有一致性, 即$ ap_j\leq w_j\leq bp_j (a\geq\frac{\sqrt{5}-1}{2}b, b\geq a)$且若$ w_i>w_j$则$ p_i\geq p_j$, 如果$ w_i=w_j$则$ p_i=p_j$。工件以时间在线的方式到达, 只有工件$ J_j$在达到释放时间$ r_j$后, 决策者才知晓工件的基本信息, 如加工时间$ p_j$和权重$ w_j$。对于此问题, 首先利用对手法证明了其下界为$ 1+\frac{b}{b+a}$, 随后给出了竞争比为$ 1+\frac{b}{b+a}$的最好可能的在线算法。特别地, 当$ a=\frac{\sqrt{5}-1}{2}b$时, 该算法的竞争比为$ \frac{\sqrt{5}+1}{2}$。

The setting we consider is nonpreemptive single machine online scheduling, with the objective to minimize the maximum weighted completion time of jobs. The weight of the job is not only limited strictly within the processing time compass of this job, but also agreeable with processing time of this job, i.e., $ ap_j\leq w_j\leq bp_j(a\geq\frac{\sqrt{5}-1}{2}b, b\geq a)$ and if $ w_i>w_j$, then $ p_i\geq p_j$. Especially, if $ w_i=w_j$, then $ p_i=p_j$. Significantly, there are irrelevant jobs arriving online over time and the knowledge of each job $ J_j$, such as its processing length $ p_j$ and weight $ w_j$, is not revealed for the scheduler until it is released at time $ r_j$. By means of adversary method, it is explicitly derived that the lower bound of the considered problem is $ 1+\frac{b}{b+a}$. Then we provide a best possible online algorithm with the competitive ratio of $ 1+\frac{b}{b+a}$. Moreover, the competitive ratio of this algorithm is $ \frac{\sqrt5+1}{2}$, when $ a=\frac{\sqrt{5}-1}{2}b$.