کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6896853 | 1446012 | 2015 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An improved heuristic for parallel machine scheduling with rejection
ترجمه فارسی عنوان
بهبودی اکتشافی برای برنامه ریزی موازی با رد
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
برنامه ریزی، طرد شدن، ابتکاری، بدترین حالت،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
چکیده انگلیسی
In this paper we study a classical parallel machine scheduling model with m machines and n jobs, where each job is either accepted and then processed by one of the machines, or rejected and then a rejection penalty is paid. The objective is to minimize the completion time of the last accepted job plus the total penalty of all rejected jobs. The scheduling problem is known to be NP-hard in the strong sense. We find some new optimal properties and develop an O(nlogân + n/ε) heuristic to solve the problem with a worst-case bound of 1.5 + ε, where ε > 0 can be any small given constant. This improves upon the worst-case bound 2â1m of the heuristic presented by Bartal et al. (Bartal, Y., Leonardi, S., Marchetti-Spaccamela, A., Sgall, J., & Stougie, L. (2000). Multiprocessor scheduling with rejection. SIAM Journal on Discrete Mathematics, 13, 64-78) in the scheduling literature.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 241, Issue 3, 16 March 2015, Pages 653-661
Journal: European Journal of Operational Research - Volume 241, Issue 3, 16 March 2015, Pages 653-661
نویسندگان
Jinwen Ou, Xueling Zhong, Guoqing Wang,