…………………………………………………………………………………………….. 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] می­گویند.