سال انتشار: ۱۳۸۷

محل انتشار: دومین همایش ملی مهندسی برق، کامپیوتر و فناوری اطلاعات

تعداد صفحات: ۷

نویسنده(ها):

گوهر وحدتی – دانشجوی کارشناسی ارشد هوش مصنوعی دانشگاه آزاد اسلامی واحد مشهد
مریم حبیبی پور – دانشجوی کارشناسی ارشد هوش مصنوعی دانشگاه آزاد اسلامی واحد مشهد
سعید طوسی زاده – عضو هیات علمی و استادیار گروه برق دانشگاه آزاد اسلامی واحد مشهد
مهدی یعقوبی – عضو هیئت علمی و استادیار گروه کامپیوتر دانشگاه آزاد اسلامی واحد مشهد

چکیده:

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