In this paper a single machine time-dependent scheduling problem with total completion time criterion is considered. There are given n jobs J1,…,Jn and the processing time pi of the ith job is given by pi=a+bisi, where si is the starting time of the ith job (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>0, then for each >0 a solution with the value of the goal function that is at most 1+ times greater than the optimal one can be found. Consequently, the problem cannot be NP-hard in the strong sense.
Autorzy
Informacje dodatkowe
- DOI
- Cyfrowy identyfikator dokumentu elektronicznego link otwiera się w nowej karcie 10.1016/j.ejor.2009.07.025
- Kategoria
- Publikacja w czasopiśmie
- Typ
- artykuł w czasopiśmie wyróżnionym w JCR
- Język
- angielski
- Rok wydania
- 2009