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 pj=αj(A+Bsj), 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)+αmaxB, where αmax=max1≤j≤nαj and λ(A)=0 or λ(A)=1 depending on whether A=0 or A > 0.