تحقیق - پایان نامه - مقاله و پروژه

پژ.هش علمی :استفاده از الگوریتم ژنتیک و منطق فازی برای بهینه سازی منابع بازار براساس شبکه بندی- قسمت ۷

۲-۳-۱۱ الگوریتم ۲-tier(الگوریتم ترکیبی):[۲]
زمانبندی taskها در گرید برای هزینه زمانی و بهینه سازی آن تحت QoS(Quality of Service) زیاد محدودیت ندارد.برای روشن شدن الگوریتم پیشنهادی به وضح،تعاریف زیر را درنظر می گیریم.
فرض کنیم t مربوط به taskهای مستقل برای زمانبندی بر روی ماشین µ باشد.یک الگوریتم برای LTS سعی می کند نگاشت های بهینه t بر روی ماشین µ را بدست آورد.
فرض کنیم{t1,t2,…, tt}مربوط به metatask هایی که شامل همه taskهای مستقل است و {m1,m2,…,mµ}مجموعه ماشین های بر روی µ باشد.
زمان اجرایی مورد انتظار برای هر task بر روی ماشین های متفاوت مشابه نمی باشد.که برای تعیین اولویت اجرایی یک ماتریس t×µبه نام ETC(Expected Time To Compute) در نظر گرفته می شود.زمان تکمیل زمان اجرایی Cti برای task مربوط به Ti بر روی ماشین mj که شامل t×µ زمان تکمیل برای ماتریس می باشد.
که در آن matj(k) زمان دستیابی به ماشین mj بعد از k،task می باشد که شرایط اولیه آن matj(0)=0 می باشد.
تعریف۱:صف taskها که با TQj مجموعه ای از task ها شامل taskهای تخصیص یافته به ماشین mj برای زمانبندی.
تعریف۲:ماشین با حداکثر زمان تکمیل که ماشین key نامیده می شود.مجموع صف task های پردازش یر روی ماشین key ماکزیمم.
برای اینکه زمان پردازش هر task که بر روی ماشین های متفاوت پردازش می شوند،تعیین شود باید معیار:
تعریف۳:صف taskها بر روی ماشین key به صورت صف key تعریف می شود.این واضح است که makespan به وسیله ماشین key یا صف task مربوط به key تعیین می شود.برای شرایط مرزی برای بهینه سازی می توان هزینه بهینه را برروی همان ماشین و همان صف task ارزیابی کرد.
U بر روی U1وU2 به صورت زیر تقسیم می شود:
۱-زمانبندی U1 و بروزرسانی ماتریس CTH با الگوریتم min-max
۲-زمانبندی U2 و بروزرسانی ماتریس CT با الگوریتم min-max
۳-یافتن TQkوmk
۴-قرار دادن U’=U-TQk و حذف mk از مجموعه ماشین ها
۵-انتخاب تصادفی مجموعه ای از جفت ها برای taskهای U’
۶-تولید عملگرهای جهش جدید
۷-ارزیابی راه حل جدید
۸-اگر راه حل جدید بهتر باشد راه حل را با قبلی جایگزین کن
۹-پایان
پیچیدگی زمانی افراز،تجزیه ماتریس CT به دو ماتریس و زمانبندی همه task ها بدون در نظر گرفتن بهینه سازی هزینه از مرتبه O(n3)است.اگر n عضو max{t,µ} باشد.پیچیدگی زمانی هزینه بهینه سازی از مرتبهO(N×n2) خواهد بود که در آن N تعداد کل تکرارهای الگوریتم و n عضوmax{t,µ} است،بنابراین پیچیدگی زمانی پیشنهاد شده الگوریتم از مرتبه max{O(n3),O(N×n2)} خواهد بود.که این مورد مشابه پیچیدگی زمانی الگوریتمmin-max می باشد که سریع ترین الگوریتم آگاهانه می باشد.
۲-۳-۹-۱مثال برای روش پیشنهادی:
برای روشن شدن کارآیی و کارآیی هزینه الگوریتم پیشنهاد شده در مقایسه با الگوریتم های min-max و الگوریتم QGMM،ماتریس ETC را با جدول هزینه ها در نظر می گیریم.[۲]

در پایین درج شده است

mop
Table 2.COST matrix Table 1.ETC matrix
h3 h2 h1 h3 h2 h1
× ۲٫۱