مصطفی ماهی - مربی، گروه مهندسی کامپیوتر و فناوری اطلاعات، دانشگاه پیام نور
پریسا امین نژاد - مهندسی کامپیوتر، دانشگاه آزاد اسلامی واحد بناب، دانشکده برق و کامپیو

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

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