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

سیستم های توزیع شده مانند Grid- و Cloud Computing خدمات وب را در سراسر جهان به کاربران خود ارائه میدهند. یکی از مهم ترین نگرانی هایی که ارائه دهندگان این خدمات با آن مواجه هستند، رسیدگی به هزینه کل مالکیت (TCO) است. بخش بزرگی از TCO مربوط به مصرف برق به دلیل مدیریت ناکارآمد منابع است. ماژول زمان بندی کار به عنوان یک جزء کلیدی می تواند تاثیر زیادی بر زمان پاسخ کاربر و استفاده از منابع اساسی داشته باشد. چنین سیستم های توزیع ناهمگنی، پردازنده های مختلف را با سرعت و معماری های متفاوت بکار برده اند. همچنین، برنامه کاربری که معمولا به صورت گراف غیر چرخه ای جهت دار (DAG) ارائه می شود باید بر روی این نوع سیستم های پردازش موازی اجرا شود. از آنجایی که زمان بندی کار در چنین سیستم های پیچیدهای جزء مسائل NP-hardاست رویکردهای اکتشافی موجود، دیگر کارآمد نیستند. بنابراین، روند کار استفاده از رویکردهای فراابتکاری ترکیبی است. در این مقاله، ما یک الگوریتم زمان بندی کار مبتنی بر ژنتیک به هم ریخته فراابتکاری را ارایه دادهایم تا زمان کل اجرا و طول زمان برنامههای کاربر را به حداقل برسانیم. در این راستا، ما از روش های اکتشافی دیگری مانند سریعترین زمان پایان ناهمگن (HEFT) برای تولید جمعیت اولیه هوشمند با استفاده از یک عملگر ترکیبی جدید بهره می بریم که برای کاوش افراد امکان پذیر و امیدوارکننده در فضای جستجو، ثروت زیادی ایجاد می کند. ما همچنین سایر اپراتورهای ژنتیکی را به روش صحیح هدایت می کنیم تا راه حل نهایی نزدیک به بهینه را تولید کنیم. برای رسیدن به نتایج ملموس ما چندین سناریو را انجام داده ایم. الگوریتم پیشنهادی ما در مقایسه با سایر رویکردهای موجود مانند نسخه های HEFT و QGARAR از نظر میانگین طول زمان، عملکرد بهتری داشته است.

کلیدواژه ها:

زمانبندی وظایف ، محاسبات ابری ، گراف غیر چرخه ای جهت دار (DAG)