ارائه الگوریتم تکاملی جهت زمان بندی وظایف بلا درنگ برروی چندپردازنده ها

زمان بندی وظایف بلادرنگ بر روی سیستم های چندپردازنده یکی از مسائل مهم و پیچیده در حوزه محاسبات موازی و بی درنگ است که به دلیل ماهیت NP-hard خود، یافتن پاسخ بهینه برای آن در زمان معقول بسیار دشوار است. در این پژوهش، یک الگوریتم ژنتیک بهبود یافته با نام New_GARTTS ارائه شده است که هدف اصلی آن، کاهش مجموع دیرکرد وظایف همراه با حفظ مهلت های زمانی، با سرعت و کارایی بالاتر نسبت به الگوریتم های پیشین است. نوآوری های اصلی این الگوریتم شامل استفاده از پیمایش توپولوژیکی گراف وظایف جهت تولید جمعیت اولیه معتبر و سریع، طراحی عملگر ترکیب چندنقطه ای هوشمند جهت جلوگیری از تولید کروموزوم های نامعتبر بدون نیاز به بازبینی، و بکارگیری عملگر جهش هدفمند برای متعادل سازی بار پردازنده ها می باشد. همچنین یک استراتژی جایگزینی هدفمند برای حفظ تنوع جمعیت و جلوگیری از گیر افتادن در بهینه محلی به کار گرفته شده است.الگوریتم پیشنهادی بر روی بیش از ۶۰ گراف وظیفه عمومی تصادفی که توسط روش P_Method تولید شده اند، آزمایش و با دو الگوریتم مشهور RT_MGA و GA_Monnier مقایسه گردید. نتایج شبیه سازی ها نشان می دهد که New_GARTTS در سرعت کاهش مجموع دیرکرد عملکرد بهتری نسبت به هر دو الگوریتم مرجع داشته و در بسیاری از موارد توانسته است زمان بندی های با کیفیت تر و سریع تر ارائه کند. این نتایج بیانگر پتانسیل بالای روش پیشنهادی برای استفاده در محیط های عملیاتی با محدودیت های زمانی و منابع پردازشی محدود است.

کلیدواژه ها:

: زمان بندی وظایف بلادرنگ ، چندپردازنده ، الگوریتم ژنتیک ، کاهش دیرکرد ، بهینه سازی تکاملی ،