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

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

کلیدواژه ها:

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