| dc.contributor.author | Kacem, Imed | |
| dc.contributor.author | Mahjoub, Ali Ridha | |
| dc.date.accessioned | 2010-01-18T12:17:14Z | |
| dc.date.available | 2010-01-18T12:17:14Z | |
| dc.date.issued | 2009 | |
| dc.identifier.uri | https://basepub.dauphine.fr/handle/123456789/3020 | |
| dc.language.iso | en | en |
| dc.subject | FPTAS | en |
| dc.subject | Weighted flow-time | en |
| dc.subject | Non-availibility constraint | en |
| dc.subject | Approximation | en |
| dc.subject | Scheduling | en |
| dc.subject.ddc | 005 | en |
| dc.title | Fully polynomial time approximation scheme for the weighted flow-time minimization on a single machine with a fixed non-availability interval | en |
| dc.type | Article accepté pour publication ou publié | |
| dc.contributor.editoruniversityother | Université de Technologie de Troyes, Troyes;France | |
| dc.description.abstracten | In a recent paper [Theoretical Computer Science 363, 257–265], He, Zhong and Gu considered the non-resumable case of the scheduling problem with a fixed non-availability interval under the non-resumable scenario. They proposed a polynomial time approximation scheme (PTAS) to minimize the total completion time.
In this paper, we propose a fully polynomial-time approximation scheme to minimize the total weighted completion time. The FPTAS has O(n2/ε2) time complexity, where n is the number of jobs and ε is the required error bound. The proposed FPTAS outperforms all the previous approximation algorithms designed for this problem and its running time is strongly polynomial. | en |
| dc.relation.isversionofjnlname | Computers and Industrial Engineering | |
| dc.relation.isversionofjnlvol | 56 | en |
| dc.relation.isversionofjnlissue | 4 | en |
| dc.relation.isversionofjnldate | 2009-05 | |
| dc.relation.isversionofjnlpages | 1708-1712 | en |
| dc.relation.isversionofdoi | http://dx.doi.org/10.1016/j.cie.2008.09.042 | en |
| dc.description.sponsorshipprivate | oui | en |
| dc.relation.isversionofjnlpublisher | Elsevier | en |
| dc.subject.ddclabel | Programmation, logiciels, organisation des données | en |
