پایان نامه - مقاله و پروژه

تحقیق – طراحی یک مدل ریاضی وحل آن با الگوریتم های ابتکاری و فرا …

۲-۴-۲مسائل ماشینهای موازی
در ادبیات تحقیق زمانبندی ماشینهای موازی الگوریتمهای ابتکاری و فراابتکاری مختلفی به چشم میخورد که بخش زیادی از آن به ماشینهای موازی یکسان و یکنواخت مربوط میشود. گوینت و داساچوی[۲۸] مسأله زمانبندی ماشینهای موازی یکسان با محدودیت زمان نصب وابسته به توالی با تابع هدف زمان پایان کار ماکسیمم با استفاده از یک روش ابتکاری بر مبنای روش مجارستانی[۲۸]را بررسی نمودهاند.
کیم و شین[۳۸] یک الگوریتم جستجوی ممنوع را برای مسأله مشابهی با تابع هدف زمان تأخیر ماکسیمم ارائه کردند. این الگوریتم تعداد جستجوها را بدون حذف جوابها به طور قابل ملاحظهای کاهش میدهد. همچین، فاولر و همکارانش[۲۲] یک الگوریتم ژنتیک ترکیبی را در مسأله مشابهی برای توابع هدف مختلف شامل زمان پایان کار بیشینه، زمان تکمیل کار وزنی کل و زمان دیرکرد وزنی کل بکار گرفتند. این الگوریتم کارها را به ماشینها اختصاص میدهد و از قوانین توزیع برای زمانبندی ماشینها استفاده میکند. نتایج محاسباتی الگوریتم برای هر سه نوع معیار بهینهسازی ذکر شده، عملکرد بهتر آن را نسبت به الگوریتمهای قبلی نشان میدهد.
با وجود مطالعات فراوان صورت گرفته در زمینه ماشینهای موازی یکسان، مسائل زمانبندی ماشینهای موازی نامرتبط کمتر مورد توجه قرار گرفتهاند. این موضوع با در نظر گرفتن محدودیت زمان نصب ماشین بیش از پیش به چشم میآید. در ادامه تعدادی از مهمترین تحقیقات ارائه شده در این زمینه آدرسدهی میشوند:
ژو و هیدی[۶۷] مسأله زمانبندی ماشینهای موازی نامرتبط را با محدودیت زمان نصب وابسته به توالی کارها و تابع هدف مجموع زمانهای دیرکرد و زودکرد وزنی ارائه کردند. آنها یک مدل برنامهریزی عددصحیح برای این مسأله پیشنهاد مینمایند که به اندازه نه کار و سه ماشین در زمان محسباتی معقول به جواب بهینه میرسد.
ونگ و همکاران[۶۵] مسأله را با تابع هدف زمان پایان کار وزنی کل آدرسدهی نمودند. آنها هفت روش ابتکاری ساده را از طریق بررسی نتایج محاسباتی با یکدیگر مقایسه نموده و یکی از آنها را به عنوان بهترین روش انتخاب مینمایند. این روش هریک از کارها را بر اساس کوچکترین نرخ زمان پردازش به علاوه زمان نصب نسبت به وزن کار در تابع هدف به ماشینها اختصاص میدهد. آکیول و همکارانش[۲] با استفاده از شبکههای عصبی مصنوعی و روش تابع جریمه به حل مسألهای با تابع هدف زمانهای زودکرد و دیرکرد وزنی پرداختند. نتایج بدستآمده نشان میدهد که این روش به یک جواب بهینه مناسب دست مییابد بطوریکه انگیزه کاربرد آن در مسائل با اندازه بزرگتر را ایجاد میکند.
در جدول(۲-۲) خلاصهای از مطالب ارائه شده در این بخش نمایش داده شده است.
جدول۲-۲٫ مسائل ماشینهای موازی با محدودیت زمان نصب ماشین

رویکردها توابع ومحدودیتها نویسندگان
یک روش ابتکاری بر مبنای روش مجارستانی P| | گوینت و داساچوی
الگوریتم جستجوی ممنوع P| | کیم و شین
الگوریتم ژنتیک P| , | ,, فاولر و همکاران
برنامهریزی عددصحیح آمیخته R | , |+ ژو و هیدی
دانلود متن کامل پایان نامه در سایت jemo.ir موجود است