Abstract:

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}$.

Key words: online scheduling, online algorithm, agreeable, weighted completion times