سال انتشار: ۱۳۸۵

محل انتشار: چهاردهمین کنفرانس مهندسی برق ایران

تعداد صفحات: ۷

نویسنده(ها):

حسین میار نعیمی – دانشکده فنی و مهندسی، دانشگاه مازندران بابل خیابان دانشکده، دانشکد
مجید نادری – دانشکده مهندسی برق، دانشگاه علم و صنعت ایران

چکیده:

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