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 = α j ( A + B s j ) , where A and B are nonnegative with A + B 0 and αj ? 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 + λ ( A ) + α max B , where α max = max 1 ? j ? n α j and λ ( A ) = 0 or λ ( A ) = 1 depending on whether A = 0 or A > 0.