Fully polynomial time approximation scheme for the weighted flow-time minimization on a single machine with a fixed non-availability interval. Kacem, I. & Mahjoub, A. R. Computers & Industrial Engineering, 56(4):1708--1712, May, 2009.
Paper doi abstract bibtex 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/[epsilon]2) time complexity, where n is the number of jobs and [epsilon] 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.
@article{kacem_fully_2009,
title = {Fully polynomial time approximation scheme for the weighted flow-time minimization on a single machine with a fixed non-availability interval},
volume = {56},
issn = {0360-8352},
url = {http://www.sciencedirect.com/science/article/B6V27-4TMBPR2-1/2/85c7578087c76c1721ac3d137884b18c},
doi = {10.1016/j.cie.2008.09.042},
abstract = {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/[epsilon]2) time complexity, where n is the number of jobs and [epsilon] 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.},
number = {4},
urldate = {2009-08-06TZ},
journal = {Computers \& Industrial Engineering},
author = {Kacem, Imed and Mahjoub, A. Ridha},
month = may,
year = {2009},
keywords = {Approximation, Non-availability constraint, Weighted flow-time, fptas, scheduling},
pages = {1708--1712}
}
Downloads: 0
{"_id":"SQEkS4hrZiLkuxp3c","bibbaseid":"kacem-mahjoub-fullypolynomialtimeapproximationschemefortheweightedflowtimeminimizationonasinglemachinewithafixednonavailabilityinterval-2009","downloads":0,"creationDate":"2016-12-19T20:50:58.810Z","title":"Fully polynomial time approximation scheme for the weighted flow-time minimization on a single machine with a fixed non-availability interval","author_short":["Kacem, I.","Mahjoub, A. R."],"year":2009,"bibtype":"article","biburl":"http://bibbase.org/zotero/verschae","bibdata":{"bibtype":"article","type":"article","title":"Fully polynomial time approximation scheme for the weighted flow-time minimization on a single machine with a fixed non-availability interval","volume":"56","issn":"0360-8352","url":"http://www.sciencedirect.com/science/article/B6V27-4TMBPR2-1/2/85c7578087c76c1721ac3d137884b18c","doi":"10.1016/j.cie.2008.09.042","abstract":"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/[epsilon]2) time complexity, where n is the number of jobs and [epsilon] 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.","number":"4","urldate":"2009-08-06TZ","journal":"Computers & Industrial Engineering","author":[{"propositions":[],"lastnames":["Kacem"],"firstnames":["Imed"],"suffixes":[]},{"propositions":[],"lastnames":["Mahjoub"],"firstnames":["A.","Ridha"],"suffixes":[]}],"month":"May","year":"2009","keywords":"Approximation, Non-availability constraint, Weighted flow-time, fptas, scheduling","pages":"1708--1712","bibtex":"@article{kacem_fully_2009,\n\ttitle = {Fully polynomial time approximation scheme for the weighted flow-time minimization on a single machine with a fixed non-availability interval},\n\tvolume = {56},\n\tissn = {0360-8352},\n\turl = {http://www.sciencedirect.com/science/article/B6V27-4TMBPR2-1/2/85c7578087c76c1721ac3d137884b18c},\n\tdoi = {10.1016/j.cie.2008.09.042},\n\tabstract = {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.\nIn this paper, we propose a fully polynomial-time approximation scheme to minimize the total weighted completion time. The FPTAS has O(n2/[epsilon]2) time complexity, where n is the number of jobs and [epsilon] 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.},\n\tnumber = {4},\n\turldate = {2009-08-06TZ},\n\tjournal = {Computers \\& Industrial Engineering},\n\tauthor = {Kacem, Imed and Mahjoub, A. Ridha},\n\tmonth = may,\n\tyear = {2009},\n\tkeywords = {Approximation, Non-availability constraint, Weighted flow-time, fptas, scheduling},\n\tpages = {1708--1712}\n}\n\n","author_short":["Kacem, I.","Mahjoub, A. R."],"key":"kacem_fully_2009","id":"kacem_fully_2009","bibbaseid":"kacem-mahjoub-fullypolynomialtimeapproximationschemefortheweightedflowtimeminimizationonasinglemachinewithafixednonavailabilityinterval-2009","role":"author","urls":{"Paper":"http://www.sciencedirect.com/science/article/B6V27-4TMBPR2-1/2/85c7578087c76c1721ac3d137884b18c"},"keyword":["Approximation","Non-availability constraint","Weighted flow-time","fptas","scheduling"],"downloads":0,"html":""},"search_terms":["fully","polynomial","time","approximation","scheme","weighted","flow","time","minimization","single","machine","fixed","non","availability","interval","kacem","mahjoub"],"keywords":["approximation","non-availability constraint","weighted flow-time","fptas","scheduling"],"authorIDs":[],"dataSources":["TJDe75XCoX4GYYsBX"]}