3-3-1- مدل BPCCP.. 70

3-3-2- مدل RPP-I 73

3-3-3- مدل RPP-II 75

3-3-4- مدل RPP-III 77

3-3-5- مدل MRPP.. 77

3-3-6- مدل HWRPP.. 78

3-3-7- مدل SWRPP.. 78

3-4- جمع بندی.. 79

فصل 4:مطالعه موردی و تحلیل نتایج 80

4-1- مقدمه. 81

4-2- روش حل.. 81

4-3- مطالعه موردی.. 82

4-4- تحلیل نتایج.. 86

فصل 5:جمع بندی و نتیجه گیری 87

5-1- نتیجه گیری.. 88

5-2- نوآوری های پژوهش…. 88

5-3- پیشنهادها برای تحقیقات آتی.. 88

منابع.. 90

پیوست…. 96

فهرست اشکال

شکل (1-1) چهار فاز چرخه ی مدیریت بحران.. 20

شکل (1-2) ساختار فضای بشردوستانه. 21

شکل (1-3) بازیگران درگیر در زنجیره تامین بشردوستانه. 24

شکل (1-4) تقسیم بندی اقلام امدادی.. 25

شکل (1-5) فعالت های امدادی اصلی.. 26

شکل (1-6) عملیات های زنجیره تامین امداد. 27

شکل (3-1) طرحی کلی از یک زنجیره تامین امداد. 67

شکل (3-2) یک عدد فازی ذوزنقه ای.. 71

فهرست جداول

جدول (1-1) پنج فاجعه با بیشترین تلفات انسانی در بازه بین سال های 1980 تا 2012. 18

جدول (1-2) بدترین بلایای اتفاق افتاده در ایران بر اساس تعداد تلفات… 33

جدول (1-3) تقسیم بندی بلایا به همراه مثال.. 34

جدول (2-1) مقایسه ویژگی های دو زنجیره تامین تجاری و امداد. 42

جدول (4-1) مقدار کالای جمع شده نوع m در نقطه تامین i 83

جدول (4-2) کل ظرفیت استفاده شده وسیله نقلیه از نقطه تامین به مرکز تویع امداد. 83

جدول (4-3) کل ظرفیت استفاده شده وسیله نقلیه از مرکز تویع امداد به نقطه آسیب دیده 83

جدول (4-4) مقدار کالای امدادی مورد نیاز نوع m در نقطه آسیب دیده 83

جدول (4-5) هزینه انتقال هر واحد کالا از نقطه تامین به مرکز تویع امداد. 84

جدول (4-6) هزینه انتقال هر واحد کالا از مرکز تویع امداد به نقطه آسیب دیده 84

جدول (4-7) نقاط کاندید برای احداث مراکز توزیع امداد. 85

جدول (4-8) عملکرد مدل های ارائه شده 85

 

 

فصل اول

بیان مسئله و کلیات تحقیق

 

1-1-تعاریف کلی از حوزه تحت بررسی

• بلایا و انواع آن

نویسندگان مختلف تعاریف متفاوتی از بلا ارائه کردند . در این قسمت به برخی از این تعاریف اشاره خواهیم کرد.

اصطلاح “بلا” معمولا برای خرابی در عملیات های عادی یک جامعه که اثرات منفی قابل توجهی بر روی افراد، کارهای آنها، محیط آنها دارد و نیازهای به وجود آمده از ظرفیت پاسخ محلی تجاوز می کنند، به کار برده می شود]1[.

مرکز تحقیقات اپیدمولوژی بلایا، بلا را به عنوان یک وضعیت یا حادثه ای که از ظرفیت محلی تجاوز کرده، و نیازمند درخواست کمک در سطح ملی یا بین المللی می باشد. یک حادثه غیر قابل پیش بینی یا ناگهانی که منجر به خسارات و صدمات زیاد و درد و رنج انسان ها می شود، تعریف می کند]1[.

سازمان بهداشت جهانی هر حادثه ای که منجر به صدمه، خسارت، ویرانی، اختلال زیست محیطی، مرگ و میر انسان ها، زوال بهداشت عمومی و خدمات بهداشتی شود و نیاز به پاسخ و کمک سریع از خارج از جامعه یا منطقه ی آسیب دیده داشته باشد را به عنوان فاجعه (بلا یا مصیبت) تعریف می کند. زلزله، طوفان، گردباد، خشکسالی، سیل، نشت مواد شیمیایی، حوادث هسته ای و … جزء بلایا دسته بندی می شوند و همگی اثرات ویرانگر زیادی از نظر صدمات مالی و جانی دارند]2[.

یک تعریف کلی برای بلایا که توسط استراتژی بین المللی برای کاهش بلایا ارائه شده است، عبارت است از: یک اختلال جدی در عملکرد جامعه، همراه با تهدید برای زندگی انسان ها، سلامتی، دارایی یا محیط زیست افراد، چه در اثر حادثه، چه طبیعی و چه فعالیت های انسانی ایجاد شود. یکی دیگر از تعاریف گسترده برای بلایا عبارت است از: یک اختلال که بر روی سیستم ها اثرات فیزیکی دارد و همه یا قسمتی از اولویت ها و اهداف را تهدید می کند. تا زمانی که سیستم، یا ملت توانایی مقابله با اثرات این حوادث را داشته باشند، این حادثه به یک بلایای بزرگ تبدیل نمی شود. فاجعه باید شرایط اعلام شده برای وضعیت های اضطراری و نیاز به کمک های بین المللی را داشته باشد]3[. فورمن و همکارانش معتقد هستند که بلایا به طور غیر منتظره رخ می دهند و به حادثه ای گفته می شود که منجر به نتایج با مقیاس بزرگ می شود و اثرات خیلی زیادی در پی دارد]4[.

اوزگون]5[ ویژگی های زیر را برای بلایا بیان می کند:

1. بلایا حوادثی سریع و بزرگ هستند.

1. بلایا چه از نظر وقوع و چه از نظر پیامدها همراه با عدم قطعیت هستند.

1. محیط بلایا (از نظر نوع و مقدار نیازها، منابع موجود، دسترسی به زیرساخت ها و …) یک محیط پویا است.

1. بلایا حوادث غیر عادی هستند که می توانند به احتمال کم اتفاق بیافتند یا اصلا اتفاق نیافتند.

طبقه بندی های متفاوتی برای بلایا وجود دارند. انواع مختلفی از بلایا را می توان بر اساس طبیعی یا انسان ساز بودن و زمان وقوع آن که سریع یا آهسته اتفاق می افتد شناسایی کرد.

در جدول (1-1) تقسیم بندی رایج بلایا به همراه مثال آورده شده است]3[.

جدول (1-1) تقسیم بندی بلایا به همراه مثال ]3[

	طبیعی	انسانی
هجوم ناگهانی	زلزله	حمله تروریستی
	طوفان	کودتا
	سیل	نشت شیمیایی
هجوم آهسته	قحطی	بحران سیاسی
	خشکسالی	بحران پناهندگان
	فقر	و…

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

• مدیریت بحران را می توان در دو گروه عمده دسته بندی کرد:

ابتدا گروه مدیریتی (کیفی) که بیشتر مربوط به محافظت، جلوگیری یا کاهش اثرات بحران، سازگار شدن با بحران از طریق تغییر سیستم های مورد استفاده بشری می شود و در دسته بندی نوع دوم راهکارهای لجستیکی (کمی) که بیشتر به طراحی شبکه و انواع مدل سازی های ممکن ریاضی با توجه به محدودیت ها و اهداف موجود همچون پاسخگویی به حداقل سطح معینی از تقاضا یا کنترل هزینه ها و پیشگیری تجاوز آنها از حدود تعیین شده مربوط می شود.

• مدیریت بحران و فازهای آن

مدیریت بحران یا مدیریت بلایا یا مدیریت اضطرار رشته ی اجتناب از ریسک و برخورد با ریسک است. هیچ کشور و هیچ جامعه ای از خطر و ریسک بلایا در امان نیست. بنابراین نیازمند به آمادگی، پاسخ و بازیابی در زمان وقوع بلایا می باشد. مدیریت بحران رشته ای است که شامل آماده سازی برای بلایا قبل از وقوع آن، پاسخ دهی بلافاصله بعد از وقوع و همچنین حمایت و بازسازی جامعه بعد از وقوع بلایای طبیعی یا ساخته ی بشر می باشد بدین منظور مدیریت بحران یا بلایا یا اضطرار یک فرایند پیوسته است از این رو داشتن طرح های اضطراری جامع و به طور پیوسته ارزیابی کردن و بهبود دادن طرح ها ضروری است]1[.

کاوی……………………………………………………………………………………………………50

2-5-2- خوشه بندی………………………………………………………………………………………………………………51

2-5-2-1- روش های خوشه بندی…………………………………………………………………………………………..52

3-1-مقدمه……………………………………………………………………………………………………………………………56

3-2-مدیریت ارتباط با مشتری(CRM)……………………………………………………………………………………..57

3-2-1-خوشه بندی در مدیریت ارتباط با مشتری………………………………………………………………………60

3-3-نظرسنجی از مشتریان………………….. …………………………………………………………………………………61

3-3-1-خواسته ها و نیازمندی های مشتریان………………… …………………………………………………………61

3-3-1-1-نیازمندی های مشتریان………………………………………… …………………………………………………61

3-3-1-2-خواسته های مشتری………………………………………………………………………………………………..63

3-3-2-روش نمونه گیری STRATA ………………………………………………………………………………………66

3-4-داده کاوی ……………………………………………………………………………………………………………………..66

3-4-1- شرح الگوریتم K-means ……………………………………………………………………………………………68

3-4-1-1- مشکلات روش خوشه بندی K-Means………………………………………………………………………69

3-5-مدلسازی ریاضی…………………………………………. ………………………………………………………………..70

3-5-1-تعریف علایم و پارامترها…………………………….. ……………………………………………………………..70

3-5-1-1-تعریف علائم……………………………………………….. ………………………………………………………70

3-5-1-2-تعریف پارامترها…………………………………………………………….. ……………………………………..71

3-5-1-3-تعریف متغیر های تصمیم……………………………………… ……………………………………………….72

3-5-2-مدل ریاضیپیشنهادی……………………………………………………. …………………………………………..72

3-5-2-1-خطی سازی تابع هدف…………………………………………………………………………………………….76

3-5-2-2- استفاده از AHP برای تابع دو هدفه(پیگیری نظرات)…………………… …………………………….77

3-5-2-2-1-روش فرآیند تحلیل سلسله مراتبی(AHP)…………………………….. ……………………………….77

3-5-2-2-1-1-تشکیل سلسله مراتب………………………………………………….. …………………………………78

3-5-2-2-1-2- الویت بندی………………………………………………….. ……………………………………………. 78

3-5-2-2-1-3-علایم ریاضی و تعاریف آنها…………………………………… ………………………………………79

3-5-2-2-1-4- الگوریتم 1: PWAHP (محاسبه وزن اهداف به کمک AHP)…………… …………………79

3-5-2-2-2- حل مسئله دو هدفه پیگیری نظرات……………………………………. ……………………………….83

3-6-جمع بندی……………………………………………………………………………………………………………………..84

4-1-مقدمه……………………………………………………………………………………………………………………………87

4-2-نظر سنجی از مشتریان به چندین روش…………………………………… ……………………………………….87

4-3-نمونه گیری به روش STRATA……………………………………………………….. ……………………………..87

4-4-میانگین وزنی عوامل………………………………………………………… ……………………………………………88

4-5-الگوریتم k-means…………………………………………………………………………. ………………………………89

4-5-1-نتیجه الگوریتم k-means …………………………………………………………… ………………………………91

4-6-مدل ریاضی………………………………………………………………….. ……………………………………………..93

4-6-1-محاسبه و تعیین پارامترهای مدل ریاضی………………………………….. ………………………………….93

4-6-2-جواب مدل ریاضی……………………………………………………………………………………………………..95

4-7-جمع بندی……………………………………………………………………………………………………………………..96

1-5 -نتیجه گیری …………………………………………………………………………… ……………………………………98

-2-5 پیشنهادها …………………………………………………………………….. …………………………………………….98

مراجع ……………………………………………………………………………………………………………………………….. 100

فهرستجداول

جدول 1-1: گرایشات مهم لجستیک در طول زمان………………….. ………………………………………………..20

جدول 3-1: پرسشنامه…………………………………………………………………………………………………………….65

جدول 3-2: مقیاس اهمیت نسبی…………………………………………………………. ………………………………….78

جدول 3-3: ماتریس هدف – معیار……………………………………….. ……. …………………………………………82

جدول 3-4: ماتریس مقایسه دوتایی معیار- معیار………………………………….. …………………………………..82

جدول 3-5: ماتریس هدف- معیار………………………………………………… …………………………………………83

جدول 3-6: ماتریس معیار- معیار……………………………………………… ………………………………………….84

 

 

فهرستشکلها

شکل -11: نمونه ای از یک زنجیره ی تامین……………………………………………………………………………….16 شکل 1-2:مقایسه زنجیره تامین رو به جلو و معکوس………………………………. ……………………………….17

شکل 1-3:تفاوت چهارچوب لجستیک یکپارچه و قدیمی………………………. …………………………………..22

شکل 2-1:جریان کالا در لجستیک مستقیم و معکوس…………………………… …………………………………….29

 

فصلاول:

کلیاتتحقیق

لجستیک……………………………………………………………………………………..18

2-5-3- مدیریت روابط…………………………………………………………………………………………18

2-6- فرایندهای زنجیره تأمین………………………………………………………………………………………..19

2-6-1- دیدگاه سیکلی………………………………………………………………………………………….19

2-6-2- دیدگاه فشاری – کششی……………………………………………………………………………20

2-7- انواع زنجیره تأمین………………………………………………………………………………………………..20

2-8- عوامل مؤثر در پیاده سازی زنجیره تأمین رقابتی……………………………………………………….22

2-8-1- خرید………………………………………………………………………………………………………22

2-8-2- انتخاب تأمین کننده…………………………………………………………………………………..22

2-8-3- انعطاف پذیری در تغییر زنجیره تأمین………………………………………………………….23

2-8-4- توزیع……………………………………………………………………………………………………..23

2-9- چالش های زنجیره تأمین………………………………………………………………………………………24

2-10- مسئله طراحی شبکه زنجیره تأمین………………………………………………………………………..29

2-11- بر الگوریتم ژنتیک…………………………………………………………………………………..31

2-11-1- مقدمه……………………………………………………………………………………………………31

2-11-2- مکانیسم الگوریتم ژنتیک…………………………………………………………………………32

2-11-3- عملگرهای الگوریتم ژنتیک……………………………………………………………………..35

2-11-4- کد کردن……………………………………………………………………………………………….38

2-11-5- ایجاد جمعیت اولیه…………………………………………………………………………………40

2-11-6- تابع برازندگی…………………………………………………………………………………………42

2-11-7- انتخاب………………………………………………………………………………………………….42

2-11-8- ترکیب…………………………………………………………………………………………………..47

2-11-9- احتمال ترکیب……………………………………………………………………………………….50

2-11-10- جهش…………………………………………………………………………………………………50

2-11-11- استراتژی برخورد با محدودیت ها…………………………………………………………..51

2-11-12- شرایط توقف الگوریتم………………………………………………………………………….53

3- بیان مسئله و ارائهمدل ریاضیآن………………………………………………………….54

3-1- شبکه زنجیره تأمین چند مرحله ای…………………………………………………………………………55

3-2- تقاضای فازی………………………………………………………………………………………………………57

3-3- ارائه مدل ریاضی مسئله…………………………………………………………………………………………61

3-3-1- اندیس های مدل………………………………………………………………………………………62

3-3-2- پارامترهای مدل………………………………………………………………………………………..62

3-3-3- متغیرهای مدل………………………………………………………………………………………….63

3-3-4- تابع هدف………………………………………………………………………………………………..63

3-3-5- محدودیت های مدل…………………………………………………………………………………66

4- روش حل و نتایج محاسباتی………………………………………………………………….68

4-1- مقدمه…………………………………………………………………………………………………………………69

4-2- روش کدگذاری اولویت محور……………………………………………………………………………….70

4-3- ارزیابی، انتخاب و مکانیسم جایگزینی…………………………………………………………………….82

4-4- عملگرهای ژنتیک………………………………………………………………………………………………..83

4-4-1- عملگر ترکیب……………………………………………………………………………………………83

4-4-2- عملگر جهش…………………………………………………………………………………………….83

4-5- حل مسائل و کارایی الگوریتم………………………………………………………………………………..85

5- نتیجه گیری و پیشنهادات……………………………………………………………………..91

5-1- بر مسئله و نتیجه گیری………………………………………………………………………………92

5-2- پیشنهادهایی برای تحقیقات آینده……………………………………………………………………………94

منابع و مآخذ………………………………………………………………………………………….95

فهرست جداول

جدول 4-1- نتایج حاصل با تابع هدف OB1 …………………………………………………………………..88

جدول 4-2- نتایج حاصل با تابع هدف OB2 …………………………………………………………………..88

جدول 4-3- نتایج حاصل با حداقل درجه تأمین 40% و تابع هدف OB1 ……………………………89

جدول 4-4- نتایج حاصل با حداقل درجه تأمین 40% و تابع هدف OB2 ……………………………89

فهرست تصاویر و نمودارها

شکل 1-1- نمایی از یک شبکه زنجیره تأمین……………………………………………………………………..4

شکل 1-2- شبکه زنجیره تأمین سه مرحله ای تک محصوله…………………………………………………6

شکل 2-1- شبکه زنجیره تأمین سه مرحله ای تک محصوله……………………………………………….30

شکل 2-2- دیاگرام بلوکی الگوریتم ژنتیک ساده……………………………………………………………….38

شکل 2-3- چرخ رولت…………………………………………………………………………………………………45

شکل 2-4- عملگر ترکیب تک نقطه ای…………………………………………………………………………..48

شکل 2-5- عملگر ترکیب دو نقطه ای…………………………………………………………………………….48

شکل 2-6- عملگر جهش وارونه سازی بیت……………………………………………………………………51

شکل 2-7- عملگر جهش تغییر ترتیب…………………………………………………………………………….51

شکل 3-1- تقاضای فازی ………………………………………………………………………………………….59

شکل 3-2- درجه تأمین تقاضای مشتری………………………………………………………………………….60

 

فصل اول

مقدمه و کلیات تحقیق

 

1-1- مقدمه

مسئله زنجیره تأمین در دنیای امروز به عنوان یک مزیت رقابتی عمده در راستای کاهش قیمت تمام شده مطرح است. زنجیره تأمین شامل خرید و تأمین، لجستیک و حمل و نقل، بازاریابی، رفتار سازمانی،شبکه،مدیریت استراتژیک، مدیریت سیستم های اطلاعاتی و مدیریت عملیات می باشد[10]. با وجود این مطلب، تصمیم گیری در مراحل مختلف این روند و هماهنگی این مراحل، مسئله اصلی در زنجیره تأمین می باشد. با توجه به رقابت شدیدی که بین تولید کنندگان وجود دارد، در صورتی که هر کدام از حلقه های این زنجیره ضعیف عمل کند، کل مجموعه موفق نخواهد بود و در سطح مورد انتظار عمل نخواهد کرد. بنابراین مدیریت مؤثر این زنجیره در صنعت، یک چالش مدیریتی عمده به حساب می آید. در سال های اخیر، شرکت ها و سازمان های کشورهای صنعتی و پیشرفته جهان، توجه ویژه ای به مدیریت زنجیره تأمین داشته اند و از این رهگذر به موفقیت های قابل توجهی نیز دست یافته اند که گواه این امر، حجم بالایی از مبادلات تجاری انجام شده و درآمد و سود آوری بالای زنجیره تأمین موفق و کارآمد است که در بازارهای به شدت رقابتی امروز، موفق به پیشی گرفتن از رقبا شده اند[11].

1-2- ضرورت انجام طرح

پیچیدگی کالاها و خدمات در دنیای امروز باعث شده است که شرکت هایی که به تنهایی و بدون کمک گرفتن و همکاری با دیگر سازمان ها، محصولی را عرضه می کنند، برای بقای خویش با مشکلات بسیاری روبرو شوند. به همین منظور سازمان ها دریافته اند که اگر با یکدیگر همکاری داشته باشند، مجموع منافعی که عاید آنها می شود بیش از وضعیتی است که هر یک فعالیت خود را بدون هماهنگی با سازمان های مرتبط انجام می دهند. به همین دلیل امروزه هر دو طرف خریدار و فروشنده بر اساس روابط بلند مدت و کسب سود با یکدیگر همکاری می کنند. در سال های اخیر به دلایل زیر توجه زیادی به مقوله زنجیره تأمین شده است :

• نیاز برای فعالیت های بهبود

• افزایش سطح برون سپاری

3-2. مدل پیشنهادی CMVRP. 37

3-2-1. فرض­های مدل. 37

3-2-2. خصوصیت مدل ارائه شده 38

3-2-3. تعریف علائم و پارامترها 39

3-2-4. مدل ریاضی CMVRP. 41

3-3. روش حل مدل پیشنهادی.. 43

3-4. الگوریتم ژنتیک (GA) 43

3-4-1. تعریف… 43

3-4-2. گذری بر ژنتیک طبیعی.. 45

3-4-3. واژگان الگوریتم ژنتیك… 51

3-4-4. ساختار كلی الگوریتم ژنتیك… 52

3-4-5. مفاهیم کلیدی الگوریتم ژنتیک… 54

3-4-6. كدینگ… 55

3-4-7. ایجاد جمعیت اولیه. 57

3-4-8. اعمال ژنتیك… 58

3-4-9. تابع برازش… 63

3-4-10. روش اجرای الگوریتم ژنتیک… 64

3-4-11. استراتژی برخورد با محدودیتها 66

3-4-12. انواع عملگرهای تقاطعی.. 69

3-4-13. انواع عملگرهای جهشی.. 73

3-5. ساختار پیشنهادی الگوریتم ژنتیک… 76

3-5-1. نحوه نمایش جواب ها 76

3-5-2. نحوه شدنی کردن جواب ها 78

3-5-3. تعریف میزان برازندگی.. 80

3-5-4. مکانیزم نمونه گیری.. 81

3-5-5. عملگر تقاطعی.. 81

3-5-6. عملگر جهشی.. 82

3-6. جمع­بندی.. 84

فصل چهارم تحلیل و نتایج محاسباتی.. 85

4-1. مقدمه. 86

4-2. تولید مسائل نمونه. 86

4-3. تنظیم پارامتر. 87

4-3-1. تنظیم پارامترهای الگوریتم ژننیک… 88

4-4. نتایج محاسباتی.. 93

4-5. صحه­گذاری مدل ارائه شده 97

4-6. جمع­بندی.. 100

فصل پنجم نتیجه­گیری و ارائه پیشنهادها……………………………………………………………………………………………101

5-1. نتیجه­گیری.. 102

5-2. پیشنهادها 103

مراجع. 104

لیست جداول

جدول 3-1. مقایسه الگوریتم ژنتیک با فرآیند تکامل طبیعی 49

جدول 4-1. سطوح فاکتورهای مسئله 87

جدول 4-2. فاکتورهای الگوریتم ژنتیک به همراه سطوحشان 89

جدول 4-3. آرایه متعامد 90

جدول 4-4. نتایج محاسباتی برای مسائل کوچک 94

جدول 4-5. نتایج محاسباتی برای مسائل بزرگ 95

جدول 4-6. اطلاعات مساله نمونه تولید شده 97

جدول 4-7. بهترین حل ریاضی دستی 98

لیست شکل­ها

شکل 2-1. نمایی از مسأله TSP 9

شکل 2-2. نمایی ساده از MTSP 10

شکل 2-3. نمایی ساده از VRP 11

شکل 2-4. نسخه های مختلف VRP کلاسیک و ارتباط بین آنها 22

شکل 2-5. مشکل عدم همبندی (زیرتور)28

شکل 3-1. مدل تئوری داروین 47

شکل 3-2. فضای کدینگ و فضای جواب 56

شکل 3-3. قانونمندی و موجه بودن 57

شکل 3-4. فضای جواب: ناحیه موجه و ناحیه غیرموجه 68

شکل 3-5. نمایش ماتریسی مسیرهای ایجاد شده 77

شکل 3-6. نمایش گرافیکی مسیرهای ایجاد شده 77

شکل 3-7. ماتریس اولیه نمایش دهنده جواب 78

شکل 3-8. ماتریس اصلاحی محدودیت تیم ها 79

شکل 3-9. ماتریس نمایش دهنده جواب 79

شکل 3-10. ماتریس اصلاحی مسیرها 80

شکل 3-11. ماتریس نمایش دهنده والدین 81

شکل 3-12. نمایش عملگر تقاطع 82

شکل 3-13. نمایش ماتریس اولیه انتخابی برای عملیات جهش 83

شکل 3-14. نمایش ماتریس در قدم دوم83

شکل 3-15. نمایش مسیر انتخابی 83

شکل 3-16. نمایش عملگر جهش 84

شکل 4-1. نمودار نرخS/Nتوابع هدف در سطوح مختلف عامل ها 91

شکل 4-2. نمودار نرخ تاثیرات میانگین داده ها بر میانگین ها،در سطوح مختلف عامل ها 92

شکل 4-3. نمودار حرکت الگوریتم ژنتیک پیشنهادی93

شکل 4-4. نمایش مقادیر تابع هدف هر دو روش 96

شکل 4-5. نمایش زمان محاسباتی حاصل از هر دو روش 96

شکل 4-6. نمایش نحوه محاسبه تابع هدف 99

شکل 4-7. نمایش کروموزم بهینه مساله نمونه 99

فصل اول کلیات تحقیق

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