کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
10523893 957133 2016 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Splitting versus setup trade-offs for scheduling to minimize weighted completion time
ترجمه فارسی عنوان
تقسیم کردن در مقابل تعویض تنظیم برای برنامه ریزی برای به حداقل رساندن زمان اتمام وزن
کلمات کلیدی
برنامه ریزی، مشاغل تقسیم شده، زمان اتمام وزن،
ترجمه چکیده
ما در حال بررسی مشکلات برنامه ریزی زمانی که شغل ها می توانند تقسیم شوند و قبل از پردازش هر بخش، قبل از پردازش مورد نیاز باشد، برای به حداقل رساندن مجموع وزن زمان های تکمیل. با استفاده از یک استراتژی تقسیم ساده و کاهش به یک برنامه زمانبندی سفارشات، یک الگوریتم تقریبی 2 برای این مورد با وزن و تنظیم یکنواخت دریافت می کنیم که بر کار قبلی بهبود می یابد. ما این ایده را به حالت کلی یکسان ماشین گسترش می دهیم و با طراحی یک الگوریتم تقریبی عامل ثابت زمانی که ماشین ها ارتباطی ندارند، نتیجه گیری می شود.
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش مقاله
تقسیم کردن در مقابل تعویض تنظیم برای برنامه ریزی برای به حداقل رساندن زمان اتمام وزن
چکیده انگلیسی
We study scheduling problems when jobs can be split and a setup is required before processing each part, to minimize the weighted sum of completion times. Using a simple splitting strategy and a reduction to an orders scheduling problem we derive a 2-approximation algorithm for the case with uniform weights and setups, improving upon previous work. We extend this idea to the general identical machine case and conclude by designing a constant factor approximation algorithm when machines are unrelated.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Operations Research Letters - Volume 44, Issue 4, July 2016, Pages 469-473
نویسندگان
, , ,