کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
480579 | 1446127 | 2010 | 5 صفحه PDF | دانلود رایگان |
In this paper a single machine time-dependent scheduling problem with total completion time criterion is considered. There are given n jobs J1,…,JnJ1,…,Jn and the processing time pipi of the i th job is given by pi=a+bisipi=a+bisi, where sisi is the starting time of the i th job (i=1,…,n),bi(i=1,…,n),bi is its deterioration rate and a is the common base processing time. If all jobs have deterioration rates different and not smaller than a certain constant u>0u>0, then for each ϵ>0ϵ>0 a solution with the value of the goal function that is at most 1+ϵ1+ϵ times greater than the optimal one can be found. We give a FPTAS that finds such a solution in On1+6log1+u21ϵ2log1+u2 time. Consequently, the problem cannot be NP-hard in the strong sense.
Journal: European Journal of Operational Research - Volume 203, Issue 2, 1 June 2010, Pages 316–320