کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6896661 1446005 2015 32 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Single machine scheduling with two competing agents and equal job processing times
ترجمه فارسی عنوان
برنامه ریزی تک ماشین با دو عامل رقیب و زمان پردازش کار برابر است
کلمات کلیدی
برنامه زمانبندی واحد دو عامل رقیب، زمان پردازش برابر، پیچیدگی،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
چکیده انگلیسی
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
نویسندگان
, , ,