کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
475842 699383 2010 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Improved polynomial algorithms for robust bottleneck problems with interval data
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
Improved polynomial algorithms for robust bottleneck problems with interval data
چکیده انگلیسی

To model uncertainties in a problem one can provide intervals of uncertainty specifying a range for each uncertain parameter value. To hedge against ‘worst-case scenarios’, i.e., most unwelcome realizations of the uncertain parameters after a solution has been determined, the minmax-regret criterion has been adopted in robust optimization. Within this field, we consider bottleneck problems with one or more uncertain parameter functions.We apply a known polynomial time solution scheme for a number of specific problems of this type with one uncertain parameter function. This leads to improved algorithms of reduced complexity, e.g., for the bottleneck Steiner tree problem and the bottleneck assignment problem.Further, we formulate a framework to solve single machine scheduling problems in polynomial time under the maximum tardiness criterion, with up to three uncertain parameter functions.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 37, Issue 5, May 2010, Pages 909–915
نویسندگان
, ,