Show simple item record

dc.contributor.authorKacem, Imed
dc.contributor.authorMahjoub, Ali Ridha
dc.date.accessioned2010-01-18T12:17:14Z
dc.date.available2010-01-18T12:17:14Z
dc.date.issued2009
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/3020
dc.language.isoenen
dc.subjectFPTASen
dc.subjectWeighted flow-timeen
dc.subjectNon-availibility constrainten
dc.subjectApproximationen
dc.subjectSchedulingen
dc.subject.ddc005en
dc.titleFully polynomial time approximation scheme for the weighted flow-time minimization on a single machine with a fixed non-availability intervalen
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherUniversité de Technologie de Troyes, Troyes;France
dc.description.abstractenIn 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.isversionofjnlnameComputers and Industrial Engineering
dc.relation.isversionofjnlvol56en
dc.relation.isversionofjnlissue4en
dc.relation.isversionofjnldate2009-05
dc.relation.isversionofjnlpages1708-1712en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.cie.2008.09.042en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelProgrammation, logiciels, organisation des donnéesen


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record