Abstract:

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

Key words: single machine, online scheduling, online algorithm, weighted completion time