— (722)

دانشکده‌ی مهندسی برق و کامپیوتر
پایان‌نامه كارشناسی ارشد در رشتهی
مهندسی کامپیوتر (نرم‌افزار)
ارائه یک الگوریتم زمانبندی کارا در شبکه محاسباتی گرید با هدف کاهش زمان اتمام کل و توازن بار
به کوشش:
مجید قندهاری پور
استاد راهنما:
دکتر غلامحسین دستغیبی فرد
دی ماه 1392

centercenter

به نام خدا
اظهارنامه
اینجانب مجید قندهاری پور (900320) دانشجوی رشته‌ی مهندسی کامپیوتر گرایش نرمافزار دانشکده‌ی مهندسی برق و کامپیوتر اظهار می‌کنم كه این پایان‌نامه حاصل پژوهش خودم بوده و هر جایی كه از منابع دیگران استفاده کرده‌ام، نشانی دقیق و مشخصات كامل آن را نوشته‌ام. همچنین اظهار می‌کنم كه تحقیق و موضوع پایان‌نامه تكراری نیست و تعهد می‌نمایم كه بدون مجوز دانشگاه دستاوردهای آن را منتشر ننموده و یا در اختیار غیر قرار ندهم. كلیه حقوق این اثر مطابق با آییننامه مالكیت فكری و معنوی متعلق به دانشگاه شیراز است.
نام و نام خانوادگی: مجید قندهاری پور
تاریخ و امضاء
22/10/1392

بهنام خدا
ارائه یک الگوریتم زمانبندی کارا در شبکه محاسباتی گرید با هدف کاهش زمان اتمام کل و توازن بار
به کوشش:
مجید قندهاری پور
پایاننامهی
ارائه شده به تحصیلات تکمیلی دانشگاه به عنوان بخشی
از فعالیتهای لازم برای اخذ درجه کارشناسی ارشد
در رشته
مهندسی کامپیوتر گرایش نرمافزار
دانشگاه شیراز
شیراز
جمهوری اسلامی ایران
ارزیابی کمیتهی پایاننامه، با درجهی: عالی دکتر غلامحسین دستغیبیفرد، استادیار بخش مهندسی و علوم کامپیوتر (استاد راهنما): ……………………………………
دکتر فرشاد خونجوش، استادیار بخش مهندسی و علوم کامپیوتر( استاد مشاور): ……………………………………………..
دکتر کورش زیارتی، دانشیار بخش مهندسی و علوم کامپیوتر(استاد مشاور): …………………………………………………….
دکتر مصطفی فخراحمد، استادیار بخش مهندسی و علوم کامپیوتر(داور متخصص داخلی): ………………………………….
دیماه 92
خدا را بسی شاکرم که از روی کرم، پدر و مادری فداکار نصبیم ساخته تا در سایه درخت پربار وجودشان بیاسایم و از ریشه آنها شاخ و برگ گیرم و از سایه وجودشان در راه کسب علم و دانش تلاش نمایم. والدینی که بودنشان تاج افتخاری است بر سرم و نامشان دلیلی است بر بودنم، چرا که این دو وجود، پس از پروردگار، مایه هستی ام بوده اند، دستم را گرفتند و راه رفتن را در این وادی زندگی پر از فراز و نشیب آموختند. آموزگارانی که برایم زندگی بودن و انسان بودن را معنا کردند.
تقدیم به وجود با ارزشتان

از استاد گرامی جناب آقای دکتر دستغیبی فرد، که در کمال سعه صدر، با حسن خلق و فروتنی، از هیچ کمکی در این عرصه بر من دریغ ننمودند و زحمت راهنمایی این رساله را بر عهده گرفتند؛ از اساتید صبور و دلسوز، آقایان دکتر زیارتی و دکتر خونجوش، که زحمت مشاوره این رساله را در حالی متقبل شدند که بدون مساعدت ایشان، این پروژه به نتیجه مطلوب نمی رسید و از استاد فرزانه، جناب آقای دکتر فخراحمد که زحمت داوری این رساله را متقبل شدند؛ کمال تشکر و قدردانی را دارم.
چکیده
ارائه یک الگوریتم زمانبندی کارا در شبکه محاسباتی گرید با هدف کاهش زمان اتمام کل و توازن بار
به کوشش
مجید قندهاری پور
شبکههای تورین محاسباتی (گرید) زمینه‌ای را فراهم آورده است که بتوان از منابع ناهمگن در نقاط مختلف جغرافیایی برای حل مسائل پیچیده علمی، مهندسی و تجارت استفاده کرد. عملیات زمانبندی نقش کلیدی در عملکرد گرید ایفا میکند. در این پایان نامه با استفاده از مزایای الگوریتم ژنتیک، پنج الگوریتم زمانبندی برای نگاشت بهینهای از کارهای دستهای روی ماشینها ارائه شده است که تمامی فضای جستجو مسأله زمانبندی را بررسی کرده و یک توازن بار روی همه ماشینها ایجاد نماید. نتایج پیادهسازی الگوریتمهای ارائه شده نشان دهنده متوسط کاهش 13.23 درصد در زمان اتمام آخرین کار نسبت به الگوریتم های پیشین است.

کلید واژه: گرید محاسباتی، زمانبندی، توازن بار.
فهرست مطالب
عنوان صفحه
1- مقدمه …………………………………………………………………………………………………… 1
1-1 مقدمه ……………………………………………………………………………………………………………. 1
1-2 هدف از اجرای پایاننامه ………………………………………………………………………………. 2
1-3 مراحل انجام پایاننامه ………………………………………………………………………………….. 2
1-4 ساختار پایاننامه …………………………………………………………………………………………… 3
2- ادبیات موضوعی ………………………………………………………………………………………. 4
2-1 مقدمه ……………………………………………………………………………………………………………. 4
2-2 ساختار الگوریتم ژنتیک ………………………………………………………………………………… 6
2-3 عملگرهای ژنتیکی …………………………………………………………………………………………. 7
2-4 روند کلی الگوریتم ژنتیک ……………………………………………………………………………… 8
2-5 شرط پایان الگوریتم ………………………………………………………………………………………. 10
2-6 برخی از کاربردهای الگوریتم ژنتیک ……………………………………………………………… 10
2-7 تعاریف ……………………………………………………………………………………………………………… 11
2-8 مزایای اجرای موازی ……………………………………………………………………………………….. 12
2-9 مراحل زمانبندی در گرید …………………………………………………………………………….. 16
2-10 انواع زمانبند ………………………………………………………………………………………………….. 17
2-11 انواع زمانبندی ……………………………………………………………………………………………… 18
2-12 نحوهی زمانبندی (ایستا و پویا) …………………………………………………………………… 19
2-13 ساختار زمانبند …………………………………………………………………………………………….. 19
2-14 انواع صفبندی کارها ……………………………………………………………………………………. 21
2-15 پیچیدگی محاسباتی زمانبندی …………………………………………………………………….22
2-16 جمع بندی ………………………………………………………………………………………………… 22
3- پیشینه پژوهشی …………………………………………………………………………………….. 23
3-1 مقدمه ……………………………………………………………………………………………………………. 23
3-2 الگوریتمهای حریصانه ………………………………………………………………………………….. 23
3-3 الگوریتمهای تکاملی …………………………………………………………………………………….. 26
3-3-1 راهکارهای مبتنی بر جستجوی محلی ………………………………………… 26
3-3-2 راهکارهای جمعیت محور ……………………………………………………………. 28
3-4 جمعبندی …………………………………………………………………………………………………… 31
4- الگوریتمهای پیشنهادی ………………………………………………………………………….. 33
4-1 مقدمه ……………………………………………………………………………………………………………. 33
4-2 فرضیات وتعاریف …………………………………………………………………………………………… 34
4-3 الگوریتم Asuffrage …………………………………………………………………………………….. 35
4-4 الگوریتم MaxSuffrage ……………………………………………………………………………….. 36
4-5 الگوریتم توازن نسخه یک …………………………………………………………………………….. 38
4-6 الگوریتم توازن نسخه دو ………………………………………………………………………………. 40
4-7 الگوریتم ژنتیک و توازن بار ………………………………………………………………………….. 41
4-8 جمعبندی ……………………………………………………………………………………………………… 46
5- نتایج حاصل از ارزیابی………………………………………………………………………………. 47
5-1 مقدمه ……………………………………………………………………………………………………………. 47
5-2 محک ارزیابی براون ……………………………………………………………………………………… 47
5-3 ارزیابی الگوریتم Asuffrage ………………………………………………………………………… 49
5-4 ارزیابی الگوریتم MaxSuffrage …………………………………………………………………… 51
5-5 ارزیابی الگوریتم توازن نسخه یک …………………………………………………………………. 53
5-6 ازریابی الگوریتم توازن نسخه دو …………………………………………………………………… 54
5-7 ارزیابی الگوریتم ژنتیک به همراه توازن بار……………………………………………………. 55
5-8 پیشنهادات برای آینده …………………………………………………………………………………. 57
6- منابع ……………………………………………………………………………………………………… 58

فهرست جداول
عنوان صفحه
جدول 5-1 حالات ماتریس ETC …………………………………………………………………………………………. 49
جدول 5-2 نتایج makespan الگوریتم Asuffrage ……………………………………………………………. 50
جدول 5-3 نتایج resource utilization الگوریتم Asuffrage ……………………………………….. 51
جدول 5-4 نتایج makespan الگوریتم MaxSuffrage ……………………………………………………… 52
جدول 5-5 نتایج resource utilization الگوریتم MaxSuffrage ………………………………….. 53
جدول 5-6 نتایج makespan الگوریتم توازن نسخه یک …………………………………………………….. 54
جدول 5-7 نتایج makespan الگوریتم توازن نسخه دو ……………………………………………………….. 55
جدول 5-8 نتایج makespan الگوریتم ژنتیک به همراه توازن بار ………………………………………. 56
جدول 5-9 نتایج resource utilization الگوریتم ژنتیک به همراه توازن بار ……………………… 57

فهرست شکلها
عنوان صفحه
شکل 2-1 کروموزوم قبل و بعد از اعمال عملگر جهش ……………………………………………………….. 8
شکل 2-2 نمودار گردشی الگوریتم زنتیک …………………………………………………………………………… 9
شکل 2-3 ماتریس تخمین زمان اجرا (ETC) ……………………………………………………………………… 12
شکل 2-4 مجازیسازی منابع ناهمگن توسط گرید …………………………………………………………….. 13
شکل 2-5 مهاجرت کارها برای ایجاد توازن بار ……………………………………………………………………. 14
شکل 2-6 تنظیمات تکرار گرید …………………………………………………………………………………………… 15
شکل 2-7 تنظیم سیاست تخصیص کارها به منابع توسط مدیر …………………………………………. 16
شکل 2-8 ساختار زمانبند متمرکز ……………………………………………………………………………………….. 19
شکل 2-9 ساختار زمانبند سلسله مراتبی …………………………………………………………………………….. 20
شکل 2-10 ساختار زمانبند غیر متمرکز ……………………………………………………………………………… 20
شکل 4-1 الگوریتم توازن نسخه دوم ……………………………………………………………………………………. 41

مقدمه
1-1 مقدمه
کامپیوترهای امروزی مانند مغز انسان معمولا از بخش کوچکی از توانایی‌های خود استفاده می‌کنند و اغلب به‌ صورت غیرفعالند و منتظر اطلاعات ورودی می‌مانند. تصور کنید که اگر از منابع سخت‌افزاری این همه کامپیوتر غیرفعال استفاده شود و همه در یک کامپیوتر جمع شوند، چه دستگاه پرقدرتی خواهیم داشت. شبکههای محاسباتی (گرید) زمینه‌ای را فراهم آورده است که بتوان از منابع (کامپیوتری) سیستم‌های دیگر نیز استفاده نماییم. اغلب مسائل پیچیده علمی، مهندسی و تجارت احتیاج به میزان زیادی از منابع برای اجرا دارند، بهترین راه حل برای اینگونه مسائل استفاده از گرید میباشد[1].
هدف شبکههای محاسباتی (گرید) به اشتراک گذاشتن منابع کامپیوتری در نقاط مختلف جغرافیایی با مدیریتهای مختلف بین کاربران است. کاربران درخواستهای خود را پیوسته برای محیط گرید ارسال میکنند و بخش مدیریت منابع این کارها را به گره های محاسباتی موجود در شبکه اختصاص میدهد. به چگونگی تخصیص این درخواستها روی گرههای محاسباتی مختلف زمانبندی میگویند.
اعمال سیاستهای مختلف برای عملیات زمانبندی نتایج متفاوتی را خواهد داشت که این سیاست با توجه به اهداف مشخص شده برای گرید اتخاذ میشوند. عملیات زمانبندی در سیاستهای مختلف از فاکتورهای متفاوتی برای تخصیص کارها روی منابع مختلف استفاده میکند. امکان دارد یک فاکتور نقش تعیین کنندهای در یکی از سیاستها داشته باشد ولی در سیاست دیگر اصلا به آن توجه نشود، از اینرو هدف هر الگوریتم بهینه کردن سیاست مورد نظر خود است.
1-2 هدف از اجرای پایان نامه
با توجه به تاثیر بالای عملیات زمانبندی در عملکرد بهینه گرید و مزایایی که برای گرید در قسمت قبل ذکر شد، ارائه یک روش کارا در زمانبندی می تواند تاثیر زیادی در حل مسائل بزرگ در شاخه های مختلف داشته باشد.
در گریدهای محاسباتی هدف بالا بردن درصد استفاده از منابع در کنار کاهش زمان اتمام آخرین کار میباشد. در این طرح تحقیق همین اهداف را دنبال میکنیم و سعی داریم نگاشتی از کارها را ارائه دهیم که هم باعث بالا رفتن بهرهوری از منابع شود و هم کمترین زمان را برای اتمام آخرین کار داشته باشد.
1-3 مراحل انجام پایان نامه
برای انجام پایاننامه ابتدا مفاهیم گرید و روشهای موجود مطالعه و بررسی شدند و بعد از مقایسه صورت گرفته روی روشهای مختلف، الگوریتم ژنتیک برای تولید نگاشت انتخاب شد. در کنار الگوریتم ژنتیک الگوریتمی را ارائه کردیم که به توازن بار روی منابع کمک میکند و با استفاده از مزایای دو الگوریتم نام برده شده نگاشت بهینهای را برای کارها بدست آوردیم. برای پیادهسازی الگوریتمها از زبان برنامه نویسی java شده است.
1-4 ساختار پایان نامه
در فصل دوم الگوریتم ژنتیک، پارامترهای موثر در این الگوریتم و مفاهیم اولیهی زمانبندی مورد بررسی قرار میگیرد. در فصل سوم گذری بر تحقیقات پیشین خواهیم داشت. الگوریتمهای پیشنهادی در فصل چهارم ارائه شده است و در فصل پنجم نتایج حاصل از ارزیابی و مقایسه الگوریتمهای پیشنهادی آورده شده است.

ادبیات موضوعی
2-1 مقدمه
در این فصل ابتدا الگوریتم ژنتیک را مورد بررسی قرار میدهیم. در این بررسی ساختار کلی الگوریتم ژنتیک و پارامترهای تاثیرگذار در عملکرد این الگوریتم را مشخص میکنیم. در ادامه محیط شبکههای محاسباتی گرید را شرح داده و به بررسی اصطلاحات و تعاریف موجود میپردازیم. روشهای مختلف زمانبندی را بیان کرده و انواع صفبندی کارها را مورد بررسی قرار میدهیم.
الگوريتم ژنتيك، الهامي از علم ژنتيك و نظرية تكامل داروين است و بر اساس بقاي برترين‏ها يا انتخاب طبيعي استوار است. يك كاربرد متداول الگوريتم ژنتيك، استفاده از آن بعنوان تابع بهينه‏كننده است. الگوريتم ژنتيك ابزار سودمندي دربازشناسي الگو، انتخاب ويژگي، درك تصوير و يادگيري ماشيني است[3-8]. در الگوريتم‏ ژنتيك، نحوه تكامل ژنتيكي موجودات زنده شبيه‏سازي مي‏شود.
اگرچه كارهايي توسط يك زيستشناس به نام Fraser در زمينه مدلسازي تكامل در سيستم‌هاي بيولوژيك در دهه 60 ميلادي صورت گرفت ولي الگوريتم ژنتيك براي كاربردهاي مهندسي و به صورت امروزي آن، نخستين بار توسط جان هلند[9] متخصص علوم كامپيوتر دانشگاه ميشيگان در سال 1975 پيشنهاد گرديد. كار وي آغاز تمامي كوششها براي كاربرد الگوريتم ژنتيك در مهندسي است. پس از آن كارهاي Dejong [10]در سال 1975 در زمينه بررسي و مقايسه چندين روش الگوريتم ژنتيك پايه‌هاي نظري بحث را فراهم آورد. اين الگوريتم با الهام از طبيعت بر پايه اصل تكاملي «پايداري بهترين‌ها» استوار است. الگوريتم ژنتيك اگرچه پس از الگوريتم استراتژي تكاملي پيشنهاد گرديد ولي مشهورترين روش از بين الگوريتم‌هاي تكاملي است. در يك الگوريتم ژنتيك يك جمعيت از افراد طبق مطلوبيت آنها در محيط بقا مييابند. افرادي با قابليتهاي برتر، شانس ازدواج وتوليد مثل بيشتري را خواهند يافت. بنابراين بعد از چند نسل فرزنداني با كارايي بهتر بوجود مي‌آيند. در الگوريتم ژنتيك هر فرد از جمعيت بصورت يك كروموزوم معرفي مي‌شود. كروموزومها در طول چندين نسل كاملتر مي‌شوند. در هر نسل كروموزومها ارزيابي مي‌شوند و متناسب با ارزش خود امكان بقا و تكثير مي‌يابند. توليد نسل در بحث الگوريتم ژنتيك با عملگرهاي آمیزش3 و جهش4 صورت مي‏گيرد. والدين برتر بر اساس يك تابع برازندگي انتخاب مي‌شوند.
در هر مرحله از اجراي الگوريتم ژنتيك، يك دسته از نقاط فضاي جستجو مورد پردازش‏هاي تصادفي قرار مي‏گيرند. به اين صورت كه به هر نقطه دنباله‏اي از كاراكترها نسبت داده مي‏شود و بر روي اين دنباله‏ها، عملگرهاي ژنتيكي اعمال مي‏شوند. سپس دنباله‏هاي بدست آمده رمزگشایی مي‏گردد تا نقاط جديدي در فضاي جستجو بدست آيد. در آخر براساس اين كه تابع هدف در هر يك از نقاط چه مقدار باشد، احتمال شركت نمودن آنها در مرحله بعد تعيين مي‏گردد[11-14].
الگوريتم‏ ژنتيك را مي‏توان يك روش بهينه‏سازي تصادفي جهت‏دار دانست كه به تدريج به سمت نقطه بهينه حركت مي‏كند. در مورد ويژگي‌هاي الگوريتم ژنتيك در مقايسه با ديگر روش‌هاي بهينه سازي مي‌توان گفت كه الگوريتمي است كه بدون داشتن هيچ گونه اطلاعي از مسئله و هيچ گونه محدوديتي بر نوع متغيرهاي آن براي هر گونه مسئله اي قابل اعمال است و داراي كارآيي اثبات شده‌اي در يافتن بهينه كلي مي‌باشد. توانايي اين روش در حل مسائل پيچيده بهينه‌سازي است كه روش‌هاي كلاسيك يا قابل اعمال نيستند و يا دريافتن بهينه كلي قابل اطمينان نيستند[15].
2-2 ساختار الگوريتم‏ ژنتيك
به طور كلی، الگوريتم‏ ژنتيك از اجزاء زير تشكيل مي‏شود:
كروموزوم
در الگوريتم‏ ژنتيك، هر كروموزوم نشان دهنده يك نقطه در فضاي جستجو و يك راه‏حل ممكن براي مسئله مورد نظر است. خود كروموزوم‏ها (راه حل‏ها) از تعداد ثابتي ژن (متغير) تشكيل مي‏شوند. براي نمايش كروموزوم‏ها، معمولاً از كدگذاري‏هاي دودويي (رشته‏هاي بيتي) استفاده مي‏شود.
جمعيت
مجموعه‏اي از كروموزوم‏ها يك جمعيت را تشكيل مي‏دهند. با تاثير عملگرهاي ژنتيكي بر روي هر جمعيت، جمعيت جديدي با همان تعداد كروموزوم تشكيل مي‏شود.
تابع برازندگي
به منظور حل هر مسئله با استفاده از الگوريتم‏هاي ژنتيكي، ابتدا بايد يك تابع برازندگي براي آن مسئله ابداع شود. براي هر كروموزوم، اين تابع عددي غير منفي را برمي‏گرداند كه نشان دهنده شايستگي يا توانايي فردي آن كروموزوم است.
عملگرهاي ژنتيكي
در الگوريتم‏ ژنتيك، در طي مرحله توليد مثل ازعملگرهاي ژنتيكي استفاده مي‏شود. با تاثير اين عملگرها بر روي يك جمعيت، نسل بعدي آن جمعيت توليد مي‏شود. عملگرهاي انتخاب , آميزش و جهش معمولاً بيشترين كاربرد را در الگوريتم‏هاي ژنتيكي دارند.
2-3 عملگرهاي ژنتيكي
در بخش قبلي اشاره شد كه در الگوريتم‏ ژنتيك به منظور توليد مثل، معمولاً از عملگرهاي انتخاب، آميزش و جهش استفاده مي‏شود. در اين بخش، هر يك از عملگرهاي فوق به صورت جداگانه معرفي مي‏شود:
عملگر انتخاب
اين عملگر از بين كروموزوم‏هاي موجود در يك جمعيت، تعدادي كروموزوم را براي توليد مثل انتخاب مي‏كند. كروموزوم‏هاي برازنده‏تر، شانس بيشتري دارند تا براي توليد مثل انتخاب شوند.
عملگر آميزش
عملگر آميزش بر روي يك زوج كروموزوم از نسل مولد عمل كرده و يك زوج كروموزوم جديد توليد مي‏كند. عملگرهاي آميزش متعددي از قبيل، آميزش تك نقطه‏اي، آميزش دو نقطه‏اي، آمیزش چرخشی و … وجود دارند که در ادامه چند مورد را بررسی میکنیم.
عملگر جهش
پس از اتمام عمل آميزش، عملگر جهش بر روي كروموزوم‏ها اثر داده مي‏شود. اين عملگر يك ژن از يك كروموزوم را به طور تصادفي انتخاب نموده و سپس محتواي آن ژن را تغيير مي‏دهد. اگر ژن از جنس اعداد دودويي باشد، آن را به وارونش تبديل مي‏كند و چنانچه متعلق به يك مجموعه باشد، مقدار يا عنصر ديگري از آن مجموعه را به جاي آن ژن قرار مي‏دهد. در شكل 2-3 چگونگي جهش يافتن پنجمين ژن يك كروموزوم نشان داده شده است.
1543021153

1543121153
شكل 2-1 كروموزوم قبل و بعد از اعمال عملگر جهش

احتمال انجام عمل جهش بر روي هر كروموزوم را نرخ جهش يا احتمال جهش مي‏گويند و با Pm نمايش مي‏دهند. معمولاً اين عدد را بسيار كوچك (مثلاً 001/0) در نظر مي‏گيرند.
پس از اتمام عمل جهش، كروموزوم‏هاي توليد شده به عنوان نسل جديد شناخته شده و براي دور بعد اجراي الگوريتم ارسال مي‏شوند.
2- 4 روند كلي الگوريتم‏ ژنتيك
در شكل 2-2 نمودار گردشي الگوريتم‏ ژنتيك نشان داده شده است.
قبل از اين كه يك الگوريتم ژنتيك بتواند اجرا شود، ابتدا بايد كدگذاري (يا نمايش) مناسبي براي مسئله مورد نظر پيدا شود. همچنين يك تابع برازندگي نيز بايد ابداع شود تا به هر راه‏ حل كدگذاري شده ارزشي را نسبت دهد.
شكل 2-2 نمودار گردشي الگوريتم‏ ژنتيك

توليد تصادفي جمعيت اوليه از كروموزوم‏ها (راه حل‏ها)
ارزيابي برازندگي
ضوابط خاتمه يافتن برآورده مي‏شوند؟
انتخاب كروموزوم‏هاي برازنده‏تر
انجام اعمال آميزش و جهش بر روي كروموزوم‏ها
نسل بعدي جمعيت
خير
جواب بهينه
بلي

شكل 2-2 نمودار گردشي الگوريتم‏ ژنتيك
در طي اجرا، والدين براي توليد مثل انتخاب مي‏شوند و با استفاده از عملگرهاي آميزش و جهش با هم تركيب مي‏شوند تا فرزندان جديدي توليد كنند. شکل 2-2 نمودار گردشی الگوریتم ژنتیک
اين فرآيند چندين بار تكرار مي‏شود تا نسل بعدي جمعيت توليد شود. سپس اين جمعيت بررسي مي‏شود و در صورتي كه ضوابط همگرايي برآورده شوند، فرآيند فوق خاتمه مي‏يابد.
2-5 شرط پايان الگوريتم
در الگوريتم‌هاي تكاملي غالباً اجراي برنامه براي تعداد نسل‌هاي از پيش تعيين شده‌اي صورت مي‌گيرد. اما شرط ديگري نيز براي پايان الگوريتم‌ ژنتيك توسط Grefenstette [16] ارائه شده است كه آن ميزان پراكندگي بيت‌ها درون جمعيت مي‌باشد. اين محك نشان دهنده ميزان همگرا شدن كد اعضاي جمعيت مي‌باشد. اگر كد يك عنصر داراي طول 1 بيت باشد و به صورت نشان داده شود و (كه تعداد اعضاي جمعيت است)، مقدار پراكندگي بيت جمعيت P، b(P) به صورت زير تعريف مي‌شود:

هر اندازه ميزان b بزرگتر باشد ميزان پراكندگي بيت‌ها درون جمعيت كمتر خواهد بود. در حالت ويژه اگر b(P)=1 باشد به اين معني است كه كد همه اعضاي جمعيت يكسان است. شرط پايان به صورت b(p)> تعريف مي‌شود كه معمولا99/0 95/0 مي‌باشد.
2-6 برخي از كاربردهای الگوريتم‏ ژنتيك
الگوريتم‏ ژنتيك در حل بسياري از مسائل علمي و مهندسي به كار گرفته شده‏ است. برخي از موارد كاربرد اين الگوريتم عبارتند از:
بهينه‏سازي، برنامه‏سازي خودكار، يادگيري ماشين، تكامل تدريجي و يادگيري، اكولوژي و سيستم‏هاي اجتماعي.
2-7 تعاریف
گرید: یک روش اشتراک منبع قابل انعطاف، امن و با مقیاس بالا بین مجموعهای از اشخاص، نهادها و منابع میباشد که به عنوان سازمانهای مجازی شناخته شدهاند. فناوری محاسبات شبکه های تورین (گرید) یک محیط ناهمگن از منابع را فراهم میکند که این منابع توسط یک شبکهی جهانی با سرعت بالا به هم وصل شدهاند[17].
گرید محاسباتی: هدف شبکه های محاسباتی (گرید) به اشتراک گذاشتن منابع کامپیوتری در نقاط مختلف جغرافیایی با مدیریت های مختلف بین کاربران است.
کار: یک فعالیت محاسباتی است که می‌تواند به منابع مختلفی نیاز داشته باشد و دارای محدودیتهایی باشد.
منبع: یک نهاد محاسباتی پایه می‌باشد که کارها بر اساس آن زمان‌بندی، تخصیص و پردازش می‌شوند. منابع میتوانند پردازنده، حافظه، نرمافزار و … باشند. پارامترهای مختلفی مانند سرعت پردازش، پهنای باند، هزینه و … به یک منبع اختصاص داده می‌شود. بعلاوه ممکن است منابع وابسته به دامنههای مدیریتی مختلف باشند که اشاره به سیاستهای مختلف برای دسترسی و استفاده از آنها میکند.
دلال منبع: یک نرم افزار گرید است که از میانافزارها و سرویسها استفاده می‌کند تا مدیریت منابع، زمانبندی کارها و کنترل را انجام دهد. دلال منبع بین تولید کننده و مصرف کننده قرار میگیرد ADDIN EN.CITE <EndNote><Cite><Author>Xhafa</Author><Year>2010</Year><RecNum>6</RecNum><DisplayText>[8]</DisplayText><record><rec-number>6</rec-number><foreign-keys><key app=”EN” db-id=”9dwzd2xdkd5ve9esetpp5axiw2f0pprwsfzp”>6</key></foreign-keys><ref-type name=”Journal Article”>17</ref-type><contributors><authors><author>Xhafa, Fatos</author><author>Abraham, Ajith</author></authors></contributors><titles><title>Computational models and heuristic methods for Grid scheduling problems</title><secondary-title>Future generation computer sys–s</secondary-title></titles><periodical><full-title>Future generation computer sys–s</full-title></periodical><pages>608-621</pages><volume>26</volume><number>4</number><dates><year>2010</year></dates><isbn>0167-739X</isbn><urls></urls></record></Cite></EndNote>[18].
سیستم مدیریت منابع : یک ابزار نرمافزاری است که مجموعهای از منابع را مدیریت می‌کند به طوری که کارایی سیستم را بهینه کند ADDIN EN.CITE <EndNote><Cite><Author>Rodero</Author><Year>2010</Year><RecNum>7</RecNum><DisplayText>[9]</DisplayText><record><rec-number>7</rec-number><foreign-keys><key app=”EN” db-id=”9dwzd2xdkd5ve9esetpp5axiw2f0pprwsfzp”>7</key></foreign-keys><ref-type name=”Journal Article”>17</ref-type><contributors><authors><author>Rodero, Ivan</author><author>Guim, Francesc</author><author>Corbalan, Julita</author><author>Fong, Liana</author><author>Sadjadi, S Masoud</author></authors></contributors><titles><title>Grid broker selection strategies using aggregated resource information</title><secondary-title>Future Generation Computer Sys–s</secondary-title></titles><periodical><full-title>Future generation computer sys–s</full-title></periodical><pages>72-86</pages><volume>26</volume><number>1</number><dates><year>2010</year></dates><isbn>0167-739X</isbn><urls></urls></record></Cite></EndNote>[19].
زمانبندی: زمانبندی، نگاشتی از کارها به منابع میباشد. یک مسالهی زمانبندی با مجموعهای از منابع، مجموعهای از کارها، ملاکی برای بهینه بودن، مشخصات محیط و محدودیتهای دیگر تعریف میشود.
سرویس اطلاعات گرید: یک نرم افزار است که اطلاعات مربوط نرم افزارها، سرویسها و سختافزارهایی که در محیط گرید شرکت کردهاند را نگهداری میکند. این نرم افزار میتواند به صورت تنها و یا توزیع شده پیادهسازی شود. به علاوه، خدماتی مثل انقیاد، کشف، مراجعه و محافظت دادهرا فراهم میکند[20].
ماتریس تخمین زمان اجرا (ETC) : ماتریسی است n در m که n تعداد کارها و m تعداد ماشینها میباشد. در این ماتریس تخمینی از زمان اجرای هر کار روی هر منبع وجود دارد. شکل 2-3 یک نمونه از ماتریس ETC را نشان میدهد.

شکل STYLEREF 1 \s ‏23 نمونهی ماتریس ETC2-8 مزایای اجرای موازی
در صورت استفاده از گرید به جای منابع تک و جداگانه میتوانیم به مزیتهایی که در زیر به آنها اشاره شده است دست پیدا کنیم:
استفادهی موثر و بهینه از منابع: با استفاده از این امکان گرید میتوان به جای استفاده از یک منبع پرکار برای پردازش کلیه کارها از چندین منبع با بار متعادل استفاده کرد. اما این عمل به دو پیش شرط نیاز دارد. اول اینکه کارها باید قابلیت اجرا از راه دور را داشته باشند، مثلا نباید به دادههای روی ماشین اصلی وابسته باشد و دوم اینکه ماشینهای دیگر باید ویژگیهای سخت افزاری و نرم افزاری مورد نیاز کار مورد نظر را داشته باشد.
قابلیت اجرای موازی کارها: یکی از کاربردهای گرید، انجام محاسبات سنگینی است که قابلیت موازیسازی را دارند. این مورد در علوم مختلفی از قبیل بیولوژی، مدلسازی اقتصادی، اکتشاف نفت، انیمیشنسازی و … کاربرد دارد. ویژگی مشترک این کاربردها اجرای برنامهها به صورت موازی در کامپیوترهای مختلف است.
سازمانهای مجازی: در محیط گرید میتوان محیطی را فراهم کرد که سازمانها و شرکتهای مختلف که دارای اهداف مختلفی هستند با یکدیگر همکاری کنند. البته سیستمهای توزیع شده هم تاکنون تا حدودی به این هدف نزدیک شده اند اما، محاسبات گرید با تعریف استانداردهایی، اشتراک گذاری منابع در محیطهای ناهمگن را نیز امکان پذیر کرده است (شکل2-4).

شکل STYLEREF 1 \s ‏24 مجازی سازی منابع ناهمگن توسط گرید ADDIN EN.CITE <EndNote><Cite><Author>Jacob</Author><Year>2005</Year><RecNum>26</RecNum><DisplayText>[2]</DisplayText><record><rec-number>26</rec-number><foreign-keys><key app=”EN” db-id=”9dwzd2xdkd5ve9esetpp5axiw2f0pprwsfzp”>26</key></foreign-keys><ref-type name=”Book”>6</ref-type><contributors><authors><author>Jacob, Bart</author><author>Brown, Michael</author><author>Fukui, Kentaro</author><author>Trivedi, Nihar</author></authors></contributors><titles><title>Introduction to grid computing</title></titles><dates><year>2005</year></dates><publisher>IBM, International Technical Support Organization</publisher><isbn>0738494003</isbn><urls></urls></record></Cite></EndNote>[2]
دسترسی به منابع بیشتر: گرید علاوه بر پردازنده و حافظه، دسترسی به منابع دیگر را نیز فراهم میکند. به عنوان مثال اگر کاربری نیاز به پهنای باند بیشتری برای استفاده از اینترنت داشته باشد میتواند با تبدیل کارها به ریزکارها و ایجاد اتصال جداگانه به ماشینهای دیگر، ریزکارها را بین آن ها تقسیم کند و از این کاربرد استفاده کند. هچنین گاهی نیاز به نرم افزارهای گران قیمتی است که نمیتوان آن را فراهم کرد، در این حالت گرید میتواند کار را بر روی ماشینی اجرا کند که نرم افزار مربوطه روی آن قرار دارد.
ایجاد تعادل در استفاده از منابع: گرید برای ایجاد یک سیستم یکپارچه منابعی را که در ماشینهای مختلف قرار گرفته اند را متحد میکند. این کار با استفاده از یک مکانیزم انجام میشود که در آن ریزکارها بر روی منابع به صورت متعادل توزیع می شوند. در شکل 2-5 این مکانیزم قابل مشاهده است که به دو روش زیر قابل انجام است:
کارها از منابع پرکار به منابع کم کار منتقل شوند.
در صورت مشغول بودن تمام منابع، کارهایی که اولویت پایینتری دارند میتوانند متوقف شوند. در این صورت فضا برای کارهایی با اولویت بالاتر ایجاد میشود.

شکل STYLEREF 1 \s ‏25 مهاجرت کارها برای ایجاد توازن بار ADDIN EN.CITE <EndNote><Cite><Author>Jacob</Author><Year>2005</Year><RecNum>26</RecNum><DisplayText>[2]</DisplayText><record><rec-number>26</rec-number><foreign-keys><key app=”EN” db-id=”9dwzd2xdkd5ve9esetpp5axiw2f0pprwsfzp”>26</key></foreign-keys><ref-type name=”Book”>6</ref-type><contributors><authors><author>Jacob, Bart</author><author>Brown, Michael</author><author>Fukui, Kentaro</author><author>Trivedi, Nihar</author></authors></contributors><titles><title>Introduction to grid computing</title></titles><dates><year>2005</year></dates><publisher>IBM, International Technical Support Organization</publisher><isbn>0738494003</isbn><urls></urls></record></Cite></EndNote>[2]
قابلیت اطمینان: با استفاده از این کاربرد در صورت بروز خطا و از کار افتادن سیستم، قابلیت بازیابی وجود دارد. برای ایجاد این امکان بایستی از منابع سخت افزاری بیشتری برای نگهداری نسخههای کپی استفاده شود. همچنین در بعضی از ماشینها که دارای چند پردازنده هستند با از کارافتادن یکی از پردازندهها بقیه پردازندهها میتوانند به کار خود ادامه دهند. یکی از روشهای دیگر این است که چند نسخه از یک کار میتواند در چند ماشین اجرا شود که در شکل 2-6 قابل مشاهده است.

شکل STYLEREF 1 \s ‏26 تنظیمات تکرار گرید ADDIN EN.CITE <EndNote><Cite><Author>Jacob</Author><Year>2005</Year><RecNum>26</RecNum><DisplayText>[2]</DisplayText><record><rec-number>26</rec-number><foreign-keys><key app=”EN” db-id=”9dwzd2xdkd5ve9esetpp5axiw2f0pprwsfzp”>26</key></foreign-keys><ref-type name=”Book”>6</ref-type><contributors><authors><author>Jacob, Bart</author><author>Brown, Michael</author><author>Fukui, Kentaro</author><author>Trivedi, Nihar</author></authors></contributors><titles><title>Introduction to grid computing</title></titles><dates><year>2005</year></dates><publisher>IBM, International Technical Support Organization</publisher><isbn>0738494003</isbn><urls></urls></record></Cite></EndNote>[2]
مدیریت: مجازی سازی منابع و ناهمگن بودن این سیستم بزرگ، موقعیت بهتری را برای مدیریت فراهم میکند. مجازی سازی منابع، مدیریت منابع را در سیستم بزرگ ساده تر میکند. مثلا مدیران میتوانند سیاستهای مختلفی را برای منابع مختلف تنظیم کنند (شکل 2-7).

شکل STYLEREF 1 \s ‏27 تنظیم سیاست تخصیص کارها به منابع توسط مدیر ADDIN EN.CITE <EndNote><Cite><Author>Jacob</Author><Year>2005</Year><RecNum>26</RecNum><DisplayText>[2]</DisplayText><record><rec-number>26</rec-number><foreign-keys><key app=”EN” db-id=”9dwzd2xdkd5ve9esetpp5axiw2f0pprwsfzp”>26</key></foreign-keys><ref-type name=”Book”>6</ref-type><contributors><authors><author>Jacob, Bart</author><author>Brown, Michael</author><author>Fukui, Kentaro</author><author>Trivedi, Nihar</author></authors></contributors><titles><title>Introduction to grid computing</title></titles><dates><year>2005</year></dates><publisher>IBM, International Technical Support Organization</publisher><isbn>0738494003</isbn><urls></urls></record></Cite></EndNote>[2]
2-9 مراحل زمانبندی در گرید
زمانبندی در گرید به 5 مرحله تقسیم میشود ADDIN EN.CITE <EndNote><Cite><Author>Xhafa</Author><Year>2010</Year><RecNum>6</RecNum><DisplayText>[8]</DisplayText><record><rec-number>6</rec-number><foreign-keys><key app=”EN” db-id=”9dwzd2xdkd5ve9esetpp5axiw2f0pprwsfzp”>6</key></foreign-keys><ref-type name=”Journal Article”>17</ref-type><contributors><authors><author>Xhafa, Fatos</author><author>Abraham, Ajith</author></authors></contributors><titles><title>Computational models and heuristic methods for Grid scheduling problems</title><secondary-title>Future generation computer sys–s</secondary-title></titles><periodical><full-title>Future generation computer sys–s</full-title></periodical><pages>608-621</pages><volume>26</volume><number>4</number><dates><year>2010</year></dates><isbn>0167-739X</isbn><urls></urls></record></Cite></EndNote>[18]:
آماده سازی و جمع آوری اطلاعات منابع و کارها.
انتخاب منابع مناسب.
محاسبهی تابع هدف برای هر کار بر روی منابع انتخاب شده.
انتساب کار بر اساس تابع هدف.
نظارت بر اتمام کارها.
در ادامه هر کدام از این مراحل را به طور مختصر شرح میدهیم.
آمادهسازی و جمع آوری اطلاعات منابع و کارها: در این مرحله زمانبند باید اطلاعات مربوط به کارها و ماشینهایی که در دسترس هستند را از سرویس اطلاعات گرید دریافت کند. بعلاوه به زمانبند در مورد اطلاعات بروز شدهی کارها و منابع اطلاع رسانی میشود.
انتخاب منابع مناسب: انتخاب منبع یکی از مراحل مهمی است که هر زمانبند باید انجام دهد. به دلیل اینکه تمام منابع نمیتوانند کاندید خوبی برای اجرای بعضی از کارها باشند. بنابراین، فرآیند انتخاب منابع از طریق نیازمندیهای کار و خصوصیات منابع انجام میشود. همچنین فرآیند انتخاب به حالت زمانبندی نیز بستگی دارد. مثلا، در حالتی که کارها به صورت دستهای هستند، تعداد زیادی از منابع کاندید ممکن، از بین تمام منابع در دسترس شناسایی میشوند و انتساب کارها به منابع به گونهای انجام میشود که به ملاک بهینهسازی مورد نظر برسیم. به عنوان قسمتی از انتخاب منابع، رزرو منابع را نیز میتوان در نظر گرفت. در این حالت به دست آوردن اطلاعات در مورد اجرای کارها در آینده بسیار سخت است. البته میتوان از صفهای وضعیت استفاده کرد، اما دقت خوبی نمیتوان انتظار داشت مخصوصا اگر اولویت یکی از نیازمندیهای کار باشد. پیشنهاد دیگر استفاده از روشهای پیشبینی بر اساس دادههای گذشته یا خصوصیات کاربران است.
محاسبهی تابع هدف برای هر کار بر روی منابع انتخاب شده: در این مرحله تابع هدف یا بهینهسازی برای هر کار و برای منابع انتخاب شده محاسبه میشود.
انتساب کار: کارها بر اساس تابع هدف به منابع انتخاب شده انتساب داده میشوند.
نظارت بر اتمام کارها: بعد از انتساب کار نظارت بر اجرای کارها لازم است تا در صورت عدم موفقیت اجرای یک کار، بر اساس سیاست زمانبندی، زمانبندی مجدد یا انتقال به منابع دیگر صورت پذیرد.
2-10 انواع زمانبند
تقسیم بندی زمانبندها به شرح زیر است ADDIN EN.CITE <EndNote><Cite><Author>Xhafa</Author><Year>2010</Year><RecNum>6</RecNum><DisplayText>[8]</DisplayText><record><rec-number>6</rec-number><foreign-keys><key app=”EN” db-id=”9dwzd2xdkd5ve9esetpp5axiw2f0pprwsfzp”>6</key></foreign-keys><ref-type name=”Journal Article”>17</ref-type><contributors><authors><author>Xhafa, Fatos</author><author>Abraham, Ajith</author></authors></contributors><titles><title>Computational models and heuristic methods for Grid scheduling problems</title><secondary-title>Future generation computer sys–s</secondary-title></titles><periodical><full-title>Future generation computer sys–s</full-title></periodical><pages>608-621</pages><volume>26</volume><number>4</number><dates><year>2010</year></dates><isbn>0167-739X</isbn><urls></urls></record></Cite></EndNote>[18]:
زمانبند گرید: یکی از اجزای نرمافزاری است که مسئولیت محاسبهی یک نگاشت از کارها به منابع گرید تحت ملاکهای مختلف و تنظیمات محیط گرید را دارد. سطوح مختلفی در درون زمانبند گرید در مقایسههای مختلف ادبیات محاسبات گرید در نظر گرفته شده است که شامل فرازمانبند و زمانبند محلی میباشد که در زیر شرح داده شده است. به عنوان یک جزء اصلی از گرید، زمانبند گرید با اجزاء دیگر گرید، از قبیل سیستم اطلاعات گرید، سیستم مدیریت منبع محلی و سیستم مدیریت شبکه در تعامل است. همچنین باید این نکته را در نظر گرفت که در محیط گرید، انواع زمانبندها باید در کنار یکدیگر همزیستی داشته باشند. حتی ممکن است که آنها دارای هدفهای مختلفی باشند، اما باید برای اجرای کارها با یکدیگر در تعامل باشند.
فرازمانبند: از این زمانبند در مواقعی که یک کار به بیش از یک منبع نیاز دارد استفاده می شود. در خوشهها فرازمانبند با هماهنگی با زمانبندهای محلی، منابع مورد نظر را انتخاب میکند. اعمال توازن بار در میان سیستمهای مختلف، هدف اصلی این زمانبند میباشد.
زمانبند محلی: این زمانبند برای انتساب کارها به یک منبع استفاده میشود و به عنوان یک زمانبند “نزدیک به منبع” شناخته میشود.
2-11 انواع زمانبندی
زمانبندی از لحاظ نوع کارها و ارتباط آنها به دو دسته مستقل و غیر مستقل تقسیم میشود ADDIN EN.CITE <EndNote><Cite><Author>Xhafa</Author><Year>2010</Year><RecNum>6</RecNum><DisplayText>[8]</DisplayText><record><rec-number>6</rec-number><foreign-keys><key app=”EN” db-id=”9dwzd2xdkd5ve9esetpp5axiw2f0pprwsfzp”>6</key></foreign-keys><ref-type name=”Journal Article”>17</ref-type><contributors><authors><author>Xhafa, Fatos</author><author>Abraham, Ajith</author></authors></contributors><titles><title>Computational models and heuristic methods for Grid scheduling problems</title><secondary-title>Future generation computer sys–s</secondary-title></titles><periodical><full-title>Future generation computer sys–s</full-title></periodical><pages>608-621</pages><volume>26</volume><number>4</number><dates><year>2010</year></dates><isbn>0167-739X</isbn><urls></urls></record></Cite></EndNote>[18]:
زمانبندی مستقل: در زمانبندی مستقل، کارهایی که باید روی منابع نگاشت داده شوند به یکدیگر وابسته نمیباشند و میتوانیم با هر ترتیب دلخواه کارها را زمانبندی نمائیم.
زمانبندی غیر مستقل (گردش کاری ): در زمانبندی غیر مستقل بین کارها وابستگی وجود دارد و نمیتوانیم با هر ترتیب داخواه کارها را به منابع واگذار نمائیم. به این صورت که مثلا اگر کار j به کار i وابسته باشد نمیتوانیم کارj را زودتر از کار i شروع نمائیم و باید ابتدا کار i را زمانبندی کرده و سپس کار jرا به منبعی نگاشت دهیم.
2-12 نحوهی زمانبندی (ایستا و پویا)
ایستا: در این حالت اطلاعات کامل منابع و کارها، هنگامی که زمانبندی انجام میشود در دسترس است (کارها به صورت دستهای میباشند). یکی از مزایای زمانبندی ایستا برنامهی ساده آن از دید زمانبندها میباشد.
پویا: در زمانبندی پویا تخصیص کارها به صورت برخط انجام میشود و در همان لحظه کار برای اجرا به یک منبع فرستاده میشود. این زمانبندی معمولا زمانی استفاده میشود که تخمین هزینه ی کارها سخت است و یا کارها به صورت برخط فرستاده میشوند ADDIN EN.CITE <EndNote><Cite><Author>ZHANG</Author><Year>2009</Year><RecNum>10</RecNum><DisplayText>[13]</DisplayText><record><rec-number>10</rec-number><foreign-keys><key app=”EN” db-id=”9dwzd2xdkd5ve9esetpp5axiw2f0pprwsfzp”>10</key></foreign-keys><ref-type name=”Journal Article”>17</ref-type><contributors><authors><author>ZHANG, Hai-bin</author><author>TANG, Lin-sha</author><author>LIU, Li-xiang</author></authors></contributors><titles><title>Survey of grid scheduling</title><secondary-title>Computer Engineering and Design</secondary-title></titles><periodical><full-title>Computer Engineering and Design</full-title></periodical><pages>026</pages><volume>9</volume><dates><year>2009</year></dates><urls></urls></record></Cite></EndNote>[23].
2-13 ساختار زمانبند
فرازمانبندها میتوانند متمرکز، سلسله مراتبی و یا توزیع شده باشند که به شرح زیر می باشند ADDIN EN.CITE <EndNote><Cite><Author>Subramani</Author><Year>2002</Year><RecNum>29</RecNum><DisplayText>[14]</DisplayText><record><rec-number>29</rec-number><foreign-keys><key app=”EN” db-id=”9dwzd2xdkd5ve9esetpp5axiw2f0pprwsfzp”>29</key></foreign-keys><ref-type name=”Conference Paper”>47</ref-type><contributors><authors><author>Subramani, Vijay</author><author>Kettimuthu, Rajkumar</author><author>Srinivasan, Srividya</author><author>Sadayappan, S</author></authors></contributors><titles><title>Distributed job scheduling on computational grids using multiple simultaneous requests</title><secondary-title> 11th IEEE International Symposium on High Performance Distributed Computing</secondary-title></titles><pages>359-366</pages><dates><year>2002</year></dates><pub-location>Edinburgh, Scotland</pub-location><publisher>IEEE</publisher><isbn>0769516866</isbn><urls></urls></record></Cite></EndNote>[24]:
متمرکز: در این مدل، فرازمانبند اطلاعات کامل تمام زمانبندهای محلی را در اختیار دارد و تمام کارها نیز به فرازمانبند ارسال میشوند (شکل 2-8). فرازمانبند، تصمیمات زمانبندی را بر اساس اطلاعات کارهای ارسال شده و اطلاعات زمانبندهای محلی میگیرد. ساختار متمرکز مقیاسپذیر نمیباشد.

شکل STYLEREF 1 \s ‏28 ساختار زمانبند متمرکز ADDIN EN.CITE <EndNote><Cite><Author>Subramani</Author><Year>2002</Year><RecNum>29</RecNum><DisplayText>[14]</DisplayText><record><rec-number>29</rec-number><foreign-keys><key app=”EN” db-id=”9dwzd2xdkd5ve9esetpp5axiw2f0pprwsfzp”>29</key></foreign-keys><ref-type name=”Conference Paper”>47</ref-type><contributors><authors><author>Subramani, Vijay</author><author>Kettimuthu, Rajkumar</author><author>Srinivasan, Srividya</author><author>Sadayappan, S</author></authors></contributors><titles><title>Distributed job scheduling on computational grids using multiple simultaneous requests</title><secondary-title> 11th IEEE International Symposium on High Performance Distributed Computing</secondary-title></titles><pages>359-366</pages><dates><year>2002</year></dates><pub-location>Edinburgh, Scotland</pub-location><publisher>IEEE</publisher><isbn>0769516866</isbn><urls></urls></record></Cite></EndNote>[24]
سلسله مراتبی: در این ساختار تمام کارها به فرازمانبند ارسال می شود سپس فرازمانبند، اطلاعات کارها را برای همهی زمانبندهای محلی ارسال میکند و هر زمانبند محلی با توجه به سیاست خود زمان اجرا را به فرازمانبند اعلام و فرازمانبند کار را به منبعی ارسال می کند که زمان اجرا یا انتظار کمتری دارد (شکل 2-9).

شکل STYLEREF 1 \s ‏29 ساختار زمانبند سلسله مراتبی ADDIN EN.CITE <EndNote><Cite><Author>Subramani</Author><Year>2002</Year><RecNum>29</RecNum><DisplayText>[14]</DisplayText><record><rec-number>29</rec-number><foreign-keys><key app=”EN” db-id=”9dwzd2xdkd5ve9esetpp5axiw2f0pprwsfzp”>29</key></foreign-keys><ref-type name=”Conference Paper”>47</ref-type><contributors><authors><author>Subramani, Vijay</author><author>Kettimuthu, Rajkumar</author><author>Srinivasan, Srividya</author><author>Sadayappan, S</author></authors></contributors><titles><title>Distributed job scheduling on computational grids using multiple simultaneous requests</title><secondary-title> 11th IEEE International Symposium on High Performance Distributed Computing</secondary-title></titles><pages>359-366</pages><dates><year>2002</year></dates><pub-location>Edinburgh, Scotland</pub-location><publisher>IEEE</publisher><isbn>0769516866</isbn><urls></urls></record></Cite></EndNote>[24]
توزیع شده: این ساختار شبیه ساختار سلسله مراتبی است با این تفاوت که در هر مکان یک فرازمانبند وجود دارد و کارها به نزدیکترین فرازمانبند ارسال میشود. فرازمانبندها در دورههای زمانی مختلف، اطلاعات بار کاری خود را با یکدیگر تبادل کرده و در صورت نیاز برای توازن بار، عمل تبادل کار را بین یکدیگر انجام میدهند. (شکل 2-10).

شکل210 ساختار زمانبند غیر متمرکز ADDIN EN.CITE <EndNote><Cite><Author>Subramani</Author><Year>2002</Year><RecNum>29</RecNum><DisplayText>[14]</DisplayText><record><rec-number>29</rec-number><foreign-keys><key app=”EN” db-id=”9dwzd2xdkd5ve9esetpp5axiw2f0pprwsfzp”>29</key></foreign-keys><ref-type name=”Conference Paper”>47</ref-type><contributors><authors><author>Subramani, Vijay</author><author>Kettimuthu, Rajkumar</author><author>Srinivasan, Srividya</author><author>Sadayappan, S</author></authors></contributors><titles><title>Distributed job scheduling on computational grids using multiple simultaneous requests</title><secondary-title> 11th IEEE International Symposium on High Performance Distributed Computing</secondary-title></titles><pages>359-366</pages><dates><year>2002</year></dates><pub-location>Edinburgh, Scotland</pub-location><publisher>IEEE</publisher><isbn>0769516866</isbn><urls></urls></record></Cite></EndNote>[24]
2-14 انواع صفبندی کارها
صف بندی کارها میتواند دستهای و یا برخط باشد که به شرح زیر میباشد ADDIN EN.CITE <EndNote><Cite><Author>Feitelson</Author><Year>1998</Year><RecNum>30</RecNum><DisplayText>[15]</DisplayText><record><rec-number>30</rec-number><foreign-keys><key app=”EN” db-id=”9dwzd2xdkd5ve9esetpp5axiw2f0pprwsfzp”>30</key></foreign-keys><ref-type name=”Conference Paper”>47</ref-type><contributors><authors><author>Feitelson, Dror G</author><author>Rudolph, Larry</author></authors></contributors><titles><title>Metrics and benchmarking for parallel job scheduling</title><secondary-title>Job Scheduling Strategies for Parallel Processing</secondary-title></titles><pages>1-24</pages><dates><year>1998</year></dates><pub-location>New York, NY</pub-location><publisher>Springer</publisher><isbn>3540648259</isbn><urls></urls></record></Cite></EndNote>[25]:
دستهای(برون خط): در این مدل، تمام کارها و نیازمندیهایی که دارند از همان ابتدا در دسترس است و بعد از شروع کار سیستم، هیچ کاری وارد نمیشود. در این مدل زمانبندی میتواند با در نظر گرفتن تمام کارها با هم، زمان پردازش کلی برای زمانبندی را به حداقل برساند. این مدل به این دلیل که دارای محیط پویا نمیباشد برای زمان بندیهایی که به صورت دستهای عمل میکنند مناسب است.
صفبندی کارها به صورت دستهای خصوصیاتی دارد که در ادامه به آنها اشاره میکنیم:
کارها نسبت به یکدیگر دارای نیازهای پردازشی متغیر و متنوعی میباشند.
کارها برای اجرا به یکدیگر وابسته نمیباشند و به صورت مستقل از هم اجرا میشوند.
کار قابل تجزیه به عناصر کوچکتر نیست.
منبعی که به هر کار واگذار میشود تا انتهای اجرای آن کار در اختیار کار مربوطه است و قابل واگذاری به کار دیگر در حین اجرا نیست.
تخمینی از زمان اجرای هر کار روی هر منبع قبل از زمانبندی وجود دارد.
برخط: در این مدل برعکس مدل قبلی کارها در هر بازهی زمانی میتوانند به سیستم وارد شوند و هیچ محدودیتی برای زمان ورود کارها وجود ندارد. در این مدل زمانبند باید این توانایی را داشته باشد که در هر زمانی کارهای جدیدی که وارد میشوند را مدیریت کند.
2-15 پیچیدگی محاسباتی عملیات زمانبندی
مسائل زمانبندی جزء مسائل NP-Hard میباشند[26]. با داشتن m منبع و n کار تعداد حالت مختلف از واگذاری کارها به منابع را می توانیم تولید نمائیم. از اینرو با افزایش تعداد کارها تعداد نگاشتهای موجود به صورت نمایی اضافه میشوند. به عنوان مثال با داشتن 10 کار و 4 منبع تعداد 1048576 نگاشت مختلف را میتوانیم برای واگذاری کارها به منابع داشته باشیم. از اینرو سعی در تولید یک نگاشت نزدیک به بهینه داریم و نمیتوانیم حالت بهینه را برای واگذاری کارها به منابع را تولید نمائیم.
2-16 جمع بندی
با توجه به توضیحاتی که در این فصل در رابطه با الگوریتم ژنتیک و مسئله زمانبندی داده شد؛ استفاده از الگوریتم ژنتیک یکی از گزینههای مناسب، برای حل مسئله زمانبندی میباشد. در سالهای اخیر به انواع مختلف از مزایای الگوریتم ژنتیک برای حل مسئله زمانبندی استفاده شده است. در فصل سوم به بررسی الگوریتمهای مختلفی که برای حل مسئله زمانبندی ارائه شده است از جمله الگوریتمهای تکاملی مثل الگوریتم ژنتیک میپردازیم.

پیشینه پژوهشی
3-1 مقدمه
در این فصل به بررسی روشهای مختلفی که برای مسئله زمانبندی ارائه شده است میپردازیم. روشهای حریصانه و تکاملی را شرح داده و پژوهشهایی که از این روشها برای حل مسئله زمانبندی استفاده کردهاند را بیان میکنیم.
برای زمانبندی در محیط گرید میتوان از روشهای مختلفی استفاده کرد. به طور کلی روشهای موجود را به دسته الگوریتمهای حریصانه و تکاملی تقسیم مینماییم. در روشهای حریصانه با هر بار اجرا به یک نتیجه میرسیم و با سرعت مطلوبی به جواب میرسیم ولی اگر از روشهای تکاملی استفاده کنیم میتوانیم به جوابهای بهتری دست پیدا کنیم ولی باید ضرری را به واسطه اجرای طولانیتر برای زمان اجرا بپردازیم.
3-2 الگوریتمهای حریصانه
در این قسمت به بررسی چند الگوریتم حریصانه که برای حل مسئله زمانبندی استفاده میشوند میپردازیم و چگونگی تولید نگاشت کارها به منابع در هر الگوریتم را مشخص میکنیم.
الگوریتم توازن بار فرصت طلب[27]:
در این الگوریتم برای هر کار نخستین منبع بیکار (آزاد) را بدون در نظر گرفتن زمان اجرای این کار روی آن منبع، انتخاب میشود. با استفاده ازاین روش بار کاری را روی منابع مختلف پخش میکنیم ولی از لحاظ کمینه کردن زمان اتمام آخرین کار عملکرد خوبی را ندارد.
الگوریتم حداقل زمان اجرا[27]:
در این الگوریتم کارها را، بر اساس کمترین زمان اجرای مورد انتظار بدون در نظر گرفتن در دسترس بودن منبع و بار کاری جاری، اختصاص داده میشود. استفاده از این الگوریتم باعث بهبود کمینه کردن زمان اتمام کلیه کارها نسبت به الگوریتم توازن بار فرصت طلب میشود ولی مسئله پخش بار کاری در نظر گرفته نمیشود.
الگوریتم حداقل زمان اتمام[27]:
این الگوریتم کارها را براساس کمترین زمان اتمام به منابع تخصیص میدهد. زمان اتمام، حاصل جمع زمان اجرای مورد انتظار و زمانی که طول میکشد تا منبع آماده اجرا این کار شود، میباشد. در این الگوریتم در هر زمان فقط یک کار در نظر گرفته میشود.
سه الگوریتم توازن بار فرصت طلب، حداقل زمان اجرا و حداقل زمان اتمام میتوانند هم در زمانبندی پویای کارها و هم در زمانبندی ایستا مورد استفاده قرار گیرند. به دلیل اینکه تصمیمگیری را فقط بر اساس کار مورد نظر و منابع موجود انجام میدهند و نیازی به بررسی کارهای دیگر ندارند.
الگوریتم کمترین کمترین [27]:
این الگوریتم با یک مجموعه از کارهای تخصیص داده نشده شروع و منبعی با کمترین زمان اتمام برای همه کارها را انتخاب میکند؛ سپس کار با کمترین زمان اتمام نسبت به بقیه انتخاب و به آن منبع تخصیص داده میشود. زمان آماده به کاربودن منبع تخصیص یافته به روزرسانی شده کار از مجموعه کارهای تخصیص داده نشده حذف و مراحل ذکر شده تکرار میشوند تا برای تمامی کارهای تخصیص داده نشده منبع مشخص گردد. در مقایسه با الگوریتم حداقل زمان اتمام این الگوریتم همه کارها را در یک زمان بررسی میکند و از اینرو نتیجه بهتری را در کاهش زمان اتمام کلی کارها، نسبت به الگوریتم حداقل زمان اتمام خواهد داشت.
الگوریتم بیشترین کمترین [27]:
روند الگوریتم بیشترین کمترین شبیه به الگوریتم کمترین کمترین میباشد به استثناء اینکه پس از مشخص کردن سریعترین منبع برای هر کار به جای در نظر گرفتن کمترین زمان اتمام کلی در کارها، بیشترین زمان اتمام کلی انتخاب میشود. هدف اصلی این الگوریتم کاهش زمان انتظار کارهای بزرگ است.
الگوریتم حق رای [27]:
الگوریتم حقرای شبیه به الگوریتم کمترین کمترین عمل میکند با این تفاوت که علاوه بر کمترین زمان اتمام، دومین کمترین زمان اتمام هم، برای هر کار محاسبه میشود. اختلاف این دو زمان برای هر کار، محاسبه میشود. کاری که دارای بیشترین اختلاف باشد اولویت بالاتری میگیرد و برای زمانبندی انتخاب میشود. کار انتخاب شده به منبعی که کمترین زمان اتمام را داشته تخصیص داده میشود. این کار از لیست کارهای نگاشت نشده حذف و مراحل ذکر شده تکرار میشوند تا تمامی کارها به منابع تخصیص داده شوند. در واقع الگوریتم حقرای سعی میکند به کارهایی که به واسطه واگذار نشدن به بهترین منبع خود بیشترین ضرر را میکنند اولویت بالاتری بدهد.
الگوریتم بزرگترین کار روی سریعترین منبع – کوچکترین کار روی سریعترین منبع [27]:
در این الگوریتم سعی میشود از مزایای هر دو الگوریتم بزرگترین کار روی سریعترین منبع و کوچکترین کار روی سریعترین منبع استفاده نمائیم. در الگوریتم بزرگترین کار روی سریعترین منبع به کارهای بزرگ اولویت داده میشود و در الگوریتم کوچکترین کار روی سریعترین منبع به کارهای کوچک اوایت داده میشود. در این روش اگر تعداد کارها را n و تعداد منابع را m در نظر بگیریم. ابتدا تعداد m کار را طبق الگوریتم بیشترین کمترین به منابع تخصیص داده و سپس از کار m+1 تا n به تناوب از الگوریتمهای کمترین کمترین و بیشترین کمترین استفاده میکند.
3-3 الگوریتمهای تکاملی
با توجه به NP-Complete بودن زمانبندی، هدف پیدا کردن یک نگاشت از کارها به منابع نزدیک به بهینه است. یکی از کاربردهای الگوریتمهای تکاملی حل مسائل بهینهسازی میباشد. تاکنون از الگوریتمهای متفاوت تکاملی برای پیدا کردن یک نگاشت بهینه استفاده شده است که در ادامه به بررسی چند مورد از این روشها میپردازیم:
3-3-1راهکارهای مبتنی بر جستجوی محلی :
روش های جستجوی محلی برای کاوش فضای راه حل از یک جواب به جواب دیگر می پرند و یک مسیر را در فضای راه حل با این هدف که بتوانند بهترین راه حل را برای مسئله موجود پیدا کنند، ایجاد میکنند. روش های تپه نوردی، شبیه سازی ذوب و جستجوی ممنوعه از این منطق استفاده می کنند.
در روش تپه نوردی پس از تولید یک نگاشت سعی میشود با تغییر در نگاشت، راهحل بهتری بدست آید. درصورتیکه با اعمال تغییر به راهحل بهتری رسیدیم راهحل جدید جایگزین قبلی میشود و در غیر این صورت از راه حل جدید صرف نظر میشود.
Ritchie و Levin [28] در سال 2003 از این روش بر مبنای الگوریتم حداقل زمان اتمام استفاده کردهاند.
روش تپه نوردی به دو دلیل مورد توجه قرار گرفته است :
با استفاده از این روش میتوان در زمان کوتاهی یک جواب قابل قبول و با کیفیت مشخص را برای مسئله پیدا کرد.
از این روش میتوانیم برای تولید راهحلهای اولیه در روشهای تکاملی جمعیت محور استفاده کنیم.
با توجه به اینکه روش تپهنوردی راهحلهای بدتر از راهحل جاری را انتخاب نمیکند و همیشه میل به بهبود برای حرکت دارد، امکان دارد در قلههای محلی افتاده و نتواند از قلههای محلی خارج شود.
روش شبیه سازی ذوب از فاکتوری استفاده میکند که در حین اجرای برنامه مقدارش تغییر مینماید. در ابتدا با استفاده از فاکتور موجود به راهحلهای بد نیز شانسی برای انتخاب شدن میدهد ولی با پیشرفت الگوریتم و تغییر این فاکتور این شانس در تکرارهای بعدی کاهش مییابد. با توجه به این مورد، الگوریتم شبیهسازی ذوب نسبت به تپه نوردی قدرتمندتر عمل میکند. Yarkhan و Dongarra [29] در سال 2002 برای حل مسئله زمانبندی از این روش استفاده کردهاند.
روش شبیهسازی ذوب اگرچه با تعریف فاکتوری به راهحلهای بد هم شانس انتخاب میدهد ولی در تکرارهای بالا شانس انتخاب راهحلهای بد کاهش مییابد و مثل الگوریتم تپه نوردی در قلههای محلی میافتد و توانایی خارج شدن از آنها را ندارد.
در روش جستجوی ممنوعه سعی میشود از تکرار مسیرهایی که تا کنون بررسی شدهاند جلوگیری نمائیم. از اینرو از حافظهای کمک میگیریم و راهحلهایی را که تا کنون بدست آوردیم درون این حافظه قرار میدهیم. برای دور بعد اگر راهحل موجود در حافظه وجود داشت انتخاب نمیشود. به دلیل اینکه راهحلهای گوناگونی میتوانند تولید شوند امکان ذخیره همهی این موارد را نداریم و مقدار فضایی که برای حافظه در نظر میگیریم تاثیر زیادی در عملکرد جستجوی ممنوعه خواهد داشت. جستجوی ممنوعه احتیاج به زمان محاسبات بیشتری دارد و با مهارت بیشتری نسبت به دو روش قبل به دنبال بهترین راه حل میگردد. Ritchie [30] در سال 2003 جستجوی ممنوعه را بر پایه حداقل زمان اتمام در ترکیب با الگوریتم مورچه ها به کار برده است.
نکته منفی که میتوان برای الگوریتم جستجوی ممنوعه در نظر گرفت حافظه مصرفی این الگوریتم است. درصورتیکه مقدار این حافظه مصرفی را کاهش دهیم الگوریتم با دقت پایینتری کار میکند و توانایی خود را برای تولید راهحلهای مناسب از دست میدهد.
3-3-2راهکارهای جمعیت محور :
روشهای جمعیت محور معمولا به زمان اجرایی بیشتری برای تولید جواب بهینه یا نزدیک به بهینه احتیاج دارند. الگوریتمهای ژنتیک، ممتیک، مورچهها و حرکت ذرات جمعیت محور میباشند.
الگوریتم ژنتیک:
Zomaya و Teh [31] در سال 2001 از الگوریتم ژنتیک برای حل مسئله زمانبندی استفاده کردهاند. در این روش برای نمایش زمانبندی های اولیه جمعیت، از آرایه دوبعدی پردازنده و کار استفاده شده است و به دلیل اینکه عملیات مربوط به آمیزش و جهش روی آرایه یک بعدی اعمال میشوند، آرایه مذکور را سطر به سطر به یکدیگر متصل و یک آرایه یک بعدی را برای نمایش هر کروموزوم در جمعیت استفاده میکند. برای عملیات آمیزش از آمیزش چرخشی استفاده میکند که تضمین میکند واگذاری هر کار روی یک ماشین و نه بیشتر صورت گیرد. برای عملیات جهش از دو والد موجود دو ماشین و روی هر ماشین یک کار به صورت تصادفی انتخاب و با یکدیگر جابجا میکند. از روش چرخ رولت نیز برای قسمت مربوط به انتخاب نسل بعد جمعیت استفاده میکند.
الگوریتم ممتیک :
الگوریتم ممتیک نسبت به دیگر روشهای بهینهسازی جمعیت محور مرسوم، روش جدیدتری میباشد و سعی در ترکیب مفاهیم روشهای جستجوی محلی و جمعیت محور دارد به صورتیکه بتواند از جنبه های مثبت هر دو روش استفاده کند.
Xhafa و همکارانش [32] در سال 2008 از الگوریتم ممتیک برای زمانبندی استفاده کرده اند. در روش استفاده شده در قسمتهای مربوط به تولید نسل اولیه، پس از عملیات آمیزش و جهش روی راه حل های بدست آمده جستجوی محلی را صورت میدهد و در صورتیکه جواب بدست آمده از اعمال جستجوی محلی نسبت به جواب قبل بهتر بود، جایگزین آن میشود.
برای نمایش جمعیت اولیه از یک آرایه یک بعدی به اندازه کارها استفاده میکند. مقادیر ذخیره شده در هر عنصر آرایه نمایانگر ماشینی میباشد که این کار روی آن قرار داده شده است. برای تولید جمعیت اولیه از تولید تصادفی راهحل ها و روش بزرگترین کار روی سریعترین منبع و کوچکترین کار روی سریعترین منبع استفاده میکند.
برای پیاده سازی آمیزش از دو روش زیر استفاده میکند :
قرار دادن یک نقطه انفصال واحد برای هر دو والد و انتخاب قسمت قبل از نقطه انفصال از والد اول و بعد از آن از والد دوم برای یک فرزند و بلعکس برای تولید فرزند دیگر.
انتخاب عناصر آرایه فرزند از عناصر مربوط به هر والد با یک احتمال خاص.
برای پیادهسازی جهش از روشهای زیر استفاده میکند :
انتخاب تصادفی یک کروموزوم و جابجایی عناصر آن با یکدیگر.
انتخاب تصادفی دو کروموزوم و جابجایی عناصر آنها با یکدیگر.
استفاده از ترکیب دو روش بالا.
انتخاب تصادفی یک کروموزوم و جابجایی عناصر داخل آن با استفاده از بررسی فاکتوری خاص که باعث توازن شود.
و در نهایت برای پیادهسازی جستجوی محلی از روشهای زیر استفاده میکند:
به صورت تصادفی از درون آرایه نمایش دهنده هر کروموزم یک کار را انتخاب و به ماشینی که به صورت تصادفی انتخاب شده تخصیص میدهد.
کار انتخاب شده به ماشینی منتقل میشود که بهترین بهبود را در کاهش زمان اتمام داشته باشد.
دو کاری که به دو ماشین مختلف تخصیص داده شدهاند با یکدیگر جابجا می شوند به صورتیکه بهترین کاهش را در زمان اتمام کل داشته باشند.
جستجوی محلیای را بر پایه استفاده از جستجوی ممنوعه استفاده میکند.
Nesmachnow و همکارانش [33] در سال 2011 الگوریتم موازی ژنتیکی به نام pCHC ارائه دادند که سعی در پیدا کردن راهحل بهینه داشتند. برای رسیدن به این هدف جمعیت اولیه را به چند زیر جمعیت تقسیم کرده و برای هر زیر جمعیت یک الگوریتم ژنتیک را اجرا میکردند؛ در حین اجرا زیر جمعیتها در شرایط خاصی راهحلهایی را بین یکدیگر جابجا میکردند. با استفاده از مزایای اجرای موازی و جابجایی راهحلها بین هر زیر جمعیت توانستند به بهترین نتیجه در کاهش زمان اتمام آخرین کار، تا آن زمان دست یابند.
راهحل ارائه شده در سال 2011 pCHC، نتایج خوبی به همراه داشت ولی به دلیل اینکه جمعیت اولیه به چند زیر جمعیت تقسیم شده بود به سرعت تنوع خود را در جمعیتهای موجود در حین اجرای الگوریتم از دست میداد. برای حل این مشکل Nesmachnow و همکارانش [34] در سال 2012 الگوریتم دیگری را بر پایه الگوریتم pCHC ارائه دادند و نام آن را pµ-CHC گذاشتند و سعی کردن مشکل عدم تنوع را در الگوریتم pCHC رفع کنند.
برای رسیدن به این هدف دو حافظه را برای اجرای الگوریتم استفاده میکردند. یک حافظه برای نگهداری بهترین راهحلهای پیدا شده و یک حافظه هم برای نگهداری راهحلهای تولید شده در حین اجرای الگوریتم. زمانیکه جمعیت موجود برای هر زیر جمعیت به سمت همگرا شدن میل میکرد راهحلهایی را بین زیر جمعیتهای موجود جابجا میکردند. برای بالا بردن تنوع در الگوریتم از یک تابع نیز استفاده میکردند که میتوانست راهحلهایی جدید را به جمعیت موجود وارد نماید. با استفاده از این روش توانستند تا حدی مشکلات روش pCHC را حل نمایند.
3-4 جمعبندی
با توجه به مطالبی که در این فصل مورد بررسی قرار گرفت استفاده از روشهای تکاملی میتواند یک راهحل مناسب برای حل مسئله زمانبندی باشد. اگرچه زمان اجرایی این روشها نسبت به روشهای حریصانه بیشتر است ولی به جواب، به مراتب بهتری نسبت به روشهای حریصانه دست پیدا میکنند. با همین رویکرد برای حل مسئله زمانبندی از الگوریتم ژنتیک برای حل مسئله زمانبندی استفاده شده و از روشهای ارائه شده توسط Nesmachnow و همکارانش [34,35] که در سالهای 2011 و 2012 ارائه شده است ایده گرفته شده است.

الگوریتمهای پیشنهادی
4-1 مقدمه
در این فصل روشهای پیشنهادی برای حل مسئله زمانبندی را بیان میکنیم. برای حل مسئله زمانبندی 5 راهکار را پیشنهاد میدهیم که 2 مورد مربوط به روشهای حریصانه، 2 مورد مربوط به الگوریتمهای توازن و یک روش ترکیبی از الگوریتم ژنتیک به همراه الگوریتم توازن میباشند. در ادامه به بررسی جزئیان این روشها میپردازیم.
روش پیشنهادی اصلی ترکیبی از یک جستجوی محلی (الگوریتم توازن) و الگوریتم ژنتیک میباشد. جستجوی محلی یک راهحل را دریافت کرده و با جابجایی و انتقالهایی که صورت میدهد سعی میکند زمان اتمام آخرین کار را برای راهحل مربوطه کاهش داده و باعث ایجاد توازن بار روی ماشینها گردد به نحوی که زمان اتمام کلیه ماشینها را به هم نزدیک کند. جستجوی محلی عملکرد خوبی در ایجاد توازن بار دارد ولی باعث کاهش چشمگیری در زمان اتمام نمی شود و عملکردش وابسته به راهحلی میباشد که به عنوان ورودی پذیرفته است. برای اینکه جستجوی محلی بتواند تاثیر خود را روی کاهش زمان اتمام نیز داشته باشد، بایستی راهحلهای مناسبی را به عنوان ورودی دریافت کند تا نتیجه مطلوبی را داشته باشد. تنوع راهحلهای ورودی به جستجوی محلی میتواند خروجیهای متفاوتی را داشته باشد و باعث کاهش یا افزایش زمان اتمام آخرین کار شود. برای اینکه راهحلهای متفاوتی را تولید و به جستجوی محلی واگذار کنیم از الگوریتم ژنتیک استفاده میکنیم. الگوریتم ژنتیک به دلیل ساختارش کمک میکند تا راهحلهای متنوعی را تولید نمائیم و این مسئله میتواند به هر چه بهتر عمل کردن جستجوی محلی کمک نماید. در روش ارائه شده سعی میکنیم از مزایای الگوریتم ژنتیک نیز استفاده کنیم و صرفا برای تولید یکسری راهحل، بکار گرفته نمیشود. در ادامه ابتدا فرضیات و تعاریف مهم را آورده وسپس دو الگوریتم حریصانه ارائه شده برای زمانبندی کارهای دستهای را مورد بحث قرار میدهیم، پس از آن دو روشی را که برای ایجاد توازن بار به کار بردهایم را مورد بررسی قرار میدهیم و در آخر الگوریتم اصلی که ترکیبی از الگوریتم ژنتیک و جستجوی محلی میباشد را ارائه میکنیم. برای پیادهسازی الگوریتم ژنتیک از روشهای که توسط Nesmachnow و همکارانش[34,35] که در سالهای 2011 و 2012 برای الگوریتم ژنتیک ارائه شده است، استفاده میکنیم.
4-2 فرضیات و تعاریف
فرض کنید نشان دهنده یک مجموعه n تایی از کارهای مستقل از یکدیگر و نشان دهنده یک مجموعه m تایی از منابع در محیط گرید محاسباتی میباشد.
در زمان شروع تمام منابع و کارها جهت پردازش در دسترس میباشند. زمان مورد انتظار پردازش برای هر کار روی هر منبع، در ماتریس ETC قرار دارد. ماتریس ETC یک ماتریس n*m میباشدکه n تعداد کارها و m تعداد منابع میباشد. ETC (i,j) نشاندهنده زمان مورد انتظار پردازش کار i روی ماشین j میباشد. زمان اتمام کار i، طبق فرمول (1) محاسبه می شود
(1)
نشاندهنده میزان حجم کار منبع j ، قبل از شروع پردازش کار i میباشد (زمانی که کار i بایستی روی منبع j منتظر بماند تا شروع به اجرا کند).
جهت ارزیابی کیفیت الگوریتم های زمانبند معیارهای متفاوتی موجود است که متداولترین معیارها عبارتند از :
زمان اتمام آخرین کار: محبوب ترین معیار بهینهسازی به حداقل رساندن زمان اتمام آخرین کار میباشد. این معیار توان سیستم گرید، را نشان میدهد. زمان اتمام آخرین کار طبق فرمول (2) محاسبه میشود.
(2)
مجموع زمان اتمام کلیه کارها: این زمان کیفیت خدمات سیستم گرید را نشان می دهد. زمان اتمام کلیه کارها طبق فرمول (3) محاسبه میشود.
(3)
بهره وری منابع (سودمندی منابع): این معیار توازن بار سیستم گرید را نشان میدهد. بهره وری منابع طبق فرمول (4) محاسبه میشود.
(4)
نشان دهنده میزان حجم کار منبع j میباشد.
برای حل مسئله زمانبندی الگوریتمهای Asuffrage، MaxSuffrage، دو الگوریتم توازن و یک الگوریتم ترکیبی را ارائه کردهایم که به شرح آنها میپردازیم.
4-3 الگوریتم پیشنهادی Asuffrage
در الگوریتم حق رای هزینه هر کار را براساس اختلاف مابین دومین کمترین زمان اتمام و اولین کمترین زمان اتمام محاسبه میشود و کار با بالاترین اختلاف انتخاب میگردد؛ در واقع الگوریتم حق رای فقط یک مرحله بعد را در انتخاب کار در نظر میگیرد و ضرری را که به واسطه انتخاب نشدن بهترین منبع برای کار متحمل میشویم را معیار ارزیابی قرارداده و با توجه به این فاکتور کارها را به منابع واگذار میکند.
در الگوریتم پیشنهادی (Asuffrage) سعیمی کنیم افق دید خود را گسترش داده و به جای ملاک قراردادن یک مرحله بعد، تعدادی از مراحل را در تصمیم گیری دخیل کنیم. در هر دور به جای زمان اتمام دومین کمترین زمان اتمام، میانگین زمان اتمام را برای کار i روی منابع موجود بدست میآوریم (فرمول (6)) تا بتوانیم بازه تغییرات زمان اتمام را در تصمیمگیری دخالت دهیم. جهت اولویتدهی به کارهایی که سریعتر به مرز میانگین تغییرات خود نزدیک می شوند، تعداد منابعی که زمان اتمامشان کمتر از میانگین زمان اتمام برای کار i میباشد را شمارش مینمائیم (فرمول (8)) و عدد بدست آمده را در اختلاف میانگین زمان اتمام (فرمول (6)) و کمترین زمان اتمام (فرمول (7)) ضرب میکنیم (فرمول (5)) تا اولویت کارهایی که زودتر به مرز میانگین تغییرات میرسند بیشتر شود.
(5)
(6)
(7)
(8)
کار با بالاترین هزینه انتخاب، به منبعی که دارای کمترین زمان اتمام میباشد تخصیص داده میشود؛ این کار را از لیست کارهای نگاشت نشده حذف، ماتریس زمان اتمام کارها بروزرسانی و الگوریتم تکرار میشود تا زمانی که تمام کارها نگاشت داده شوند.
4-4 الگوریتم پیشنهادی MaxSuffrage
الگوریتم MaxSuffrage حاصل ادغام الگوریتم بیشترین کمترین و الگوریتم حقرای با اعمال یکسری تغییرات میباشد. در الگوریتم بیشترین کمترین برای هر کار کمترین زمان اتمام را محاسبه و از بین این مقادیر کار با بیشترین زمان اتمام را انتخاب و به منبع با کمترین زمان اتمام واگذار مینماییم. هدف الگوریتم بیشترین کمترین، اولویت دادن به کارهای بزرگ است. برای بهبود عملکرد الگوریتم بیشترین کمترین بجای در نظر گرفتن کمترین زمان اتمام برای هر کار، k امین کمترین زمان اتمام را در نظر میگیریم (نزدیک ترین ستون به میانگین تغییرات). در ابتدای الگوریتم تنها یکبار مقدار k محاسبه شده و در ادامه الگوریتم از این مقدار استفاده میگردد. مقدار k با استفاده از فرمول (9) و (10) محاسبه می گردد. در ابتدا زمان اتمام کارها بر روی تمام منابع را محاسبه، درون یک ماتریس n*m ذخیره مینماییم(Mct) که n تعداد کارها و m تعداد منابع میباشد. ماتریس Mct قبل از هر واگذاری محاسبه شده و بصورت سطری مرتب میگردد.
مقادیر مربوط به مجموع درصد تغییرات فرمول (9) و میانگین کلی تغییرات فرمول (10) به صورت زیر محاسبه میگردد.
(9)
(10)
بطور مثال Sum[j=2]برابر با مجموع دومین کمترین زمان اتمام کار، تقسیم بر اولین کمترین زمان اتمام کار، در تمام کارها میباشد. همانطور که در بالا ذکر شد هر سطر ماتریس Mct به صورت صعودی مرتب شده است به همین دلیل ستون j مقدار بیشتری را نسبت به ستون j-1 خواهد داشت.
حال با توجه به مقادیر آرایه Sum ستونی را که اختلافش با میانگین تغییرات (AvgCh) کمترین باشد به عنوان ستون اصلی تغییرات در نظر گرفته و آن را ستون k مینامیم. در واقع ستون k برای هر کار، زمان اتمامی را نشان میدهد که میانگین تغییرات را در خود جای داده است و از آنجایی که ماتریس MCT مرتب میباشد ستون k برابر با kامین کمترین زمان اتمام میباشد و در الگوریتم ارائه شده از همین ستون (k) در الگوریتم بیشترین-کمترین استفاده مینماییم. ادامه الگوریتم طبق روال زیر میباشد و تا زمانی که کلیه کارها به منابع واگذار گردند تکرار میشود.
برای کلیه کارهای واگذار نشده هزینه طبق فرمول (11) محاسبه می‏گردد.
(11)
، اختلاف دومین کمترین زمان اتمام و اولین کمترین زمان اتمام کار i (الگوریتم حقرای) و ، k امین کمترین زمان اتمام کار i (الگوریتم بیشترین-کمترین).
کار با بالاترین هزینه انتخاب و به منبعی که دارای کمترین زمان اتمام میباشد تخصیص داده میشود.
کار واگذار شده از لیست کارهای نگاشت نشده حذف، ماتریس زمان اتمام کارها بروز رسانی و بصورت سطری مرتب میگردد.
با استفاده از روش ذکر شده سعی در استفاده از مزایای دو الگوریتم حق رای و بیشترین-کمترین داریم (دخالت دادن ضرر ناشی از واگذار نشدن کار به بهترین منبع در عملیات نگاشت- اولویت دهی به کارهای بزرگ است).
4-5 الگوریتم پیشنهادی توازن نسخه یک
در بسیاری از الگوریتم ها، جستجوی محلی برای بهتر شدن جواب و رسیدن به بهینه ی محلی استفاده می شود. مهمترین قسمت یک الگوریتم جستجوی محلی، تعریف و انتخاب همسایه میباشد. انتخاب همسایه باید به نحوی انجام شود که تابع هدف بهینهتر شود. از آنجایی که در زمانبندی هدف کم کردن زمان اتمام آخرین کار میباشد همسایهها را باید طوری انتخاب کرد که این معیار کاهش پیدا کند. برای انتخاب همسایه از دو عملگر انتقال و معاوضه برای تغییر فضای جستجو استفاده میکنیم. در حالت انتقال، یک کار از یک منبع به یک منبع دیگر انتقال پیدا میکند. منظور از معاوضه جابجا کردن دو کار در دو منبع میباشد. هر کدام از این تغییرها ممکن است زمان اتمام آخرین کار را کمتر یا بیشتر کنند که باید مورد بررسی قرار گیرند.
دو مساله زیر مطرح است:
الف) انتخاب همسایهی بهتر: در بسیاری از جستجوهای محلی اولین همسایه بهتر را انتخاب میکنند ولی این انتخاب ممکن است که خیلی بهینه نباشد. در بعضی از الگوریتمها تمام همسایهها را در نظر میگیرند که خیلی زمانبر است.
ب) انتخاب منابع: برای انجام انتقال یا معاوضه می باشد. در روشی که در این پایاننامه ارائه داده ایم علاوه بر بهینه بودن جواب، زمان اجرای الگوریتم را نیز در نظر گرفتهایم. زمان در الگوریتم هایی مثل ژنتیک، مورچه ها و … که از جستجوی محلی استفاده میکنند نیز اهمیت پیدا می کند چون خود این الگوریتم ها زمانبر میباشند.
در الگوریتم ارائه شده، جستجوی محلی بر روی خروجی الگوریتم کمترین – کمترین اعمال می شود. مراحل اجرای الگوریتم به شرح زیر می باشند.
فرض می کنیم که m تعداد منابع و n تعداد کارها در منبعی است که بیشترین زمان اتمام را دارد.
ابتدا منبع Rhigh که بیشترین زمان اتمام را دارد مشخص می شود.
با رعایت ترتیب کارها، به ازای تمام کارها در منبع Rhigh : اگر با انتقال کار Ti (1<i<=n)، از منبع Rhigh به منبع Rj (j!=high,1<j<=m)، زمان اتمام آخرین کار کاهش یافت، کار Ti را از منبع Rhigh به Rj انتقال بده.
اگر زمان اتمام آخرین کار کاهش یافت به 1 برو در غیر این صورت به ازای تمام کارها در منبع Rhigh، زمان اتمام آخرین کار را به ازای معاوضهی کار Ti از منبع Rhigh با کارهایی که در دیگر منابع وجود دارند بدست بیاور.
در صورتی



قیمت: 10000 تومان

متن کامل در سایت homatez.com

About: admin


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

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *