Geodesic
Improving the solution complexity of the scheduling problem with deadlines: A general technique
Elalouf, Amir1 ; Levner, Eugene2 
1 Bar Ilan University, Ramat Gan, Israel.
2 Ashkelon Academic College, Ashkelon, Israel.
RAIRO - Operations Research - Recherche Opérationnelle, Special issue - Advanced Optimization Approaches and Modern OR-Applications, Tome 50 (2016) no. 4-5, pp. 681-687

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

The aim of this paper is to develop improved polynomial-time approximation algorithms belonging to the family of the fully polynomial time approximation schemes (FPTAS) for a group of scheduling problems. In particular, the new technique provides a positive answer to a question posed more than three decades ago by Gens and Levner [G.V. Gens and E.V. Levner, Discrete Appl. Math. 3 (1981) 313–318]: “Can an epsilon-approximation algorithm be found for the minimization version of the job-sequencing-with-deadlines problem running with the same complexity as the algorithms for the maximization form of the problem?”

Reçu le :
Accepté le :
DOI : 10.1051/ro/2016021
Classification : 41A29, 41A10, 65D15, 65Y10, 68Q25
Keywords: Job-sequencing-with-deadlines scheduling problem, approximation algorithm, FPTAS

Elalouf, Amir 1 ; Levner, Eugene 2

1 Bar Ilan University, Ramat Gan, Israel.
2 Ashkelon Academic College, Ashkelon, Israel. 
@article{RO_2016__50_4-5_681_0,
     author = {Elalouf, Amir and Levner, Eugene},
     title = {Improving the solution complexity of the scheduling problem with deadlines: {A} general technique},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {681--687},
     publisher = {EDP-Sciences},
     volume = {50},
     number = {4-5},
     year = {2016},
     doi = {10.1051/ro/2016021},
     zbl = {1357.90052},
     mrnumber = {3570524},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ro/2016021/}
}
TY  - JOUR
AU  - Elalouf, Amir
AU  - Levner, Eugene
TI  - Improving the solution complexity of the scheduling problem with deadlines: A general technique
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2016
SP  - 681
EP  - 687
VL  - 50
IS  - 4-5
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ro/2016021/
DO  - 10.1051/ro/2016021
LA  - en
ID  - RO_2016__50_4-5_681_0
ER  - 
%0 Journal Article
%A Elalouf, Amir
%A Levner, Eugene
%T Improving the solution complexity of the scheduling problem with deadlines: A general technique
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2016
%P 681-687
%V 50
%N 4-5
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ro/2016021/
%R 10.1051/ro/2016021
%G en
%F RO_2016__50_4-5_681_0
Elalouf, Amir; Levner, Eugene. Improving the solution complexity of the scheduling problem with deadlines: A general technique. RAIRO - Operations Research - Recherche Opérationnelle, Special issue - Advanced Optimization Approaches and Modern OR-Applications, Tome 50 (2016) no. 4-5, pp. 681-687. doi: 10.1051/ro/2016021

Cité par Sources :