Geodesic
Strongly Fully Polynomial Time Approximation Scheme for the weighted completion time minimization problem on two-parallel capacitated machines
Kacem, Imed1  ; Sahnoune, Myriam1   ; Schmidt, Günter2
1 Université de Lorraine, LCOMS EA 7306, 57000, Metz, France.
2 Universität des Saarlandes, ORBI, Sarbrucken, Germany.
RAIRO - Operations Research - Recherche Opérationnelle, Tome 51 (2017) no. 4, pp. 1177-1188

Voir la notice de l'article provenant de la source Numdam

We consider the total weighted completion time minimization for the two-parallel capacitated machines scheduling problem. In this problem, one of the machines can process jobs until a certain time T 1 after which it is no longer available. The other machine is continuously available for performing jobs at any time. We prove the existence of a strongly Fully Polynomial Time Approximation Scheme (FPTAS) for the studied problem, which extends the results for the unweighted version (see [I. Kacem, Y. Lanuel and M. Sahnoune, Strongly Fully Polynomial Time Approximation Scheme for the two-parallel capacitated machines scheduling problem, Int. J. Plann. Sched. 1 (2011) 32–41]). Our FPTAS is based on the simplification of a dynamic programming algorithm. Moreover, we present a set of numerical experiments and we discuss the results.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2017044
Classification : 90C59, 90C39, 90B35
Keywords: Scheduling, parallel machine, approximation

Kacem, Imed 1 ; Sahnoune, Myriam 1 ; Schmidt, Günter 2

1 Université de Lorraine, LCOMS EA 7306, 57000, Metz, France.
2 Universität des Saarlandes, ORBI, Sarbrucken, Germany. 
@article{RO_2017__51_4_1177_0,
     author = {Kacem, Imed and Sahnoune, Myriam and Schmidt, G\"unter},
     title = {Strongly {Fully} {Polynomial} {Time} {Approximation} {Scheme} for the weighted completion time minimization problem on two-parallel capacitated machines},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {1177--1188},
     publisher = {EDP-Sciences},
     volume = {51},
     number = {4},
     year = {2017},
     doi = {10.1051/ro/2017044},
     mrnumber = {3783940},
     zbl = {1395.90148},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ro/2017044/}
}
TY  - JOUR
AU  - Kacem, Imed
AU  - Sahnoune, Myriam
AU  - Schmidt, Günter
TI  - Strongly Fully Polynomial Time Approximation Scheme for the weighted completion time minimization problem on two-parallel capacitated machines
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2017
SP  - 1177
EP  - 1188
VL  - 51
IS  - 4
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ro/2017044/
DO  - 10.1051/ro/2017044
LA  - en
ID  - RO_2017__51_4_1177_0
ER  - 
%0 Journal Article
%A Kacem, Imed
%A Sahnoune, Myriam
%A Schmidt, Günter
%T Strongly Fully Polynomial Time Approximation Scheme for the weighted completion time minimization problem on two-parallel capacitated machines
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2017
%P 1177-1188
%V 51
%N 4
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ro/2017044/
%R 10.1051/ro/2017044
%G en
%F RO_2017__51_4_1177_0
Kacem, Imed; Sahnoune, Myriam; Schmidt, Günter. Strongly Fully Polynomial Time Approximation Scheme for the weighted completion time minimization problem on two-parallel capacitated machines. RAIRO - Operations Research - Recherche Opérationnelle, Tome 51 (2017) no. 4, pp. 1177-1188. doi: 10.1051/ro/2017044

Cité par Sources :