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.

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
Mots-clés : 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://www.numdam.org/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://www.numdam.org/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://www.numdam.org/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. http://www.numdam.org/articles/10.1051/ro/2017044/

W.L. Eastman, S. Even and I.M. Issacs, Bounds for the optimal scheduling of n jobs on m processors. Manag. Sci. 11 (1964) 268–279. | DOI | MR

G.V. Gens and E.V. Levner, Fast approximation algorithms for job sequencing with deadlines. Discrete Appl. Math. 3 (1981) 313–318. | DOI | Zbl

O. Ibarra and C.E. Kim, Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM 22 (1975) 463–468. | DOI | MR | Zbl

I. Kacem, Approximation algorithms for the makespan minimization with positive tails on a single machine with a fixed non-availability interval. J. Combin. Optim.. 17 (2009) 117–133. | DOI | MR | Zbl

I. Kacem, Y. Lanuel and M. Sahnoune, Strongly Fully Polynomial Time Approximation Scheme for the two-parallel capacitated machines scheduling problem. Int. J. Plann. Scheduling 1 (2011) 32–41. | DOI

I. Kacem, Fully Polynomial-Time Approximation Scheme for the Weighted Total Tardiness Minimization with a Common Due Date. Discrete Appl. Math. 158 (2010) 1035–1040. | DOI | MR | Zbl

I. Kacem and H. Kellerer, Fast approximation algorithms to minimize a special weighted flow-time criterion on a single achine with a non-availability interval and release dates. J. Sched. 14 (2011) 257–265. | DOI | MR | Zbl

I. Kacem and R.A. Mahjoub, Fully Polynomial Time Approximation Scheme for the Weighted Flow-time Minimization on a Single Machine with a Fixed Non-Availability Interval. Comput. Ind. Eng. 56 (2009) 1708–1712. | DOI

I. Kacem and M. Haouari, Approximation algorithms for single machine scheduling with one unavailability period. 4OR: A Quarterly J. Oper. Res. 7 (2009) 79–92. | DOI | MR | Zbl

H. Kellerer and V.A. Strusevich, A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date. Theor. Comput. Sci. 369 (2006) 230–238. | DOI | MR | Zbl

H. Kellerer and V.A. Strusevich, Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications. Algorithmica 57 (2010) 769–795. | DOI | MR | Zbl

M.Y. Kovalyov and W. Kubiak, A fully polynomial approximation scheme for weighted earliness-tardiness problem. Oper. Res. 47 (1999) 757–761. | DOI | MR | Zbl

M.Y. Kovalyov and W. Kubiak, Fully polynomial approximation schemes for decomposable partition problems. Working Paper 98-15 of the Faculty of Business Administration, Memorial University of Newfoundland. Presentation in Operations Research Proceedings 1999, Selected papers of the Sympos. Oper. Res. (SOR 99), Magdeburg (1999) 397–401. | MR | Zbl

C.Y. Lee and S.D. Liman, Capacitated two-parallel machines sceduling to minimize sum of job completion times. Discrete Appl. Math. 41 (1993) 211–222. | DOI | MR | Zbl

C.-J. Liao, C-W. Chao and C.-H. Lin, Minimizing the sum of job completion times on capacitated two-parallel machines. Eur. J. Oper. Res. 197 (2009) 475–481. | DOI | MR | Zbl

S. Sahni, Algorithms for scheduling independent tasks. J. ACM 23 (1976) 116–127. | DOI | MR | Zbl

G. Schmidt, Scheduling with limited machine availability. Eur. J. Oper. Res. 121 (2000) 1–15. | DOI | MR | Zbl

W.E. Smith, Various optimizers for single stage production. Nav. Res. Log. Quarterly 3 (1956) 59–66. | DOI | MR

G.J. Woeginger, When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme (FPTAS)? INFORMS J. Comput. 12 (2000) 57–75. | DOI | MR | Zbl

Z. Xu, A strongly polynomial FPTAS for the symmetric quadratic knapsack problem. Eur. J. Oper. Res. 218 (2012) 377–381. | DOI | MR | Zbl

Cité par Sources :