دانلود مقاله محدودیت زمانی و بهینه سازی

دانلود پایان نامه
  • نکته دیگری که قابل توجه است جلوگیری از واگراشدن شدن های ناگهانی می باشد.چرا که عمل انتخاب در هر حال به صورت یک تابع احتمال است و امکان دارد که حتی بهترین کروموزوم هم به نسل بعدی راه پیدا نکند بدین منظور در هر نسل می توان بهترین کروموزوم را به صورت دستی به نسل بعدی منتقل کرد.
    2-3-10شرط توقف
    یکی از راه های محدود کردن تعداد نسل ها می باشد که می توان مشخص کرد برنامه تا چند نسل پیش برود.راه دیگر گذاشتن محدودیت زمانی است و شاید بهترین راه چک کردن بهترین کروموزوم هر نسل باشد که در صورت تکرار شدن آن به میزان k دفعه عملیات خاتمه یابد.
    2-3-11 الگوریتم 2-tier(الگوریتم ترکیبی):[2]
    زمانبندی 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 می باشد.
    تعریف1:صف taskها که با TQj مجموعه ای از task ها شامل taskهای تخصیص یافته به ماشین mj برای زمانبندی.
    تعریف2:ماشین با حداکثر زمان تکمیل که ماشین key نامیده می شود.مجموع صف task های پردازش یر روی ماشین key ماکزیمم.
    برای اینکه زمان پردازش هر task که بر روی ماشین های متفاوت پردازش می شوند،تعیین شود باید معیار:
    تعریف3:صف taskها بر روی ماشین key به صورت صف key تعریف می شود.این واضح است که makespan به وسیله ماشین key یا صف task مربوط به key تعیین می شود.برای شرایط مرزی برای بهینه سازی می توان هزینه بهینه را برروی همان ماشین و همان صف task ارزیابی کرد.
    U بر روی U1وU2 به صورت زیر تقسیم می شود:
    1-زمانبندی U1 و بروزرسانی ماتریس CTH با الگوریتم min-max
    2-زمانبندی U2 و بروزرسانی ماتریس CT با الگوریتم min-max
    3-یافتن TQkوmk
    4-قرار دادن U’=U-TQk و حذف mk از مجموعه ماشین ها
    5-انتخاب تصادفی مجموعه ای از جفت ها برای taskهای U’
    6-تولید عملگرهای جهش جدید
    7-ارزیابی راه حل جدید
    8-اگر راه حل جدید بهتر باشد راه حل را با قبلی جایگزین کن
    9-پایان
    پیچیدگی زمانی افراز،تجزیه ماتریس CT به دو ماتریس و زمانبندی همه task ها بدون در نظر گرفتن بهینه سازی هزینه از مرتبه O(n3)است.اگر n عضو max{t,µ} باشد.پیچیدگی زمانی هزینه بهینه سازی از مرتبهO(N×n2) خواهد بود که در آن N تعداد کل تکرارهای الگوریتم و n عضوmax{t,µ} است،بنابراین پیچیدگی زمانی پیشنهاد شده الگوریتم از مرتبه max{O(n3),O(N×n2)} خواهد بود.که این مورد مشابه پیچیدگی زمانی الگوریتمmin-max می باشد که سریع ترین الگوریتم آگاهانه می باشد.
    2-3-9-1مثال برای روش پیشنهادی:
    برای روشن شدن کارآیی و کارآیی هزینه الگوریتم پیشنهاد شده در مقایسه با الگوریتم های min-max و الگوریتم QGMM،ماتریس ETC را با جدول هزینه ها در نظر می گیریم.[2]
    Table 2.COST matrix
    این نوشته در مقالات و پایان نامه ها ارسال شده است. افزودن پیوند یکتا به علاقه‌مندی‌ها.