کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6896661 | 1446005 | 2015 | 32 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Single machine scheduling with two competing agents and equal job processing times
ترجمه فارسی عنوان
برنامه ریزی تک ماشین با دو عامل رقیب و زمان پردازش کار برابر است
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
برنامه زمانبندی واحد دو عامل رقیب، زمان پردازش برابر، پیچیدگی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
چکیده انگلیسی
We study various two-agent scheduling problems on a single machine with equal job processing times. The equal processing time assumption enables us to design new polynomial-time or faster-than-known optimization algorithms for many problems. We prove, however, that there exists a subset of problems for which the computational complexity remains NP-hard. The set of hard problems includes different variations where the objective functions of the two agents are either minimizing the weighted sum of completion times or the weighted number of tardy jobs. For these problems, we present pseudo-polynomial time algorithms.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 244, Issue 1, 1 July 2015, Pages 86-99
Journal: European Journal of Operational Research - Volume 244, Issue 1, 1 July 2015, Pages 86-99
نویسندگان
Daniel Oron, Dvir Shabtay, George Steiner,