شکل ۲-۳ نتایج‌شبیه‌سازی سیاست مدیریت‌ درست زمان‌بندی ۱۴
شکل۲-۴ اهداف زمان‌بندی گردش کاری ۱۶
شکل ۲-۵ مروری بر گردش کاری زمان ‌بند ۲۶
شکل ۳-۱ نحوه ارزیابی شایستگی در چرخ رولت ۳۶
شکل ۳-۲ یک نمونه تلفیق (آمیزش) ۳۷
یک کروموزوم قبل و بعد از اعمال عملگر جهش ۳۷
شکل ۳-۴ کد برنامه مجازی الگوریتم ژنتیک ساده و فلوچارت آن ۳۸
شکل ۳-۵ نحوه ارزیابی تابع شایستگی در چرخ رولت ۳۹
شکل ۳-۶: شمای کلی الگوریتم رقابت استعماری ۴۲
شکل ‏۳‑۷: حرکت مستعمرات به سمت امپریالیست (سیاست جذب) ۴۲
شکل ۳-۸ : شمای کلی رقابت استعماری ۴۳
شکل ۳-۹ مثالی از مسئله زمان‌بندی با ۹ وظیفه و ۳ منبع ۴۴
شکل ۳-۱۰ : وضعیت نهایی الگوریتم ICA و ترکیبی ۴۶
شکل ۳-۱۱ – تغییراتی که در حرکت مستعمره ها به سمت استعمارگرها ایجاد می شوند. ۴۷
شکل ۳-۱۲ فرایند تعویض امپریالیستها و کشورهای مستقل ۴۸
شکل ۳-۱۳: شمای کلی رقابت استعماری: امپراطوری‌های بزرگ‌تر، با احتمال بیشتری، مستعمرات امپراطوری‌های دیگر را تصاحب می‌کنند. ۴۹
شکل ۳-۱۴: سقوط امپراطوری‌ ضعیف؛ امپراطوری شماره ۴، به علت از دست دادن کلیه مستعمراتش، دیگر قدرتی برای رقابت ندارد و باید از میان بقیه امپراطوری‌ها حذف شود. ۵۱

شکل ۴-۱ زمان برگشت برای الگوریتمهای مختلف ۵۸
شکل ۴-۲ زمان برگشت برای حالت (۱۰ و ۲۰۰ و ۵۰ ) و تکرارهای ۱۰۰ و ۲۰۰ و ۳۰۰ ۵۹
شکل ۴-۳ زمان اجرا برای حالت (۱۰ و ۲۰۰ و ۵۰ ) و تکرارهای ۱۰۰ و ۲۰۰ و ۳۰۰ ۶۰
شکل ۴-۴ زمان های اجرا برای ۵۰ وظیفه با ۳۰۰ تکرار ۶۰
شکل ۴-۵ زمان برگشت برای وظایف متنوع جمعیت ۵۰ تا تکرار ۱۰۰ بار و تعداد منابع ۱۰ تا ۶۱
فهرست جداول
عنوان شماره صفحه
جدول ۳-۱ تنظیم نرخ تحول ۴۷
جدول ۴-۱ تنظیمات ده منبع پردازشی نمونه ۵۴
جدول ۴-۲ مقادیر تعیین شده برای الگوریتمها ۵۴
جدول ۴-۳ ارزیابی مقادیر زمان برگشت ۵۶
جدول ۴-۴ ارزیابی زمان های اجرای الگوریتمها ۵۷
چکیده
گرید محاسباتی به معنای همکاری منابع توزیع‌شده جغرافیایی در حل مسائل بزرگ می‌باشد. زمان‌بندی در گرید محاسباتی برای انواع سیستم‌هایی که به عنوان سیستم‌های دفاعی و امنیتی هستند و موبایل و سیستم‌های آزمایشگاهی پزشکی که متمرکز نیستند، از اهمیت بالایی برخوردار است. از الگوریتم‌های قطعی برای بالا بردن کیفیت زمان‌بندی نمی‌توان استفاده کرد زیرا زمان‌بندی در گرید محاسباتی یک مسئله غیرقطعی است. الگوریتم ژنتیک، رقابت استعماری، ازدحام ذرات، تپه نوردی از روش‌های غیرقطعی در بهبود زمان‌بندی در گرید می‌باشند. در این تحقیق با مقایسه کردن و بررسی الگوریتم‌های ذکرشده مزایا و معایب آن‌ها اقدام به ادغام و ترکیب نقاط قوت این الگوریتم‌ها بر پایه الگوریتم رقابت استعماری استفاده نموده‌ایم. زمان‌بندی وظایف مسئله‌ای مستقل است که شامل n وظیفه و m ماشین می‌باشد و هر وظیفه باید با هر یک از ماشین‌ها مورد پردازش قرار بگیرد طوری که زمان انجام کار کمینه شود. الگوریتم رقابت استعماری پایه برای مقادیر حقیقی و فضاهای پیوسته تعریف‌شده است درصورتی‌که زمان‌بندی وظایف گسسته باشد، بدین منظور الگوریتم رقابت استعماری را با الگوریتم‌های ژنتیک و ازدحام ذرات، ترکیب نموده‌ایم و به حالت فضای گسسته مبدل کردیم.الگوریتم ترکیبی را با افزودن گروهی به نام کشورهای مستقل بررسی کردیم. علی‌رغم ایده اصلی الگوریتم رقابت استعماری که مبتنی بر استعمارگر و کلونی (مستعمره) است، یک گروه از کشورهای بی‌طرف و صلح‌آمیز در اینجا در نظر گرفته‌شده‌اند. این کشورها متحده هستند و با بهره گرفتن از هوش ازدحامی با همدیگر ارتباط برقرار می‌کنند.
کلمات کلیدی:
گریدهای محاسباتی، زمان‌بندی وظایف مستقل، الگوریتم‌های تکاملی، رقابت استعماری، الگوریتم ترکیبی
فصل اول: کلیات تحقیق
در ابتدای این فصل انگیزه و هدف از این پایان‌نامه ارائه می‌شود، بعدازآن روش مورداستفاده در این پایان‌نامه، توضیح داده خواهد شد، سرانجام یک نمای کلی از ساختار پایان‌نامه ارائه خواهد شد.
مقدمه
محاسبات گرید در اکثر موارد به عنوان فناوری شناسایی پتانسیل عظیم در دانش صنعت معرفی و موردتوجه قرارگرفته است. الگوی سیر تکاملی در فناوری گرید، بسیار شبیه به رشد و تکامل فناوری‌های اینترنت که در اوایل ۱۹۰۰ رخ داد و همچنین مشابه با اینترنت فناوری‌های محاسبات گرید ابتدایی در دانشگاه‌ها و آزمایشگاه‌های تحقیقاتی توسعه‌یافته‌ای که مسائل تحقیقاتی منحصربه‌فرد را حل می‌کردند و امکان تشریک‌مساعی میان پژوهشگران مختلف را داشتند، می‌باشد. اخیراٌ صنایعی که محاسبات سطح بالا دارند به‌طور مثال: امور مالی، انرژی، خودروسازی و … علاقه شدیدی به توان ارتباط برقرار کردن خودکار، خوشه‌های درون یک سازمان و گرید تجاری نشان می‌دهند. اکنون محاسبات گرید در میان استنتاج کردن استانداردها، ارث‌بری از تکنولوژی‌های توسعه‌یافته در محاسبات با کارایی بالا، توزیع‌شده و اخیراً نیز از انجمن سرویس‌های وب می‌باشد. به علت عدم گستردگی و سازگاری استانداردهای استفاده‌شده، بسیاری از سازمان‌های تجاری درباره پیاده‌سازی یک سیستم گرید تجاری نگرانی‌هایی دارند، اگرچه توان این‌چنین سیستم‌هایی ثابت‌شده است. حتی زمانی که بعضی از سازمان‌های تجاری، گرید را به عنوان یک‌راه حل ممکن در نظر گرفتند، موضوعات و مسائل بسیاری آن‌ها را مجبور به تجدیدنظر نمود. موضوعاتی مربوط به مهندسی برنامه کاربردی، قابلیت اداره، مدیریت داده‌ها، مجوز دهی، امنیت، زمان‌بندی و … آن‌ها را از پیاده‌سازی یک‌راه حل گرید تجاری بازداشته‌اند. از دید علم فناوری، محاسبات گرید توانی فراتر از صنایع محاسباتی با کارایی بالا دارد و این امر به دلیل رفتار ذاتی همکاری کننده، مستقل و سرویس مبتنی بر سود می‌باشد. برای میسر شدن این سیر تکاملی، تمامی موضوعات مطرح‌شده در بالا، باید حل شوند.هرکدام از موضوعات مطرح‌شده در بالا مانند مبحث زمان‌بندی مهم هستند و باید به‌دقت موردبررسی قرار گیرند. در این تحقیق منحصراً بر روی مسائل مربوط به زمان‌بندی فرآیندها در گرید تمرکز خواهیم کرد.
در جهت افزایش کارایی گرید، در حل مسئله ما به یک زمان‌بندی کارآمد نیاز داریم. اگرچه طبیعت پویای منابع گرید و تقاضاهای مختلف کاربران، باعث پیچیدگی مسئله زمان‌بندی گریدهای محاسباتی شده است. پویایی کارایی منابع، ناشی از ناهمگونی، اشتراکی بودن و خودمختاری منابع گرید است. هدف ما در مسئله زمان‌بندی گرید، انتساب بهینه کارها به منابع است. تحقیق و بررسی در زمان‌بندی گرید ازاین‌جهت مهم است که سیستم‌های دنیای واقعی به‌طور فیزیکی یا عملیاتی، به‌صورت توزیع‌شده و ناهمگون می‌باشند. سیستم‌هایی مانند زیست‌شناسی، نجوم، پزشکی، کنترل ترافیک هوایی، نظامی و همچنین موبایل از این دسته هستند. با الهام گرفتن از یک سری از قوانین طبیعی برای بهبود زمان‌بندی در گرید پیشنهادشده است. ازجمله الگوریتم ژنتیک، رقابت استعماری و ازدحام ذرات می‌باشد. در این تحقیق با معرفی آن‌ها و بیان مزایا و معایب آن اقدام به ترکیب این سه الگوریتم نموده و الگوریتم حاصل را با داده‌های مختلف مورد آزمایش قراردادیم.
۱-۲- بیان مسئله
۱-۲-۱- هدف آرمانی
هدف آرمانی از انجام تحقیق حاضر رفع نسبی مشکلات زمان‌بندی فرآیندها در محیط گرید و همچنین بهبود سرعت از دید کاربران این محیط است. مشکلات زمان‌بندی فرآیندها به دلیل بغرنج بودن چالش بزرگی در محیط‌های گرید محاسباتی می‌باشند که حتماً باید راه‌حلی برای آن‌ها در نظر گرفته شود.
۱-۲-۲- هدف کلی
هدف کلی از انجام تحقیق ارائه روش و راه‌حلی جهت بهینه‌سازی زمان‌بندی فرآیندها در محیط محاسبات گرید می‌باشد.
۱-۲-۳- اهداف ویژه تحقیق
اهداف ویژه تحقیق حاضر عبارت است از
بررسی کلی گریدهای محاسباتی و تاریخچه پیدایش آن
بررسی کاربردهای گریدهای محاسباتی
بررسی مزایا و مشکلات گریدهای محاسباتی
بررسی انواع روش‌های زمان‌بندی فرآیندها در گریدهای محاسباتی
بررسی انواع روش‌های مکاشفه‌ای و الگوریتم‌های تکاملی استفاده‌شده در زمان‌بندی گریدهای محاسباتی