والدین گره انتخاب می کند. این الگوریتم می خواهد در واقع به گره هایی که در مسیر بحرانی قرار گرفته اند زودتر منابع تخصیص دهد و با این کار زمان اتمام کلی جریان کار را کاهش دهد. در این الگوریتم از بین کارهای موجود در صف آماده کاری که دارای بالاترین رتبه باشد را انتخاب و به منبع با کمترین زمان اتمام ارسال می نماید. این الگوریتم نیز معایب الگوریتم HLEFT را دارد (بدلیل استفاده از نحوه رتبه بندی الگوریتم HLEFT). با این وجود نسبت به الگوریتم HLEFT دارای زمان اتمام آخرین کار بهتری می باشد.
2-9-9 الگوریتم PETS27 ]27[:
این الگوریتم دارای 7 مرحله می باشد.
گره شروع در گروه اول
تولید گروه جدید
قرار داده کلیه فرزندان گروه قبل در گروه جدید
رفتن به مرحله دوم درصورت وجود گره بدون گروه
تولید رتبه برای هر کار براساس فرمول (2)
(2) رتبه = میانگین زمان اجرایی + بالاترین رتبه میان والدین + مجموع هزینه انتقال داده به فرزندان
مرتب سازی کارهای موجود در هر گروه بصورت نزولی براساس رتبه
نگاشت کلیه کارها به ترتیب از گروه اول براساس رتبه تا گروه آخر به منبعی که کمترین زمان اتمام را داشته باشد
در واقع با اعمال گروه بندی سعی در موازی سازی اجرای کارهایی که بین آنها وابستگی وجود ندارد می باشد این الگوریتم در اکثر مواقع دارای توازن بار می باشد و از معایب آن می توان عدم توجه به مسیر بحرانی نام برد که باعث تولید زمان اتمام اخرین کار، کارایی و سرعت نامطلوب می شود.
2-9-10 الگوریتم HLEFT با نگاه به جلو ]28[:
این الگوریتم از نحوه رتبه دهی الگوریتم HLEFT استفاده کرده است. در هر مرحله، منبعی را انتخاب می کند که برای فرزندان آن کار، کمترین زمان اتمام را تولید نماید. در واقع یکبار بصورت صوری کار مورد نظر و فرزندانش را بروی تک تک منابع زمانبندی می نماید و منبعی که کمترین زمان اتمام را برای کلیه فرزندان به همراه داشت انتخاب، و آن کار را بر روی منبع منتخبی ارسال می نماید. این الگوریتم دارای نتایج خوبی می باشد در همین مقاله نسخه دیگری نیز ارائه شده است که کار با بالاترین رتبه را انتخاب، و به منبعی تخصیص می دهد که علاوه بر فرزندان خود، برای بالاترین رتبه بعدی و فرزندان او نیز مناسب باشد. زمان اجرایی این نسخه نسبت به نسخه اول خود بیشتر می باشد اما نتایج بهتری را ایجاد می نماید. در این الگوریتم بدلیل نگاه به جلو دارای زمان اتمام آخرین کار، کارایی و سرعت مناسب می باشد.
2-9-11 الگوریتم FTBAR ]29[:
این الگوریتم در هر مرحله از بین کارهایی که در صف آماده قرار گرفته است کاری را انتخاب میکند که دارای بالاترین رتبه باشد. والدین کارهای موجود در صف آماده در زمانی که اجرایشان تمام می شود، داده تولید شده خود را باید برای فرزندان خود ارسال نمایند و این هزینه ارسال به زمان اتمام خود اضافه می گردد در این الگوریتم این هزینه اتمام بعلاوه هزینه انتقال داده تولیدی را در نظر می گیرد و از والدین خود بالاترین هزینه در دسترس قرار گرفتن داده تولیدی را با رتبه حاصل توسط الگوریتم HLEFT جمع می کند و کاری که دارای بالاترین رتبه باشد را، از بین کارهای موجود در صف آماده انتخاب و به منبعی که دارای کمترین زمان اتمام باشد ارسال می نماید. در این الگوریتم بدلیل در نظر نگرفتن تعداد فرزندان در رتبه دارای زمان اتمام آخرین کار، کارایی و سرعت مناسبی نمی باشد. اما نسبت به مابقی الگوریتم ها دارای نتایج بهتری می باشد.
2-9-12 الگوریتم TSB28 ]30[ :
در این الگوریتم از دو صف استفاده کرده است یک صف برای کارهایی که آمادگی اجرا را دارند و در آن ترتیب جهت اجرا و انتخاب منابع مشخص شده است (RTQ29) و صف دیگری که در آن فرزندان کارهای موجود در صف RTQ قرار گرفته است این صف بنام NRTQ30 می باشد در ابتدای کار صف RTQ خالی و گره شروع در صف NRTQ قرار می گیرد تا زمانی که صف NRTQ خالی نشده است الگوریتم ادامه دارد در هر مرحله گره سر صف NRTQ برداشته می شود و اگر قادر به اجرا باشد (والدین گره تماما در صف RTQ قرار داشته باشد) این گره از صف NRTQ حذف و به آخر صف RTQ اضافه می گردد و تمام فرزندان این گره به آخر صف NRTQ اضافه می گردند این مراحل تا جایی که تمام گرهها در صف RTQ قرار بگیرند ادامه می یابد بعد از این مرحله از ابتدای صف RTQ کارها را به منبعی اختصاص می دهیم که دارای کمترین زمان اتمام باشد و این کار ادامه می یابد تا تمام کارها به منابع نگاشت گردند. این الگوریتم نیز معایب الگوریتم HLEFT را دارد (بدلیل استفاده از نحوه رتبه بندی الگوریتم HLEFT). با این وجود نسبت به الگوریتم HLEFT دارای زمان اتمام آخرین کار بهینه تر می باشد.
2-10 جمع بندی
با توجه به مطالبی که در این فصل مورد بررسی قرار گرفت الگوریتم های HLEFT و HLEFT با نگاه به جلو به ترتیب جهت تولید رتبه کار و انتخاب منبع مناسب که در سالهای 2007 و 2010 ارائه شده است ایده گرفته شده است.
فصل سوم

دسته بندی : No category

دیدگاهتان را بنویسید