A new optimal algorithm for a time-dependent scheduling problem

In this article a single machine time-dependent sche- duling problem with total completion time criterion is considered. There are n given jobs, j1,...,jn, and the processing time pi of the i-th job is given by pi = 1 + bisi, where si is the starting time of the i-th job, i = 1,...n. If all jobs have different and non-zero deterioration rates and bi > bj ⇒ bi ≥ b min+1 bmin bj + 1 bmin , where bmin = min{bi}, then an optimal schedule can be found in O(nlogn) time. The conducted computational experiments show that the presented algorithm performs very well even on data not satisfying the assumed constraints.