ارائه یک روش کارا برای زمانبندی وظایف وابسته در سیستم های محاسباتی ناهمگن با استفاده از روش جستجوی تبو

یک سیستم محاسباتی ناهمگن شامل تعدادی ماشین های محاسباتی با توانایی های متمایز است که از طریق یک شبکه ارتباطی سریع به هم متصل شده اند تا برنامه های موازی را اجرا کنند. با اینوجود، کارایی اجرای برنامه های موازی روی چنین سیستمهایی شدیداً به نحوه زمانبندی وظایف برنامه موازی روی ماشین های موجود در این سیستمها وابسته است. هدف اصلی از مسأله زمانبندی وظایف وابسته در سیستمهای موازی، اجرای وظایف یک برنامه موازی روی ماشینهای مختلف است بطوریکه کمترین زمان اتمام کلی برنامه به دست آید. اثبات شده است که مسأله زمانبندی وظایف از نوع مسائل NP-Complete بوده و پیدا کردن جواب بهینه برای مسائل بزرگ و حتی متوسط غیر ممکن است. روشهای مختلفی برای پیدا کردن جواب نزدیک به بهینه ارائه شدهاند. در این مقاله ما مسئله زمانبندی را مورد مطالعه قرار دادهایم و الگوریتمی را با استفاده از روش جستجوی تبو برای زمانبندی وظایف وابسته در محیطهای محاسباتی ناهمگن پیشنهاد و آن را با چهار تا از بهترینالگوریتمهای موجود مقایسه کردهایم که نتایج شبیه سازیهای انجام شده نشان میدهد، الگوریتم پیشنهادی در محیطهایی با ناهمگنی بالا نسبت به بهترین الگوریتمهای موجود عملکرد بهتری دارند.

Keywords:

سیستم محاسباتی ناهمگن , زمانبندی وظا یف , متاهیوریستیک , جستجوی تبو