工件的释放时间和加工时间具有一致性, 是指释放时间大的工件其加工时间不小于释放时间小的工件的加工时间, 即若$r_{i}\geq r_{j}$, 则$p_{i}\geq p_{j}$。本文在该一致性约束下, 研究最小化最大加权完工时间单机在线排序问题, 和最小化总加权完工时间单机在线排序问题, 并分别设计出$\frac{\sqrt{5}+1}{2}$-竞争的最好可能在线算法。

There are $n$ jobs $J_1, J_2, \cdots, J_n$ to be scheduled on the single machine. Each job $J_{j}$ has a nonnegative arriving time $r_{j}$, a positive processing time $p_{j}$, and a nonnegative weight $w_{j}$. We consider one restricted model: the jobs have agreeable release times and processing times (i.e., if $r_{i}\geq r_{j}$, then $p_{i}\geq p_{j}$). Under this restricted model, we study the single-machine online schedule to minimize the maximum weighted completion time of jobs or the total weighted completion times of jobs. We present two best possible online algorithms with the competitive ratio of both $\frac{\sqrt{5}+1}{2}$.