ارایه ی یک مدل برنامه ریزی عددی صحیح جدید و یک حد پایین مناسب برای مسایل ماشین های موازی یکسان با معیار کمینه سازی دیرکرد کل کارها

در این مقاله مسیله ی توالی عملیات بر روی ماشین های موازی یکسان با معیار کمینه سازی مجموع دیر کرد کارها بررسی می شود. مد برنامه ریزی عدد صحیح مختلط کارایی برای مسیله ی مورد نظر ارایه می شود؛ سپس مدلی پیشنهادی برای به دست آوردن حد پایین بهتر و کاراتر از یکی از حدود پایین موجود در پیشینه ی پژوهش های مسیله ارایه می شود. مسیله ی ماشین های موازی یکسان با تابع هدف کمینه سازی مجموع دیرکرد کل کارها تعمیمی یافته ی مسیله ی تک ماشینی است و این مسیله جزء مسایل NP-hard دسته بندی می شود. از این رو مدل ارایه شده توانایی حل بهینه ی مسایل با اندازه ی بزرگ در زمان منطقی را ندارد. به همین دلیل برای حل مسیله در اندازه های متوسط و بزرگ و نیز ارزیابی کارایی حد پایین به دست آمده از مدل پیشنهادی و حد پایین موجود در پیشینه، الگوریتم فرا ابتکاری شبیه سازی تبرید اصلاح شده ای که برای اولین بار از عملگر تقاطع و جهش برای ایجاد جواب همسایگی بهره می برد، ارایه می شود.

Keywords:

ماشین های موازی , مجموع دیرکرد کل کارها , الگوریتم شبیه سازی , تبرید اصلاح شده , برنامه ریزی عددی صحیح مختلط