سامانه پژوهشی – زمان بندی ماشین های موازی نامرتبط به همراه دوباره کاری با در …

سطح

۴-۹٫ نتایج محاسباتی
بهمنظور ارزیابی عملکرد الگوریتمهای حل پیشنهاد شده در این تحقیق ۳۰ مسئله آزمایشی در سه مقیاس کوچک شامل ۱۶ مسئله، متوسط شامل ۸ مسئله و بزرگ شامل ۶ مسئله تولید و نتایج حاصل از حل مسائل توسط الگوریتمها در قالب جداولی در ادامه فصل آورده شده است. بهمنظور ارزیابی عملکرد الگوریتمها و کیفیت جوابهای تولید شده توسط آنها نسبت به جوابهای بهینه سراسری، هر ۱۶مسئله در ابعاد کوچک با هدف بدست آوردن جوابهای بهینه سراسری بوسیله نرمافزار لینگو ۹ (Lingo 9)در حالت Global Solver حل شدند. لازم به ذکر است که در حداقل ۳ مورد از مثالهای تولید شده در ابعاد کوچک، نرمافزار لینگو۹ حتی پس از گذشت ۱۰ ساعت از شروع حل نیز نتوانست به جواب بهینه سراسری دست پیدا کند. در گام بعد، تمام ۱۶مسئله توسط هر کدام از الگوریتمها به تعداد ۱۰ مرتبه اجرا و نتایج بدست آمده از حل هر مثال توسط هر الگوریتم شامل بدترین جواب تولید شده، میانگین جوابها و بهترین جواب بدست آمده بههمراه میانگین زمان محاسباتی آنها در قالب جداولی ارائه میشوند. الگوریتمهای حل در محیط برنامه نویسی Matlab R2010a کدنویسی شده و مجموعه مسائل معیار بر روی یک رایانه شخصی با مشخصات Intel Pentium IV (2.4 GHz) و حافظه ۲ گیگابایت اجرا شدهاند.
همانطور که در بخش معرفی مدل بیان شد، بهمنظور لحاظ کردن محدودیت دسترسی به ماشینها در مدل پیشنهادی از یک محدودیت غیرخطی استفاده گردید که در ادامه ذکر شد میتوان با استفاده از تکنیکهای خطیسازی، این محدودیت را بصورت محدودیت خطی تبدیل کرد. با این تبدیل، هرچند تعداد محدودیتهای تولید شده در روش حل بوسیله نرمافزار لینگو افزایش مییابد اما تعداد محدودیتهای غیر خطی آن نیز بشدت کاهش مییابد. بهعنوان مثال تعداد محدودیتهای تولید شده در مسئله ای با ۴ کار اصلی و ۲ پردازش روی ۲ ماشین (۲,۴,۲) در حالت وجود محدودیت غیرخطی دسترسی محدود به ماشینها برابر با ۲۷۷۹محدودیت بوده که از مجموع آنها به تعداد ۹۸۴ محدودیت غیرخطی است در حالیکه این نسبت با در نظرگرفتن محدودیت خطی دسترسی محدود به ماشینها برابر با ۲۹۹۹ محدودیت و ۴۳۲ محدودیت غیرخطی است. از این رو، در حل مسائل با ابعاد کوچک توسط مدل پیشنهادی، از هر دو محدودیت بصورت جداگانه استفاده و تحت عناوین EX1 و EX2 از آنها یاد میشود. بعبارت بهتر، از مدل با محدودیت غیر خطی دسترسی به ماشینها با عنوان EX1 و از مدل با محدودیت خطی دسترسی به ماشینها با عنوان EX2 یاد میشود.
جدول۴-۳۱٫ نتایج محاسباتی حاصل از حل مسائل با ابعاد کوچک

Size Exact Solution Worst Average Best
m,n,L EX1 EX2 GA BA1 BA2 GA BA1 BA2 GA BA1 BA2
۲,۲,۲ ۴۹٫۵۹۲ ۴۹٫۵۹۲ ۴۹٫۵۹۲ ۴۹٫۵۹۲ ۴۹٫۵۹۲ ۴۹٫۵۹۲ ۴۹٫۵۹۲ ۴۹٫۵۹۲ ۴۹٫۵۹۲