A FPTAS for minimizing total completion time in a single machine time-dependent scheduling problem

Krzysztof Ocetkiewicz

doi:10.1016/j.ejor.2009.07.025

A FPTAS for minimizing total completion time in a single machine time-dependent scheduling problem

Abstrakt

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.

Cytowania

8

CrossRef
0

Web of Science
9

Scopus

Autor (1)

Krzysztof Ocetkiewicz dr inż.

Cytuj jako

Pełna treść

pełna treść publikacji nie jest dostępna w portalu

pełna treść artykułu zobacz w serwisie zewnętrznym otwiera się w nowej karcie

Słowa kluczowe

Informacje szczegółowe

Kategoria:: Publikacja w czasopiśmie
Typ:: artykuł w czasopiśmie wyróżnionym w JCR
Opublikowano w:: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH nr 203,
ISSN: 0377-2217
Język:: angielski
Rok wydania:: 2009
Opis bibliograficzny:: Ocetkiewicz K.: A FPTAS for minimizing total completion time in a single machine time-dependent scheduling problem// EUROPEAN JOURNAL OF OPERATIONAL RESEARCH. -Vol. 203, nr. iss. 2, June. (2009),
DOI:: Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.ejor.2009.07.025
Weryfikacja:: Politechnika Gdańska