مروری برالگوریتم های زمان بندی وظایف

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

Keywords:

محیط محاسباتی توزیع شده , زمان بندی وظایف , الگوریتم ژنتیک , الگوریتم کلونی مورچگان , الگوریتم خفاشها , الگوریتم لیگ قهرمانان , الگوریتم ازدحام ذرات