کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
475405 699303 2016 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A fast and effective subset sum based improvement procedure for workload balancing on identical parallel machines
ترجمه فارسی عنوان
در مجموع زیر مجموعه روش سریع و موثر بر بهبود حجم کار تعادل در ماشین های موازی یکسان
کلمات کلیدی
برنامه ریزی دستگاه های موازی مشابه تعادل کار؛ NSSWD-معیار؛ اهریمنی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
چکیده انگلیسی


• We minimize the normalized sum of squared workload deviations to balance workload.
• We develop an exact algorithm for the case of three machines.
• We propose an effective subset sum based local search procedure for multiple machines.
• The innovation is to use triples of machines as a neighborhood instead of pairs.
• We optimally solve 98% of the benchmark instances within very short computation time.

The paper on hand addresses the workload balancing problem that asks for an assignment of n independent jobs to m identical parallel machines so that the normalized sum of squared workload deviations (NSSWD-criterion) is minimized. For the special case of m  =3 machines we propose an exact algorithm that requires solving a sequence of subset sum problems. This algorithm also builds the core of our local search procedure for solving the general case of m≥3m≥3 machines. The main innovation of our approach compared to existing methods, therefore, consists in using triples of machines as a neighborhood instead of pairs of machines. Results of a comprehensive computational study on the benchmark library established by Ho et al. [10] and Cossari et al. [5] attest to the effectiveness of our approach. In addition, we demonstrate its capability to determine high-quality solutions for further balancing criteria as discussed in Cossari et al. [6].

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 73, September 2016, Pages 84–91
نویسندگان
, ,