طرح الگوریتم اجتماع مورچگان برای حل مساله زمانبندی برنامه های موازی با مدلگرافهای جهت دار روی سیستمهای پردازش موازی

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

کلیدواژه ها:

زمانبندی سیستمهای پردازش موازی ، الگوریتم اجتماع مورچگان ، گرافهای جهت دار ، مسئله دستفروش دوره گرد