شبکههای تورین محاسباتی (گرید) زمینه‌ای را فراهم آورده است که بتوان از منابع ناهمگن در نقاط مختلف جغرافیایی برای حل مسائل پیچیده علمی، مهندسی و تجارت استفاده کرد. عملیات زمانبندی نقش کلیدی در عملکرد گرید ایفا میکند. در این پایان نامه با استفاده از مزایای الگوریتم ژنتیک، پنج الگوریتم زمانبندی برای نگاشت بهینهای از کارهای دستهای روی ماشینها ارائه شده است که تمامی فضای جستجو مسأله زمانبندی را بررسی کرده و یک توازن بار روی همه ماشینها ایجاد نماید. نتایج پیادهسازی الگوریتمهای ارائه شده نشان دهنده متوسط کاهش 13.23 درصد در زمان اتمام آخرین کار نسبت به الگوریتم های پیشین است.کلید واژه: گرید محاسباتی، زمانبندی، توازن بار. فهرست مطالب1- مقدمه ....... 11-1 مقدمه ........... 11-2 هدف از اجرای پایاننامه ........................................................................................... 21-3 مراحل انجام پایاننامه ............................................................................................... 21-4 ساختار پایاننامه ......................................................................................................... 32- ادبیات موضوعی .................................................................................................... 42-1 مقدمه ............................................................................................................................ 42-2 ساختار الگوریتم ژنتیک ............................................................................................. 62-3 عملگرهای ژنتیکی ....................................................................................................... 72-4 روند کلی الگوریتم ژنتیک .......................................................................................... 82-5 شرط پایان الگوریتم .................................................................................................... 102-6 برخی از کاربردهای الگوریتم ژنتیک ........................................................................ 102-7 تعاریف .............................................................................................................................. 112-8 مزایای اجرای موازی ..................................................................................................... 122-9 مراحل زمانبندی در گرید ......................................................................................... 162-10 انواع زمانبند ................................................................................................................. 172-11 انواع زمانبندی ............................................................................................................ 182-12 نحوهی زمانبندی (ایستا و پویا) .............................................................................. 192-13 ساختار زمانبند ........................................................................................................... 192-14 انواع صفبندی کارها ................................................................................................. 212-15 پیچیدگی محاسباتی زمانبندی ...............................................................................222-16 جمع بندی ............................................................................................................... 223- پیشینه پژوهشی .................................................................................................. 233-1 مقدمه ............................................................................................................................ 233-2 الگوریتمهای حریصانه ............................................................................................... 233-3 الگوریتمهای تکاملی .................................................................................................. 263-3-1 راهکارهای مبتنی بر جستجوی محلی ................................................ 263-3-2 راهکارهای جمعیت محور ...................................................................... 283-4 جمعبندی .................................................................................................................. 314- الگوریتمهای پیشنهادی ...................................................................................... 334-1 مقدمه ............................................................................................................................ 334-2 فرضیات وتعاریف ......................................................................................................... 344-3 الگوریتم Asuffrage.................................................................................................. 354-4 الگوریتم MaxSuffrage ............................................................................................ 364-5 الگوریتم توازن نسخه یک ......................................................................................... 384-6 الگوریتم توازن نسخه دو ........................................................................................... 404-7 الگوریتم ژنتیک و توازن بار ...................................................................................... 414-8 جمعبندی ..................................................................................................................... 465- نتایج حاصل از ارزیابی........................................................................................... 475-1 مقدمه ............................................................................................................................ 475-2 محک ارزیابی براون ................................................................................................... 475-3 ارزیابی الگوریتم Asuffrage.................................................................................... 495-4 ارزیابی الگوریتم MaxSuffrage.............................................................................. 515-5 ارزیابی الگوریتم توازن نسخه یک ............................................................................ 535-6 ازریابی الگوریتم توازن نسخه دو .............................................................................. 545-7 ارزیابی الگوریتم ژنتیک به همراه توازن بار............................................................. 555-8 پیشنهادات برای آینده .............................................................................................. 576- منابع ..................................................................................................................... 58 فهرست جداول عنوان صفحه جدول 5-1 حالات ماتریس ETC....................................................................................................... 49جدول 5-2 نتایج makespanالگوریتم Asuffrage...................................................................... 50جدول 5-3 نتایج resourceutilizationالگوریتم Asuffrage............................................... 51جدول 5-4 نتایج makespanالگوریتم MaxSuffrage............................................................... 52جدول 5-5 نتایج resourceutilizationالگوریتم MaxSuffrage......................................... 53جدول 5-6 نتایج makespanالگوریتم توازن نسخه یک .............................................................. 54جدول 5-7 نتایج makespanالگوریتم توازن نسخه دو................................................................. 55جدول 5-8 نتایج makespanالگوریتم ژنتیک به همراه توازن بار.............................................. 56جدول 5-9 نتایج resourceutilizationالگوریتم ژنتیک به همراه توازن بار ........................... 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] زمینه‌ای را فراهم آورده است که بتوان از منابع (کامپیوتری) سیستم‌های دیگر نیز استفاده نماییم. اغلب مسائل پیچیده علمی، مهندسی و تجارت احتیاج به میزان زیادی از منابع برای اجرا دارند، بهترین راه حل برای اینگونه مسائل استفاده از گرید میباشد[1].هدف شبکههای محاسباتی (گرید) به اشتراک گذاشتن منابع کامپیوتری در نقاط مختلف جغرافیایی با مدیریتهای مختلف بین کاربران است. کاربران درخواستهای خود را پیوسته برای محیط گرید ارسال میکنند و بخش مدیریت منابع[2] این کارها را به گره های محاسباتی[3] موجود در شبکه اختصاص میدهد. به چگونگی تخصیص این درخواستها روی گرههای محاسباتی مختلف زمانبندی[4] میگویند.اعمال سیاستهای مختلف برای عملیات زمانبندی نتایج متفاوتی را خواهد داشت که این سیاست با توجه به اهداف مشخص شده برای گرید اتخاذ میشوند. عملیات زمانبندی در سیاستهای مختلف از فاکتورهای متفاوتی برای تخصیص کارها روی منابع مختلف استفاده میکند. امکان دارد یک فاکتور نقش تعیین کنندهای در یکی از سیاستها داشته باشد ولی در سیاست دیگر اصلا به آن توجه نشود، از اینرو هدف هر الگوریتم بهینه کردن سیاست مورد نظر خود است. 1-2 هدف از اجرای پایان نامهبا توجه به تاثیر بالای عملیات زمانبندی در عملکرد بهینه گرید و مزایایی که برای گرید در قسمت قبل ذکر شد، ارائه یک روش کارا در زمانبندی می تواند تاثیر زیادی در حل مسائل بزرگ در شاخه های مختلف داشته باشد.در گریدهای محاسباتی هدف بالا بردن درصد استفاده از منابع در کنار کاهش زمان اتمام آخرین کار میباشد. در این طرح تحقیق همین اهداف را دنبال میکنیم و سعی داریم نگاشتی از کارها را ارائهدهیم که هم باعث بالا رفتن بهرهوری از منابع شود و هم کمترین زمان را برای اتمام آخرین کار داشته باشد. 1-3 مراحل انجام پایان نامهبرای انجام پایاننامه ابتدا مفاهیم گرید و روشهای موجود مطالعه و بررسی شدند و بعد از مقایسه صورت گرفته روی روشهای مختلف، الگوریتم ژنتیک برای تولید نگاشت انتخاب شد. در کنار الگوریتم ژنتیک الگوریتمی را ارائه کردیم که به توازن بار روی منابع کمک میکند و با استفاده از مزایای دو الگوریتم نام برده شده نگاشت بهینهای را برای کارها بدست آوردیم. برای پیادهسازی الگوریتمها از زبان برنامه نویسی javaشده است. 1-4 ساختار پایان نامهدر فصل دوم الگوریتم ژنتیک، پارامترهای موثر در این الگوریتم و مفاهیم اولیهی زمانبندی مورد بررسی قرار میگیرد. در فصل سوم گذری بر تحقیقات پیشین خواهیم داشت. الگوریتمهای پیشنهادی در فصل چهارم ارائه شده است و در فصل پنجم نتایج حاصل از ارزیابی و مقایسه الگوریتمهای پیشنهادی آورده شده است. 2-1 مقدمهدر این فصل ابتدا الگوریتم ژنتیک را مورد بررسی قرار میدهیم. در این بررسی ساختار کلی الگوریتم ژنتیک و پارامترهای تاثیرگذار در عملکرد این الگوریتم را مشخص میکنیم. در ادامه محیط شبکههای محاسباتی گرید را شرح داده و به بررسی اصطلاحات و تعاریف موجود میپردازیم. روشهای مختلف زمانبندی را بیان کرده و انواع صفبندی کارها را مورد بررسی قرار میدهیم.الگوريتم ژنتيك، الهامي از علم ژنتيك و نظرية تكامل داروين است و بر اساس بقاي برترينها يا انتخاب طبيعي استوار است. يك كاربرد متداول الگوريتم ژنتيك، استفاده از آن بعنوان تابع بهينهكننده است. الگوريتم ژنتيك ابزار سودمندي دربازشناسي الگو،انتخاب ويژگي،درك تصويرو يادگيري ماشيني است[3-8]. در الگوريتم ژنتيك[5]، نحوه تكامل ژنتيكي موجودات زنده شبيهسازي مي‌شود.اگرچه كارهايي توسط يك زيستشناس به نام Fraserدر زمينه مدلسازي تكامل در سيستم‌هاي بيولوژيك در دهه 60 ميلادي صورت گرفت ولي الگوريتم ژنتيك براي كاربردهاي مهندسي و به صورت امروزي آن، نخستين بار توسط جان هلند[9] متخصص علوم كامپيوتر دانشگاه ميشيگان در سال 1975 پيشنهاد گرديد. كار وي آغاز تمامي كوششها براي كاربرد الگوريتم ژنتيك در مهندسي است. پس از آن كارهاي Dejong [10]در سال 1975 در زمينه بررسي و مقايسه چندين روش الگوريتم ژنتيك پايه‌هاي نظري بحث را فراهم آورد. اين الگوريتم با الهام از طبيعت بر پايه اصل تكاملي «پايداري بهترين‌ها»[6] استوار است. الگوريتم ژنتيك اگرچه پس از الگوريتم استراتژي تكاملي پيشنهاد گرديد ولي مشهورترين روش از بين الگوريتم‌هاي تكاملي است.در يك الگوريتم ژنتيك يك جمعيت از افراد طبق مطلوبيت آنها در محيط بقا مييابند. افرادي با قابليتهاي برتر، شانس ازدواج وتوليد مثل بيشتري را خواهند يافت. بنابراين بعد از چند نسل فرزنداني با كارايي بهتر بوجود مي‌آيند. در الگوريتم ژنتيك هر فرد از جمعيت بصورت يك كروموزوم معرفي مي‌شود. كروموزومها در طول چندين نسل كاملتر مي‌شوند. در هر نسل كروموزومها ارزيابي مي‌شوند و متناسب با ارزش خود امكان بقا و تكثيرمي‌يابند. توليد نسل در بحث الگوريتم ژنتيك با عملگرهاي آمیزش3 و جهش4 صورت ميگيرد. والدين برتر بر اساس يك تابع برازندگي انتخاب مي‌شوند.در هر مرحله از اجراي الگوريتم ژنتيك، يك دسته از نقاط فضاي جستجو مورد پردازشهاي تصادفي قرار ميگيرند. به اين صورت كه به هر نقطه دنبالهاي از كاراكترها نسبت داده مي‌شود و بر روي اين دنبالهها، عملگرهاي ژنتيكي اعمال مي‌شوند. سپس دنبالههاي بدست آمده رمزگشایی ميگردد تا نقاط جديدي در فضاي جستجو بدست آيد. در آخر براساس اين كه تابع هدف در هر يك از نقاط چه مقدار باشد، احتمال شركت نمودن آنها در مرحله بعد تعيين ميگردد[11-14].الگوريتم ژنتيك را مي‌توان يك روش بهينه‌سازي تصادفي جهتدار دانست كه به تدريج به سمت نقطه بهينه حركت ميكند. در مورد ويژگي‌هاي الگوريتم ژنتيك در مقايسه با ديگر روش‌هاي بهينه سازي مي‌توان گفت كه الگوريتمي است كه بدون داشتن هيچ گونه اطلاعي از مسئله و هيچ گونه محدوديتي بر نوع متغيرهاي آن براي هر گونه مسئله اي قابل اعمال است و داراي كارآيي اثبات شده‌اي در يافتن بهينه كلي[7] مي‌باشد. توانايي اين روش در حل مسائل پيچيده بهينه‌سازي است كه روش‌هاي كلاسيك يا قابل اعمال نيستند و يا دريافتن بهينه كلي قابل اطمينان نيستند[15]. 2-2 ساختار الگوريتم ژنتيكبه طور كلی، الگوريتم ژنتيك از اجزاء زير تشكيل مي‌شود:كروموزوم[8]در الگوريتم ژنتيك، هر كروموزوم نشان دهنده يك نقطه در فضاي جستجو و يك راهحل ممكن براي مسئله مورد نظر است. خود كروموزومها (راه حلها) از تعداد ثابتي ژن[9] (متغير) تشكيل مي‌شوند. براي نمايش كروموزومها، معمولاً از كدگذاريهاي دودويي (رشتههاي بيتي) استفاده مي‌شود.جمعيت[10]مجموعهاي از كروموزومها يك جمعيت را تشكيل ميدهند. با تاثير عملگرهاي ژنتيكي بر روي هر جمعيت، جمعيت جديدي با همان تعداد كروموزوم تشكيل مي‌شود.تابع برازندگي[11]به منظور حل هر مسئله با استفاده از الگوريتم‌هاي ژنتيكي، ابتدا بايد يك تابع برازندگي براي آن مسئله ابداع شود. براي هر كروموزوم، اين تابع عددي غير منفي را برميگرداند كه نشان دهنده شايستگي يا توانايي فردي آن كروموزوم است.عملگرهاي ژنتيكيدر الگوريتم ژنتيك، در طي مرحله توليد مثل[12] ازعملگرهاي ژنتيكي استفاده مي‌شود. با تاثير اين عملگرها بر روي يك جمعيت، نسل[13] بعدي آن جمعيت توليد مي‌شود. عملگرهاي انتخاب[14] , آميزش و جهش معمولاً بيشترين كاربرد را در الگوريتم‌هاي ژنتيكي دارند. 2-3 عملگرهاي ژنتيكيدر بخش قبلي اشاره شد كه در الگوريتم ژنتيك به منظور توليد مثل، معمولاً از عملگرهاي انتخاب، آميزش و جهش استفاده مي‌شود. در اين بخش، هر يك از عملگرهاي فوق به صورت جداگانه معرفي مي‌شود:عملگر انتخاباين عملگر از بين كروموزومهاي موجود در يك جمعيت، تعدادي كروموزوم را براي توليد مثل انتخاب ميكند. كروموزومهاي برازندهتر، شانس بيشتري دارند تا براي توليد مثل انتخاب شوند.عملگر آميزشعملگر آميزش بر روي يك زوج كروموزوم از نسل مولد عمل كرده و يك زوج كروموزوم جديد توليد ميكند. عملگرهاي آميزش متعددي از قبيل، آميزش تك نقطهاي[15]، آميزش دو نقطهاي[16]، آمیزش چرخشی[17] و ... وجود دارند که در ادامه چند مورد را بررسی میکنیم.