انجمن کامپیوتر ایران

مسأله‎ي زمانبندي وظيفه‏هاي مستقل در گريدهای محاسباتي يک مسأله‎ي NP-Complete است. بنابراين، براي رسيدن به راه‏حل‎هاي نزديک به بهينه در اين مسأله از روش‏هاي ابتکاري استفاده مي‎شود. الگوريتم رقابت استعماري (ICA) يک روش‏ جديد بهينه‎سازي تکاملي مي‏باشد که تاکنون براي حل مسأله زمانبندي گريد بررسي نشده است. در اين مقاله، ما با ترکيب ICA و جستجوي محلي، الگوريتم جديدي‎ برای کاهش makespan همزمان با افزايش بهره‏وري منابع و توازن بار معرفي کرده‎ايم. براي ارزيابي ‎الگوريتم پيشنهادي، آن را بر روي نمونه‎هاي محک براون و سايرين بررسي کرديم؛ اين نمونه‏ها سخت‏ترين محک براي مسأله زمانبندي در حالت ايستا هستند. نتايج ارزيابي نشان داد که الگوريتم ترکيبي براي زمانبندي در مقايسه با الگوريتم‎هاي قطعي، الگوريتم ژنتيک و ICA خالص، کارايي بهتري از نظر معيار makespan داشته و نگاشت‎هاي بسيار متوازني را توليد مي‎کند. همچنين، سرعت همگرايي اين الگوريتم به جواب‏هاي بهينه، نسبت به الگوريتم‏هاي تکاملي بررسي شده، بيشتر است.