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.
Fully polynomial time approximation scheme for the weighted flow-time minimization on a single machine with a fixed non-availability interval [link]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