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

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

Keywords:

زمان بندی ربات های موازی , الگوریتم ژنتیک , میانگین تاخیر