الگوریتم های تکاملی ژنتیک برای حل و بهبود مسیله زمانبندی

زمانبندی و نگاشت گراف وظیفه با محدودیت اولویت به پردازنده ها بعنوان یک مسیله سخت مهم در سیستم های محاسبات توزیع شده و موازی در نظر گرفته می شود. الگوریتم های ژنتیک متعددی جهت حل این مسیله توسعه یافته اند. ویژگی مشترک در اکثر آنها، استفاده از نمایش کروموزومی برای زمانبندی است. با اینحال، این الگوریتم ها یکپارچه هستند، زیرا برای پیمایش فضای راه حل کامل بدون در نظر گرفتن نحوه ی کاهش پیچیدگی فرایند بهینه سازی تلاش می کنند. در این مقاله، دو الگوریتم ژنتیک توسعه یافته و پیاده سازی شدند. الگوریتم های توسعه یافته ما، الگوریتم های ژنتیک با چند اصل هیوریستیک هستند که جهت بهبود کارایی اضافه شدند. با توجه به اولین الگوریتم ژنتیک توسعه یافته، دو تابع برازندگی یکی بعد از دیگری بکار گرفته شدند. اولین تابع برازندگی در رابطه با کمینه سازی کل زمان اجرا (طول زمانبندی) است و دومی در رابطه با تامین تعادل بار است. دومین الگوریتم ژنتیک توسعه یافته برمبنای تکنیک تکرار وظیفه جهت غلبه بر سربار ارتباطات است. الگوریتم های پیشنهادی ما با استفاده از الگوها پیاده سازی شده و ارزیابی شدند. با توجه به نتایج بدست آمده مشخص است که الگوریتم های ما همیشه بهتر از الگوریتم سابق عمل می کنند.

Keywords:

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