پایان نامه زمان بندی کارهای بلادرنگ در محیط ابرهای محاسباتی با استفاده از الگوریتم رقابت استعماری
پایان نامه زمان بندی کارهای بلادرنگ در محیط ابرهای محاسباتی با استفاده از الگوریتم رقابت استعماری
فرمت فایل دانلودی: .docxفرمت فایل اصلی: docx
تعداد صفحات: 94
پایان نامه زمان بندی کارهای بلادرنگ در محیط ابرهای محاسباتی با استفاده از الگوریتم رقابت استعماری
نوع فایل: word (قابل ویرایش)
تعداد صفحات : 94 صفحه
چکیده
الگوریتم زمان بندی کار، که یک مسئله NP-کامل است، نقش کلیدی در سیستم ابرهای محاسباتی ایفا می کند. الگوریتم رقابت استعماری یکی از جدیدترین الگوریتم های بهینه سازی تکاملی است. همانگونه که از نام آن بر می آید، این الگوریتم بر مبنای مدل سازی فرایند اجتماعی- سیاسی پدیده استعمار بنا نهاده شده است.
در این تحقیق با استفاده از الگوریتم رقابت استعماری ، الگوریتمی برای زمان بندی کارهای بلادرنگ نرم در محیط ابرهای محاسباتی طراحی می گردد که بتواند برنامه را در کمترین زمان ممکن، پیش از مهلت تعیین شده و با استفاده از کمترین تعداد منابع اجرا نماید، به نحوی که زمان اجرای کار در مقایسه با زمان بندی کارهای بلادرنگ بر اساس الگوریتم ژنتیک و در شرایط مساوی کاهش پیدا نماید. الگوریتم پیشنهادی از سیستم های ناهمگن، که در آن منابع از ناهمگونی محاسباتی و ارتباطات برخوردار هستند استفاده می نماید. زمان بندی نیز از نوع متمرکز و پویا در نظر گرفته شده است، که در این نوع زمان بندی باید به کارهای از قبل پیش بینی شده و محیط سیستم و حالت فعلی سیستم جهت ساخت طرح زمان بندی توجه کرد.
پیاده سازی های الگوریتم پیشنهادی برای دو آزمایش ۲۰۰ خادمی و ۴۰۰ خادمی انجام گرفته است و کارها از تعداد ۱۶ تا ۴۰۹۶ به سیستم وارد گردیده است، نتایج بدست آمده با نتایج زمان بندی کارهای بلادرنگ بر اساس الگوریتم ژنتیک مقایسه گردیده است و بهینه بودن الگوریتم پیشنهاد شده را بر اساس زمان انجام کار، تعداد کارهای انجام نشده در مهلت تعیین شده و تعداد خادم های مورد استفاده نتیجه می گیریم.
در این تحقیق با استفاده از الگوریتم رقابت استعماری در زمان بندی کارهای بلادرنگ در محیط ابرهای محاسباتی، استفاده از منابع بهینه شده است، نسبت بین زمان اجرای مورد انتظار و زمان اجرایی کمتر شده است و مقدار بهینه برازندگی نیز بهتر شده است.
واژه های کلیدی
ابرهای محاسباتی، کارهای بلادرنگ، الگوریتم ژنتیک، الگوریتم رقابت استعماری
فهرست مطالب
فصل اول- کلیات تحقیق 1
۱-۱-مقدمه 2
۱-۱-۱ ابرهای محاسباتی 2
۱-۱-۲ الگوریتم رقابت استعماری 3
۱-۱-۳ زمان بندی کارها 3
۱-۲ اهمیت موضوع تحقیق 5
۱-۳ تعریف مسئله 6
۱-۴ اهداف تحقیق 6
۱-۵ محدوده تحقیق 6
۱-۶ ساختار کلی پایان نامه 6
فصل دوم- ادبیات و پیشینه ی تحقیق 7
۲-۱ مقدمه 8
۲-۲ ابرهای محاسباتی 8
۲-۲-۱ تعریف 9
۲-۲-۲ تاریخچه 9
۲-۲-۳ معماری ابرهای محاسباتی 10
۲-۲-۴ مدل های پیاده سازی ابرهای محاسباتی 11
۲-۲-۵ مجازی سازی 12
۲-۲-۶ مزایای ابرهای محاسباتی 12
۲-۲-۷ چالش های ابرهای محاسباتی 13
۲-۳ زمان بندی کارهای مستقل 14
۲-۳-۱ تعریف 15
۲-۳-۲ الگوریتم های زمان بندی در ابرهای محاسباتی 16
۲-۳-۲-۱ مروری بر الگوریتم های زمان بندی حداکثر تلاش 20
۲-۳-۲-۲ الگوریتم زمان بندی آگاه از منبع 20
۲-۳-۲-۳ قیمت گذاری بر اساس فعالیت بهبود یافته (ABC) 21
۲-۳-۲-۴ بهینه سازی ازدحام ذرات (PSO) 21
۲-۳-۲-۵ الگوریتم توافق زمان-هزینه (CTC) 21
۲-۳-۲-۶ چندین گردش کاری با چندین محدودیت QOS (MQMW) 22
۲-۳-۲-۷ الگوریتم زودترین زمان پایان ناهمگن (HEFT) 22
۲-۳-۳ الگوریتم های فوق ابتکاری 22
۲-۴ زمان بندی بلادرنگ 23
۲-۴-۱ برخی از الگوریتم های زمان بندی بلادرنگ 24
۲-۴-۱-۱الگوریتم نرخ یکنواخت 24
۲-۴-۱-۲ الگوریتم ابتدا زودترین مهلت(EDF) 24
۲-۴-۱-۳ الگوریتم کمترین لختی 24
۲-۴-۱-۴ زمان بندی دو سطحی 25
۲-۵ الگوریتم رقابت استعماری 25
۲-۵-۱ مراحل الگوریتم رقابت استعماری 25
۲-۵-۱-۱ شکل دهی امپراطوری‌های اولیه 27
۲-۵-۱-۲ مدل‌سازی سیاست جذب: حرکت مستعمره‌ها به سمت امپریالیست 29
۲-۵-۱-۳ جابجایی موقعیت مستعمره و امپریالیست 31
۲-۵-۱-۴ قدرت کل یک امپراطوری 32
۲-۵-۱-۵ سیاست رقابت استعماری 33
۲-۵-۱-۶ سقوط امپراطوری‌های ضعیف 35
۲-۵-۱-۷ همگرایی 36
۲-۵-۲ مزایای الگوریتم رقابت استعماری 38
۲-۶ تحقیقات انجام شده در زمان بندی ابرهای محاسباتی 40
۲-۷ جمع بندی و نتیجه گیری 42
فصل سوم- روش پیشنهادی 43
۳-۱ مقدمه 44
۳-۱-۱ بیان مساله 44
۳-۱-۲ پارامترهای زمان بندی 44
۳-۱-۲-۱ مدل زمان بندی 45
۳-۱-۲-۲ تطابق اولیه 45
۳-۱-۳ تابع هدف 47
۳-۱-۴ نحوه انجام عمل زمان بندی 47
۳-۱-۴-۱ مدل ماشین مجازی بلادرنگ نرم 47
۳-۱-۴-۲ مدل خادم 48
۳-۱-۴-۳ درخواست ماشین مجازی بلادرنگ 48
۳-۱-۴-۴ ساختار زمان بندی ابری بلادرنگ 48
۳-۱-۵ مراحل اجرای الگوریتم رقابت استعماری 50
۳-۱-۵-۱ شکل دهی امپراطوری های اولیه 50
۳-۱-۵-۲ سیاست جذب 51
۳-۱-۵-۳ انقلاب 51
۳-۱-۵-۴ سیاست رقابت استعماری 52
فصل چهارم- شبیه‌سازی و ارزیابی روش‌های پیشنهادی 54
۴-۱ مقدمه 55
۴-۲ شبیه ساز 55
۴-۲-۱ مزایای کلود سیم 55
۴-۲-۲ مدل سازی در کلود سیم 55
۴-۲-۲-۱ مدل سازی ابر 56
۴-۲-۲-۲ مدل کردن تخصیص ماشین های مجازی 56
۴-۲-۲-۳ مدل کردن بارهای کاری پویا 56
۴-۲-۳ جمع بندی شبیه ساز 56
۴-۳ ارزیابی 58
۴-۲-۱ آزمایش ۲۰۰ خادمی 59
۴-۲-۲ آزمایش ۴۰۰ خادمی 62
۴-۳ نتیجه گیری 65
فصل پنجم- جمع بندی و پیشنهادات 67
۵-۱ جمع بندی 68
۵-۱-۱ خلاصه کار انجام شده 68
۵-۱-۲ مزایا و معایب روش پیشنهادی 69
۵-۱-۲-۱ مزایای روش پیشنهادی 69
۵-۱-۲-۲ معایب روش پیشنهادی 69
۵-۳ نو آوری 69
۵-۴ پیشنهادات 70
فصل ششم- ضمیمه 71
۶-۱ مقدمه 72
۶-۲ شبیه سازی با استفاده از الگوریتم ژنتیک 72
۶-۲-۱ کد گذاری 72
۶-۲-۲ جمعیت اولیه 73
۶-۲-۳ تابع برازندگی (محاسبه هزینه) 73
۶-۲-۴ عملگر انتخاب 73
۶-۲-۵ عملگر تقاطع 73
۶-۲-۶ الگوریتم جهش 74
۶-۲-۷ الگوریتم خاتمه 74
۶-۳ نتیجه گیری 75
مراجع 76
Abstract 79
پرداخت با کلیه کارتهای عضو شتاب امکان پذیر است.