Online scheduling with linear deteriorating jobs to minimize the total weighted completion time

In this paper, we study the online scheduling of linear deteriorating jobs on a single machine to minimize the total weighted completion time. In the problem, a set of n independent linear deteriorating jobs arriving online over time has to be scheduled on a single machine, where the information of each job including its deterioration rate and weight is unknown in advance. Linear deterioration means that the processing time pj of a job Jj is a linear function of its starting time sj . In this paper, we assume that $p_j=a_j(A+B{s}_j),$ where A and B are nonnegative with $A+B>0$ and aj ≥ 0 is the deterioration rate of Jj . The goal is to minimize the total weighted completion time, i.e., ΣwjCj . For this problem, we provide a best possible online algorithm with a competitive ratio of $1+\lambda \left(A\right)+a_{\max }B,$ where $a_{\max }={\max }_{1\le j\le n}{a}_j$ and $\lambda \left(A\right)=0$ or $\lambda \left(A\right)=1$ depending on whether $A=0$ or A > 0.