حل مسئله زمانبندی گراف وظایف با استفاده از الگوریتم ژنتیک بهبود یافته در معماری چندپردازنده ای

زمانبندی بهینه وظایف یکی از چالشهای سیستم های چند پردازنده ای است که امروزه کابرد وسیعی در محاسبات موازیدارند. در این سیستم ها این مسئله یک امر حیاتی برای داشتن سریعترین زمان پاسخ و حداقل سازی زمان انتظار است. الگوریتمهای موجود همواره سعی در توزیع وظایف به پردازنده ها در جهت افزایش کارائی سیستم از دید گاه حداقل سازی زمان پاسخ وهزینه دارند. با این حال با توجه به اینکه الگوریتم های مبتنی بر روش های قطعی بواسطه NP-Hard بودن این مسئله معمولاً کارانبوده اند استفاده از رویکردهای پردازش تکاملی و به طور عمده الگوریتم ژنتیک برای حل این مسئله می تواند مؤثر واقع شود. در اینتحقیق از الگوریتم ژنتیک بهبود یافته برای زمانبندی گراف وظایف در معماری چند پردازنده ای استفاده شده است. از ویژگی هایاین الگوریتم عدم نیاز به محاسبات مربوط به تنظیم پارامترهای نرخ جهش و نرخ برش می باشد. نتایج حاصل از اجرای تکنیکپیشنهادی در آزمایش های متفاوت نشان از بهتر شدن زمان پاسخ و توازن بار مناسب روی پردازنده ها نسبت به روش های موجود ازجمله نسبت به مدل بر پایه الگوریتم ژنتیک بوده است.

Keywords:

زمانبندی گراف وظایف , معمابی چند پردازنده ای , پردازش تازیع شده , الرابیتم ژنتیک بهباد یافته