کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1135529 | 956102 | 2009 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Fully polynomial time approximation scheme for the weighted flow-time minimization on a single machine with a fixed non-availability interval
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
سایر رشته های مهندسی
مهندسی صنعتی و تولید
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
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)O(n2/ε2) time complexity, where nn 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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Industrial Engineering - Volume 56, Issue 4, May 2009, Pages 1708–1712
Journal: Computers & Industrial Engineering - Volume 56, Issue 4, May 2009, Pages 1708–1712
نویسندگان
Imed Kacem, A. Ridha Mahjoub,