%34تخفیف

رشته مدیریت و زیر مجموعه ها

بهينه سازي زمان بندي وظايف در گريد با استفاده از الگوريتم هاي تركيبي ژنتيك, ازدحام ذرات و رقابت استعماري

تعداد 75صفحه در فایل word

كارشناسي ارشد « M.sc »

گرايش: نرم افزار

بهينه سازي زمان بندي وظايف در گريد با استفاده از الگوريتم هاي تركيبي

ژنتيك, ازدحام ذرات و رقابت استعماري

چکیده

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

کلمات کلیدی:

گریدهای محاسباتی، زمان‌بندی وظایف مستقل، الگوریتم‌های تکاملی، رقابت استعماری، الگوریتم ترکیبی

دسته: علوم انسانی, مدیریت برچسب: الگوریتم ترکیبی, الگوریتم‌های تکاملی, رقابت استعماری, زمان‌بندی وظایف مستقل, کلمات کلیدی: گریدهای محاسباتی

توضیحات

فهرست مطالب

عنوان صفحه

چکیده 1

1-1- مقدمه. 3

1-2- بیان مسئله. 4

1-2-1- هدف آرمانی.. 4

1-2-2- هدف کلی.. 4

1-2-3- اهداف ویژه تحقیق.. 4

1-3- روش انجام تحقیق.. 4

1-4- ساختار پایان‌نامه. 5

2-1 محاسبات گرید 7

2-2 اصول ساخت Grid. 7

قلمروهای مدیریتی چندگانه و استقلال آن‌ها: 7

2-3 انواع کاربردهای Grid. 10

2-4 محاسبات گرید و نیاز به زمان‌بندی.. 11

2-5 کارهای مرتبط.. 12

2-6 گردش‌کاری.. 15

2-7 زمان‌بندی گردش‌کاری.. 15

2-8 پارامترهای الگوریتم‌های زمان‌بندی.. 16

2-9 چند نمونه الگوریتم زمان‌بندی معروف در زمینه‌ی محاسبات گرید 17

2-9-1 الگوریتم Min-min با بار متعادل شده (LBMM) 17

2-9-2 الگوریتم توزیع زمان – هزینه (DCT ) 18

2-9-3 الگوریتم بهینه‌سازی ازدحام ذرات(pso) 19

2-9-4 الگوریتم زمان‌بندی منبع مجتمع و پویا (daris) 20

2-9-5 الگوریتم توافق زمان- هزینه (ctc) 21

2-9-5-1 الگوریتم ctc – mc 21

2-9-5-2 الگوریتم ctc – mt 22

2-9-6 بزرگ‌ترین تکه ابر، سریع‌ترین عنصر پردازشی(lcfp) 23

2-9-7 الگوریتم قیمت‌گذاری بر اساس فعالیت بهبودیافته(abc) 24

2-9-8 الگوریتم زندگی زنبورها ((bla. 25

2-9-9 چندین گردش کاری با چندین محدودیت(mqmw) qos 25

2-9-10 الگوریتم کاهش تعادل (bar) 27

2-9-11 الگوریتم زودترین زمان پایان ناهمگن (heft) 27

2-9-12 الگوریتم زمان‌بندی آگاه از منابع(RASA) 29

2-9-13 الگوریتم ژنتیک جلو رونده (LAGA) 30

3- 1 الگوریتم ژنتیک… 34

3-1-1 مقدمه. 34

3-1-2 تاریخچه. 34

3-1-3 تاریخچه بیولوژیکی.. 34

3-2 ساختار و اجزای الگوریتم ژنتیک… 34

3-2-1 کروموزوم 34

3-2-2 جمعیت.. 35

3-2-3 تابع برازندگی.. 35

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

3-3-1 عملگر انتخاب (Selection): 35

3-3-2 عملگر آمیزش (Crossover): 36

3-3-3 عملگر جهش (Mutation): 37

3-4 – روند کلی الگوریتم ژنتیک: 38

3-5 روند بهینه‌سازی و حل مسائل در الگوریتم ژنتیک: 38

3-6- شرط پایان الگوریتم 39

3-7 الگوریتم تجمع ذرات( Particle Swarm Optimization) 39

3-8 الگوریتم رقابت استعماری.. 41

3-9 حل مسئله زمان‌بندی با استفاده از الگوریتم ترکیبی.. 43

4-1 آماده‌سازی و مقدمات ارزیابی.. 54

4-2 نتایج آزمایش‌ها 55

5-1 نتیجه‌گیری.. 63

منابع و مراجع. 67

فهرست شکل‌ها

عنوان شماره صفحه

شکل 2- 1 ساختار لایه‌ای Grid. 9

شکل 2-2- فرایند فیلترکردن منبع. 13

شکل 2-3 نتایج‌شبیه‌سازی سیاست مدیریت‌ درست زمان‌بندی. 14

شکل2-4 اهداف زمان‌بندی گردش کاری. 16

شکل 2-5 مروری بر گردش کاری زمان ‌بند 26

شکل 3-1 نحوه ارزیابی شایستگی در چرخ رولت.. 36

شکل 3-2 یک نمونه تلفیق (آمیزش) 37

شکل 3-3 یک کروموزوم قبل و بعد از اعمال عملگر جهش.. 37

شکل 3-4 کد برنامه مجازی الگوریتم ژنتیک ساده و فلوچارت آن. 38

شکل 3-5 نحوه ارزیابی تابع شایستگی در چرخ رولت.. 39

شکل 3-6: شمای کلی الگوریتم رقابت استعماری. 42

شکل ‏3‑7: حرکت مستعمرات به سمت امپریالیست (سیاست جذب) 42

شکل 3-8 : شمای کلی رقابت استعماری. 43

شکل 3-9 مثالی از مسئله زمان‌بندی با 9 وظیفه و 3 منبع. 44

شکل 3-10 : وضعیت نهایی الگوریتم ICA و ترکیبی. 46

شکل 3-11 – تغییراتی که در حرکت مستعمره ها به سمت استعمارگرها ایجاد می شوند. 47

شکل 3-12 فرآیند تعویض امپریالیستها و کشورهای مستقل. 48

شکل 3-13: شمای کلی رقابت استعماری: امپراطوری‌های بزرگ‌تر، با احتمال بیشتری، مستعمرات امپراطوری‌های دیگر را تصاحب می‌کنند. 49

شکل 3-14: سقوط امپراطوری‌ ضعیف؛ امپراطوری شماره 4، به علت از دست دادن کلیه مستعمراتش، دیگر قدرتی برای رقابت ندارد و باید از میان بقیه امپراطوری‌ها حذف شود. 51

شکل 4-1 زمان برگشت برای الگوریتمهای مختلف.. 58

شکل 4-2 زمان برگشت برای حالت (10 و 200 و 50 ) و تکرارهای 100 و 200 و 300. 59

شکل 4-3 زمان اجرا برای حالت (10 و 200 و 50 ) و تکرارهای 100 و 200 و 300. 60

شکل 4-4 زمانهای اجرا برای 50 وظیفه با 300 تکرار. 60

شکل 4-5 زمان برگشت برای وظایف متنوع جمعیت 50 تا تکرار 100 بار و تعداد منابع 10 تا 61

فهرست جداول

عنوان شماره صفحه

جدول 3-1 تنظيم نرخ تحول. 47

جدول 4-1 تنظیمات ده منبع پردازشی نمونه 54

جدول 4-2 مقادیر تعیین شده برای الگوریتمها 54

جدول 4-3 ارزیابی مقادیر زمان برگشت.. 56

جدول 4-4 ارزیابی زمانهای اجرای الگوریتمها 57

امتیاز 0 از 5 از 0 دیدگاه

قیمت اصلی: 35,000 تومان بود.قیمت فعلی: 23,000 تومان.

تاریخ ایجاد دی 21, 1399
تاریخ بروزرسانی اسفند 13, 1401
فروش 0
دیدگاه 0

شرایط استفاده از محصول

تمام محصولات به ازای پرداخت پروژه تنها قابل استفاده می باشند. این بدین معنی است که برای استفاده از یک یا چند محصول ، لازم به خرید آن محصول است.

مزایای خرید این محصول:

دسترسی به فایل به صورت همیشگی
پشتیبانی رایگان
پشتیبانی 24 ساعته محصول
بازگشت وجه در صورت عدم رضایت مشتری

مشاهده قوانین سایت