پایاننامه ارائه راهکار الگوریتم ژنتیک تقویت شده باروش MIN-MAX برای بهینه سازی مساله زمانبندی وظایف در محیط ابری


در حال بارگذاری
۷ دی ۱۳۹۷
۰ تومان

پایاننامه ارائه راهکار الگوریتم ژنتیک تقویت شده باروش

MIN-MAX برای بهینه سازی مساله زمانبندی وظایف در محیط های ابری

فلوچارت پیشنهادی برای پایاننامه ارشدارائه راهکار الگوریتم ژنتیک تقویت شده باروش MIN-MAX برای بهینه سازی مساله زمانبندی وظایف در محیط ابری بصورت شکل بالا میباشد.

 

ابر رایانه یک گسترش از محاسبات موازی، محاسبات توزیع شده و شبکه محاسبات است (سِلوارانی[۱]، ۲۰۱۰). ابر رایانه آخرین روند در دنیای فناوری اطلاعات است. به موجب آن منابع به اشبتراک گذاشبته شبده، نرم افزار و اطلاعات، به رایانه­ها و دیگر دسبتگاه­های مورد تقاضبا، مانند آماده کردن، آب، برق، گاز طبیعی، فراهم شده­اند. مفهوم این روند جدید که از سال ۱۹۶۰ آغاز شده بوسیله شرکت­های ارتباط از راه دور تا سال ۱۹۹۰ برای ارائه نقطه به نقطه مدارهای اطلاعات و سپس ارائه شبکه­های خصوصی مجازی استفاده می­شد. در سال ۲۰۰۷ توسط، GOOGLE ، IBM و بسیاری از دا نشگاه­ها و شرکت­های دیگر مورد تایید قرار گرفت. و در سال ۲۰۰۸ شرکت گارتنر ویژگی­های آن را برای مشتری به عنوان ارائه دهندگان خدمات به خوبی برجسته کرد (لی و کیو[۲]، ۲۰۱۲).

زمانبندی وظایف در علم کامپیوتر یکی از چالش برانگیزترین مسائل است. محققان و کارشناسان بسیاری وجود دارند که در مقالات و پروژه­های خود به بررسببی منابع و اشکالاتی در اجرای برنامه­های کاربردی از جمله مساله زمانبندی وظایف پرداخته­اند. همکاری اجرا در میان ابرها، مکانیزم نظارت و مدیریت یک جزء کلیدی است و نیاز به در نظر گرفتن آمادگی، زمانبندی، نظارت و مدیریت خرابی دارد. علاوه بر این، بسیاری از نظم­های پدیدار شده از یافته­های پژوهشی برای حل مساله زمانبندی اعمال می­شود، از جمله الگوریتم ژنتیک، الگوریتم کلونی مورچه، شبکه عصبی، هوش مصنوعی و جستجوی توزیع شده که با توجه به حل مساله زمانبندی به عنوان یکی از زمینه­های پژوهشی است (سیمارو[۱]، ۲۰۱۲).

شبکه های نسل پنجم

شبکه های نسل پنجم رادیویی ابری

در محیط محاسبات ابری هر کاربر ممکن است برای اجرای هر وظیفه، با صدها منابع مجازی روبه­رو شود. در این حال، تخصیص وظایف به منابع مجازی و ترتیب اجرا توسبط خود کاربر غیرممکن می­باشد. هدف از استفاده سیستم­های محاسبات ابری به حداقل رساندن هزینه و نیز به حداکثر رساندن درآمد حاصل از سرویس به برنامه­های کاربردی مصرف کنندگان می­باشد. سیستم زمانبندی، وظایف مختلفی را در جهت افزایش نرخ تکمیل وظیفه و افزایش بهره­وری از منابع و در نتیجه افزایش توان محاسباتی کنترل می­کند. زمانبندی و اجرای برنامه­ها در ابر برروی مجموعه­ای از منابع ابرهای مجازی اجرا می­شود (سلطان باغشاهی و همکاران، ۱۳۹۱).

الگوریتم­های مختلفی جهت بهبود مساله زمانبندی در محاسبات ابری استفاده می­شوند. یکی از پرکاربردترین این الگوریتم­ها، الگوریتم ژنتیک است. اخیرا استفاده از الگوریتم­های ژنتیک تقویت شده با سایر الگوریتم­ها رویکرد جدیدی را در حل مساله زمانبندی در محاسبات ابری مطرح کرده است. به همین دلیل در این پروژه از راهکار الگوریتم ژنتیک تقویت شده با روش max-min به منظور بهبود مساله زمانبندی در محاسبات ابری تحقیق می­شود.

محاسبات ابری، نمونه محاسبات رایج برای سرویس­ها و سیستم­های محاسباتی بزرگ، شناخته می­شود. با افزایش استفاده از رایانش ابری، رشد پیچیدگی ساختارها در این موضوع به وجود آورده است. بنابراین برای بهبود عملکرد و مدیریت منابع لازم است از شیوه و مدل¬های استفاده شود تا مناسب­ترین منابع برای هر حجم کاری مشخص شود. تخصیص منبع در محاسبات ابری، باعث شده است تا سرویس­های زیادی در کنار هم قرار گیرند. یکی از اهداف استراتژی تخصیص منابع به حداکثر رساندن سود از هر دو جنبه مشتری و ارائه دهنده منابع در یک مرکز بزرگ با متعادل کردن عرضه و تقاضا در بازار است.

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

فهرست:

۱ فصل اول.. ۱

۱-۱ مقدمه.. ۱

۱-۲ پیشنهاد پروژه.. ۲

۱-۳ فلوچارت الگوریتم پیشنهادی.. ۶

۱-۴ نوآوری.. ۶

۱-۵ روشها و مراحل انجام پروژه.. ۷

۲ فصل دوم.. ۹

۲-۱ مقدمه.. ۹

۲-۲ رایانش ابری…………………………………. …………………………………………………………………………………………………. ۱۰

۲-۲-۱ ویژگیهای رایانش ابری.. ۱۲

۲-۲-۲ الگوهای خدمات در دسترس رایانش ابر.. ۱۲

۲-۲-۳ الگوهای گسترش رایانش ابری.. ۱۲

۲-۳ موارد استفاده و کاربرد ابر.. ۱۳

۲-۴ مدلهای سرویسدهی رایانش ابری.. ۱۴

۲-۴-۱ نرم­افزار به عنوان سرویس.. ۱۴

۲-۴-۲ پلتفرم بهعنوان سرویس (PaaS).. 15

۲-۴-۳ زیرساخت بهعنوان سرویس (IaaS).. 16

۲-۵ خصوصیات رایانش ابری.. ۱۷

۲-۶ زمانبندی در ابر.. ۱۸

۲-۷ الگوریتمهای زمانبندی محاسبات ابر.. ۲۰

۲-۷-۱ روش FCFS. 21

۲-۷-۲ روش نوبت چرخشی.. ۲۱

۲-۷-۳ الگوریتم MIN-MIN.. 21

۲-۷-۴ روش max-min. 24

۲-۷-۵ روش مبتنی بر الگوریتم ژنتیک.. ۲۶

۲-۷-۶ الگوریتم زمانبندی تعادل بین زمان و هزینه.. ۲۶

۲-۷-۷ روش اکتشافی مبتنی بر بهینهسازی ازدحام ذرات برای نرمافزار زمانبندی گردش کار   ۲۷

۲-۷-۸ الگوریتم مبتنی بر هزینه بهبود یافته برای زمانبندی کارها   ۲۷

۲-۸ مروری بر کارهای داخلی.. ۲۸

۲-۹ مروری بر مطالعات خارجی.. ۴۲

فصل سوم………………………………………………………………………………………………………………………..۴۷

۳-۱مقدمه       …………………………………………………………………………………………………………………۴۹

۳-۲الگوریتم پیشنهادی………………………………………………………………………………………………………..۵۰

۳-۲-۱ ایجاد جمعیت اولیه………………………………………………………………………………………………….۵۲

۳-۲-۲ تابع برازندگی………………………………………………………………………………۵۳

۳-۲-۳ عملیات ترکیب…………………………………………………………………………….۵۴

۳-۲-۴ عملیات جهش …………………………………………………………………………….۵۵

۳-۲-۵ شرایط توقف الگوریتم ……………………………………………………………………..۵۵

۳-۲-۶ روش پیشنهادی تولید نسل اولیه ……………………………………………………………….۵۶

فهرست اشکال

شکل ‏۲‑۱. نرمافزار بهعنوان سرویس.. ۱۵

شکل ‏۲‑۲. پلتفرم سرویسدهی PaaS. 16

شکل ‏۲‑۳. زیرساخت به­عنوان سرویس.. ۱۷

شکل ‏۲‑۴. فلوچارت زمانبندی و تخصیص منبع در محاسبات ابری   ۲۰

شکل ‏۲‑۵. شرح معماری الگوریتم MIN-MIN.. 23

شکل ‏۲‑۶. شرح معماری الگوریتم MAX-MIN.. 25

 

مراجع و منابع

  1. اسلامی زاد, علیرضا و سارا نجف زاده، ۱۳۹۵، مقایسه الگوریتم های زمانبندی در محیط رایانش ابری، اولین کنفرانس بین المللی چشم انداز های نو در مهندسی برق و کامپیوتر، تهران، کنفدراسیون بین المللی مخترعان جهان (IFIA)، دانشگاه جامع علمی کاربردی
  2. اسمعیلی, محمد و عباس میرزایی، ۱۳۹۴، زمانبندی وظایف در رایانش ابری با استفاده از الگوریتم بهینه سازی ازدحام ذرات بهبود یافته، کنفرانس بین المللی یافته های نوین پژوهشی درمهندسی برق و علوم کامپیوتر، تهران، موسسه آموزش عالی نیکان
  3. اشکو, نوید و ساناز دژم، ۱۳۹۴، زمانبندی کارها در محیط های محاسبات ابری موبایل به کمک الگوریتم ژنتیک، دومین همایش پژوهش های نوین در علوم و فناوری، بصورت الکترونیکی، شرکت علم محوران آسمان
  4. اطمینانی, کبری؛ سید مجتبی روحانی و نورعلی رائیجی یانه سری، ۱۳۸۷، طراحی و پیاده سازی یک الگوریتم زمانبندی در گرید بر مبنای دو الگوریتم Min-Min و Max-Min به کمک برنامه سازی ژنتیک، چهاردهمین کنفرانس سالانه انجمن کامپیوتر ایران، تهران، انجمن کامپیوتر، دانشگاه صنعتی امیر کبیر
  5. ثقفی فر, حسین و ابوالحسن مبشری، ۱۳۸۴، به کارگیری الگوریتم Min-Max به منظور بهینه سازی تصویر اجسام زیر آب، ششمین همایش علوم و فنون دریایی، تهران، مرکز علوم جوی و اقیانوسی
  6. حبیبی, فرشته؛ همایون موتمنی و فرهاد رمضانی، ۱۳۹۳، رویکرد جدید برای حل مسئله زمانبندی کارها در محیط محاسبات ابری با استفاده از ترکیب الگوریتم ژنتیک و جستجوی حرام، همایش ملی علوم و مهندسی کامپیوتر، مشهد، موسسه آموزش عالی خاوران
  7. رضائی, فرشته، ۱۳۹۴، تجزیه و تحلیل مطالعه روشهای تعادل بار در محیط محاسبات ابری (مورد مطالعه :الگوریتم های MIN-MIN و MAX-MIN)، هجدهمین کنفرانس ملی دانشجویی مهندسی برق ایران، مشهد، سازمان علمی دانشجویی مهندسی برق کشور
  8. رمضانی طرقدری, عطیه و جواد محبی نجم آباد، ۱۳۹۲، الگوریتم زمانبندی مبتنی برmin-min و max-min درمحیط گرید محاسباتی، کنگره ملی مهندسی برق، کامپیوتر و فناوری اطلاعات، مشهد، موسسه آموزش عالی خیام
  9. سلطان باغشاهی سمیه، سلطان باغشاهی لیلا،خادم زاده احمد، جبه داری سام) ۱۳۹۱ (، >>تحلیل چالش های امنیتی و تاثیر آن بر رایانش ابری<<،دانشگاه صنعتی امیر کبیرد
  10. سلطانی سولگان، نسیم؛ برکتین، بهرنگ و بهزاد سلیمانی، ۱۳۹۴، یک الگوریتم بهبود یافته جهت زمانبندی وظایف در محاسبات ابری مبتنی بر الگوریتم ژنتیک چند هدفه وزنی، پایان‌نامه کارشناسی ارشد، مؤسسه آموزش عالی علامه نایینی، پژوهشکده برق و کامپیوتر
  11. شیرمحمدی, پوریا؛ سمیره خمیسی؛ پگاه نصیری و مهدی صادق زاده، ۱۳۹۵، رویکردی کارآمد از الگوریتم ژنتیک برای زمانبندی کارها در محیط محاسبه ابری، اولین کنفرانس بین المللی دستاوردهای نوین پژوهشی در مهندسی برق و کامپیوتر، تهران، کنفدراسیون بین المللی مخترعان جهان (IFIA)، دانشگاه جامع علمی کاربردی
  12. غزنوی قصونی، برات اله؛ خرم، اسماعیل و علی میرحسنی، ۱۳۸۷، روش‌های Min-Norm و Min-Max در بهینه‌سازی چند هدفه، پایان‌نامه کارشناسی ارشد، دانشگاه صنعتی امیرکبیر، دانشکده ریاضی و علوم کامپیوتر
  13. غلامی, سمانه و مهران شرقی، ۱۳۹۵، بررسی انواع الگوریتم های بهینه سازی درحل مسئله زمانبندی جریان کار جهت بهبود کیفیت سرویس در محاسبات ابری، دومین همایش ملی پژوهش های مهندسی رایانه، همدان، گروه پژوهشی اکباتان
  14. فرج زاده اصل, فرید؛ علی سلیمانی ایوری و حسین خسروی، ۱۳۹۱، روش جدیدی برای طبقه بندی الگو، بر پایه ابرجعبه های فازی Min-Max، یازدهمین کنفرانس سراسری سیستم های هوشمند، انجمن سیستمهای هوشمند ایران، دانشگاه خوارزمی
  15. گلزاری اسکویی, امین؛ عسگرعلی بویر و هیوا ابراهیم زاده، ۱۳۹۶، ارایه یک روش بهبود یافته Kernel K means با روش Min-Max، سومین کنفرانس ملی محاسبات توزیعی و پردازش داده های بزرگ، تبریز، دانشگاه شهید مدنی آذربایجان
  16. مقبلی, سیدمسعود و خسرو امیری زاده، ۱۳۹۵، حل مسئله زمانبندی گراف وظایف با استفاده از الگوریتم ژنتیک بهبود یافته در معماری چندپردازنده ای، اولین کنفرانس بین المللی دستاوردهای نوین پژوهشی در مهندسی برق و کامپیوتر، تهران، کنفدراسیون بین المللی مخترعان جهان (IFIA)، دانشگاه جامع علمی کاربردی
  17. منتظری، مرتضی؛ میخ چین سعید و علی راستی، ۱۳۹۵، طراحی و بهینه سازی تکاملی چند هدفه الگوریتم کنترل سوخت مین-ماکس موتور توربوفن، نشریه مهندسی مکانیک مدرس، دوره ۱۶ , شماره ۵; ۳۸۸-۳۷۹.
  18. میر, سجاد و مهدی فاضلی، ۱۳۹۴، ارائه یک الگوریتم زمانبندی وظایف کارا در محیط های رایانش ابری بر مبنای الگوریتم ژنتیک بهینه سازی شده، اولین کنفرانس بین المللی وب پژوهی، تهران، دانشگاه علم و فرهنگ
  19. نبوی چاشمی, سیدمحمد صادق و کوروش کیانی، ۱۳۹۳، رویکردی نوین برای زمانبندی وظایف در سیستم های محاسبات ابری با ترکیب الگوریتم ژنتیک و جستجوی هارمونی، ششمین کنفرانس مهندسی برق و الکترونیک ایران، گناباد، دانشگاه آزاد اسلامی واحد گناباد
  20. یداللهی, مهدی و محمد صفری مهماندوستی، ۱۳۹۵، زمانبندی کارها در سیستم های محاسبات ابری با استفاده از الگوریتم ژنتیک ترکیبی، کنفرانس ملی ربات های پروازی، گرگان، موسسه آموزش عالی میرداماد گرگان
  21. Alhazmi, O. H. (2016). A Cloud-Based Adaptive Disaster Recovery Optimization Model. Computer and Information Science, 9(2), 58.
  22. Awad, A. I., N. A. El-Hefnawy, and H. M. Abdel_kader. “Enhanced particle swarm optimization for task scheduling in cloud computing environments.” Procedia Computer Science 65 (2015): 920-929.
  23. Cui Lin, Shiyong Lu,” Scheduling ScientificWorkflows Elastically for Cloud Computing” in IEEE 4th International Conference on Cloud Computing, 2011.
  24. Efficient Optimal Algorithm of Task Scheduling in Cloud Computing Environment, Amit Agarwal, Saloni Jain, International Journal of Computer Trends and Technology (IJCTT) – volume 9 number 7– Mar 2014
  25. Magoules, T. Nguyen and L. Yu, Grid resource management Toward Virtual and Services Compliant Grid Computing, CHAPMAN & HALL/CRC Numerical Analysis and Scientific Computing, London, pp. 161-88, 2009.
  26. Guangzhen Lu, Wen’an Tan, Yong Sun, Zijian Zhang, Anqiong Tang, “QoS Constraint Based Workflow Scheduling for Cloud Computing Services”, Journal Of Software, Vol. 9, No.4, pp. 926-930, 2014.
  27. Jamali, S., Alizadeh, F., & Sadeqi, S. (2016). Task Scheduling in Cloud Computing Using Particle Swarm Optimization. The Book of Extended Abstracts, 192.
  28. Liu; Y. Yang; J. Chen, X. Liu; D. Yuan; H. Jin, A Compromised-Time- Cost Scheduling Algorithm in SwinDeW-C for Instance-intensive Cost-Constrained Workflows on Cloud Computing Platform, International Journal of High Performance Computing Applications, vol.24 no.4 445-456,May,2010.
  29. Kumar P, Verma A. Independent task scheduling in cloud computing by improved genetic algorithm. International Journal of Advanced Research in Computer Science and Software Engineering. 2012 May;2(5).
  30. Levi, E. E., Cohen, I., Levi, R., & Sade, S. (2016). U.S. Patent No. 20,160,034,835. Washington, DC: U.S. Patent and Trademark Office
  31. Li, C., Liu, Y. C., & Yan, X. (2016). Optimization-based resource allocation for software as a service application in cloud computing. Journal of Scheduling, 1-11.
  32. Li, J., & Qiu, M. (2012). Online optimization for scheduling preemptable tasks on IaaS cloud systems. J. Parallel Distrib. Comput., 677-666.
  33. Liu K, Jin H, Chen J, Liu X, Yuan D, Yang Y. ,”A Compromisedtime-cost Scheduling Algorithm in Swindew-c for Instance-intensive Cost-constrained Workflows on a Cloud Computing Platform”, International Journal of High Performance Computing Application s, pp. 445-456, 2010.
  34. Lucas-Simarro, J. L., Moreno-Vozmediano, R., S. Montero, R., & M. Llorente, I. (2012). Scheduling strategies for optimal service deployment across multiple clouds. Future Generation Computer Systems.
خرید
 راهنمای خرید:
  لینک دانلود فایل بلافاصله بعد از پرداخت وجه به نمایش در خواهد آمد.
  همچنین لینک دانلود به ایمیل شما ارسال خواهد شد به همین دلیل ایمیل خود را به دقت وارد نمایید.
  ممکن است ایمیل ارسالی به پوشه اسپم یا Bulk ایمیل شما ارسال شده باشد.
  در صورتی که به هر دلیلی موفق به دانلود فایل مورد نظر نشدید با ما تماس بگیرید.