زمانبندب ایستای کارها در سامانه توزیع شده همگن با تاکید بر توازن کاری

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

Keywords:

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