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] زمینه‌ای را فراهم آورده است که بتوان از منابع (کامپیوتری) سیستم‌های دیگر نیز استفاده نماییم. اغلب مسائل پیچیده علمی، مهندسی و تجارت احتیاج به میزان زیادی از منابع برای اجرا دارند، بهترین راه حل برای اینگونه مسائل استفاده از گرید می­باشد[1].

 

هدف شبکه­های محاسباتی (گرید) به اشتراک گذاشتن منابع کامپیوتری در نقاط مختلف جغرافیایی با مدیریت­های مختلف بین کاربران است. کاربران درخواست­های خود را پیوسته برای محیط گرید ارسال می­کنند و بخش مدیریت منابع[2] این کارها را به گره های محاسباتی[3] موجود در شبکه اختصاص می­دهد. به چگونگی تخصیص این درخواست­ها روی گره­های محاسباتی مختلف زمانبندی[4] می­گویند.