کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4626057 | 1631782 | 2016 | 14 صفحه PDF | دانلود رایگان |
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),pj=αj(A+Bsj), where A and B are nonnegative with A+B>0A+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,1+λ(A)+αmaxB, where αmax=max1≤j≤nαjαmax=max1≤j≤nαj and λ(A)=0λ(A)=0 or λ(A)=1λ(A)=1 depending on whether A=0A=0 or A > 0.
Journal: Applied Mathematics and Computation - Volume 273, 15 January 2016, Pages 570–583