بهینه¬سازی مسئله زمانبندی فازی ماشین¬های موازی با استفاده از الگوریتم ژنتیک جزیره¬ای
بهینه¬سازی مسئله زمانبندی فازی ماشین¬های موازی با استفاده از الگوریتم ژنتیک جزیره¬ای
فاطمه اکبری1 تورج محمدپور2
1) کارشناسی ارشد مهندسی کامپیوتر- نرمافزار، واحد آیت الله آملی، دانشگاه آزاد اسلامی، آمل، ایران
2) استادیار، گروه مهندسی کامپیوتر، واحد آیت الله آملی، دانشگاه آزاد اسلامی، آمل، ایران-
کد IOI مقاله
:
AAHD-ABEEKG
محل انتشار :
کنفرانس ملی فناوری اطلاعات، نانوتکنولوژی، هوش مصنوعی و آینده پژوهی فناوری (itnaf.ir)
چکیده :
در حل مسائل زمان¬بندی ماشینهای موازی، فاکتورهایی نظیر زمان پردازش فعالیت¬ها و زمان موعد مقرر برای تحویل کارها، اغلب بهصورت مبهم برای تحلیل¬گر تعریف می¬شوند. در چنین شرایطی برخلاف روشهای کلاسیک، استفاده از پارامترهای فازی و اهداف چندگانه مبتنی بر علم فازی، لازم بهنظر رسیده که منجر به مساله زمان¬بندی فازی می¬شود. مساله زمان¬بندی ماشین¬های موازی یکی از سخت¬ترین مسائل بهینه¬سازی ترکیبی بوده که از رده مسائل Np-hard است. برای بهینه¬سازی این مسائل با توجه به غیر چندجمله¬ای بودن آن¬ها، میتوان از روشهای مبتنی بر الگوریتمهای تکاملی استفاده نمود. در این مقاله برای بهینه¬سازی مساله زمانبندی فازی ماشین¬های موازی، یک روش مبتنی بر الگوریتم ژنتیک جزیرهای ارائه میشود. روش پیشنهادی با در نظر گرفتن زمان پردازش فازی و زمان موعد مقرر فازی، سعی در بهینهسازی مساله زمان¬بندی فازی ماشین¬های موازی مینماید. با توجه به معیارهای شاخص توافق، زمان تکمیل فازی و زمان موعد مقرر فازی، مسائل زمان¬بندی فازی ماشین¬های موازی را می¬توان به¬صورت مسائلی با اهداف سه¬گانه فرمولبندی نمود، بطوریکه کمینهکردن ماکزیمم زمان تکمیل کارها، بیشینهکردن متوسط شاخص توافق و بیشینهکردن مینیمم شاخص توافق، اهداف سهگانه مساله را تشکیل می¬دهند. بعد از مشخص نمودن توابع عضویت برای اهداف فازی مساله زمانبندی، برای حل آن از الگوریتم بهینه¬سازی ژنتیک جزیره¬ای استفاده میشود. این استراتژی، توانایی تعادل بهتر بین تنوع و تشدید روند جستجو را دارد. الگوریتم پیشنهادی بر روی دو مجموعه داده 6×6 و دو مجموعه داده 10×10 مورد آزمایش قرار میگیرد. نتایج حاصل از شبیهسازی نشان میدهد که روش پیشنهادی توانسته است که به همگرایی یکنواختی دستیافته و در مقایسه با سایر الگوریتمها، بهتر عمل نماید.
کلمات کلیدی : الگوریتم ژنتیک جزیره¬ای بهینه¬سازی فازی زمان¬بندی فازی ماشین¬های موازی مهلت زمانی فازی