کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
477643 1446174 2008 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Worst-case analysis of the WSPT1 and MWSPT2 rules for single machine scheduling with one planned setup period
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
Worst-case analysis of the WSPT1 and MWSPT2 rules for single machine scheduling with one planned setup period
چکیده انگلیسی

In this article, we consider the single machine scheduling problem with one planned setup period, with the aim of minimizing the weighted sum of the completion times. We study the WSPT and MWSPT heuristics and we show that the worst-case performance ratio is 3 for the two heuristics in some cases and it is unbounded otherwise. We also show that these worst-case performance ratios are tight.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 187, Issue 3, 16 June 2008, Pages 1080–1089
نویسندگان
, ,