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 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.
Accepté le :
DOI : 10.1051/ro/2017044
Mots clés : Scheduling, parallel machine, approximation
@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/
, and , Bounds for the optimal scheduling of jobs on processors. Manag. Sci. 11 (1964) 268–279. | DOI | MR
and , Fast approximation algorithms for job sequencing with deadlines. Discrete Appl. Math. 3 (1981) 313–318. | DOI | Zbl
and , Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM 22 (1975) 463–468. | DOI | MR | Zbl
, 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
, and , Strongly Fully Polynomial Time Approximation Scheme for the two-parallel capacitated machines scheduling problem. Int. J. Plann. Scheduling 1 (2011) 32–41. | DOI
, 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
and , 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
and , 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
and , Approximation algorithms for single machine scheduling with one unavailability period. 4OR: A Quarterly J. Oper. Res. 7 (2009) 79–92. | DOI | MR | Zbl
and , 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
and , Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications. Algorithmica 57 (2010) 769–795. | DOI | MR | Zbl
and , 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
and , Capacitated two-parallel machines sceduling to minimize sum of job completion times. Discrete Appl. Math. 41 (1993) 211–222. | DOI | MR | Zbl
, and , Minimizing the sum of job completion times on capacitated two-parallel machines. Eur. J. Oper. Res. 197 (2009) 475–481. | DOI | MR | Zbl
, Algorithms for scheduling independent tasks. J. ACM 23 (1976) 116–127. | DOI | MR | Zbl
, Scheduling with limited machine availability. Eur. J. Oper. Res. 121 (2000) 1–15. | DOI | MR | Zbl
, Various optimizers for single stage production. Nav. Res. Log. Quarterly 3 (1956) 59–66. | DOI | MR
, 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
, A strongly polynomial FPTAS for the symmetric quadratic knapsack problem. Eur. J. Oper. Res. 218 (2012) 377–381. | DOI | MR | Zbl
Cité par Sources :
