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

Abstract

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.

Citations

8

CrossRef
0

Web of Science
9

Scopus

Author (1)

Krzysztof Ocetkiewicz dr inż.

Cite as

Full text

full text is not available in portal

full content of the article see on external site open in new tab

Keywords

Details

Category:: Articles
Type:: artykuł w czasopiśmie wyróżnionym w JCR
Published in:: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH no. 203,
ISSN: 0377-2217
Language:: English
Publication year:: 2009
Bibliographic description:: 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:: Digital Object Identifier (open in new tab) 10.1016/j.ejor.2009.07.025
Verified by:: Gdańsk University of Technology