ارائه مدل ترکیبی زمانبندی وظایف براساس الگوریتم تطبیقی پویا و ژنتیک در محیط رایانش ابری
محورهای موضوعی : پارکهاي علم و فناوري و مراکز رشدمژده ربانی 1 , هدی مرادی 2 , اسداله علیرضایی 3 *
1 - دانشگاه ازاد اسلامی یزد
2 - دانشگاه ازاد اسلامی یزد
3 - دانشگاه آزاد یزد
کلید واژه: رایانش ابری زمانبندی الگوریتم تطبیقی پویا الگوریتم ژنتیک درخت کی‌دی,
چکیده مقاله :
رایانش ابری مفهومی است که اخیراً در دنیای فناوری اطلاعات معرفی شده که محیطی را برای به اشتراک‌گذاری منابع فراهم می‌نماید. در محیط رایانش ابری یک سیستم زمانبندی کارا و مؤثر، نقش کلیدی دارد و در میزان موفقیت آن محیط بسیار تعیین‌کننده می‌باشد. از این‌رو مسأله زمانبندی وظایف در رایانش ابری، مسأله‌‌ای بسیار مهمی محسوب می‌شود که سعی دارد یک زمانبندی بهینه برای اجرای وظایف و تخصیص منبع بهینه مشخص نماید. این پژوهش با هدف ارائه رویکردی جدید برای بهینه‌سازی زمانبندی وظایف براساس ترکیبی از الگوریتم تطبیقی پویا و الگوریتم ژنتیک در محیط رایانش ابری انجام گرفته است. مدل ترکیبی، با هدف پوشش‌دادن نقاط ضعف دو الگوریتم ژنتیک و زمانبندی تطبیقی پویا، ارائه شد که به موجب آن ضعف الگوریتم ژنتیک یعنی سرعت عمل پایین، با ایجاد یک راه‌حل اولیه مناسب برطرف گردید و همچنین ضعف الگوریتم زمانبندی تطبیقی پویا که همانا به دام افتادن در جواب‌های محلی است، با استفاده از الگوریتم بهینه‌سازی تکاملی پوشش داده شد. در مدل پیشنهادی نخست الگوریتم تطبیقی پویا با تکنیک جستجوی منابع مورد نیاز به کمک درخت کی‌دی و بازیابی داده‌ها به صورت موازی توانسته است در زمان بسیار خوبی جواب مناسبی برای مسأله‌ی زمانبندی پیدا کند، که به‌عنوان جواب اولیه به الگوریتم ژنتیک سپرده شد و الگوریتم ژنتیک نیز به جستجوی بهینه می‌پردازد. در نتیجه الگوریتم نهایی حاصل از ترکیب این دو، توازن بار بهتری برای منابع ابری در مدت زمان نسبتاً قابل قبول ارائه می‌دهد.
Cloud computing is a concept introducing in the world of information technology recently, and provides an environment for sharing sources. In this environment, an efficient and effective scheduling system plays a fundamental role. Hence, the problem of scheduling tasks in cloud computing is a very important issue, which tries to identify an optimal scheduling for performing tasks and allocating an optimal source. The purpose of this research is to provide a new hybrid model for optimization of scheduling tasks based on combination of dynamic adaptive and genetic algorithms in a cloud computing environment. The hybrid model aimed to cover the defects of these algorithms. Based on this model, an initial solution was presented for resolving the weakness of the genetic algorithm, the action of low speed as well as the weakness of the dynamic adaptive algorithm, trapping in local answers. In the proposed model, first, dynamic adaptive algorithm could find an appropriate solution for scheduling problem within a good time using the technique of searching required resources by KD tree and data retrieval in parallel. This solution, as an initial answer, was given to the genetic algorithm, and this algorithm performed the optimal research. As a consequence, the final algorithm, a combination of these two algorithms, provides a better load balancing for cloud resources in a relatively acceptable time.
1- محمودی، احمد و بهروزیان‌نژاد. زمان‌بندي وظایف در محیط رایانش ابري با استفاده از الگوریتم ترکیبی ژنتیک و تکاملی تفاضلی. دومین کنفرانس ملی کامپیوتر، فناوری اطلاعات و کاربردهای هوش مصنوعی، دانشگاه شهید چمران اهواز، 1397.
2- درخشانیان، یلدا، میرعابدینی، جواد و هارون آبادی، علی. توازن بار در محیط رایانش ابری با در نظر گرفتن وابستگی میان وظایف و استفاده از الگوریتم ژنتیک تطبیقی. فصلنامه مهندسی مخابرات جنوب، دوره 7، شماره 24: صص 58-69، 1396.
3- سلیمی حجت آبادی، رضا. زمانبندی وظایف با حفظ تعادل بار در گرید محاسباتی با استفاده از الگوریتم ژنتیک با نامغلوب و عملگرهای فازی، پایان‌نامه کارشناسی‌ارشد علوم کامپیوتر، دانشگاه غیردولتی گلبرگ، 1391.
4- سپهر، فرشته، بزرگی، اشرف السادات و صدقی، شکوه. امکان‌ســنجی به‌کارگیری فناوری رایانش ابری از دیدگاه کتابداران کتابخانه‌های دانشــگاه‌های علوم پزشکی شهر تهران. مجله دانشکده پیراپزشکی دانشگاه علوم پزشکی تهران، شماره 5: صص 442-429، 1395.
5- اصغری، علی و سهرابی، محمدکریم. بررسی الگوریتم‌های زمانبندی منابع در پردازش ابری. دومین کنفرانس ملی و اولین کنفرانس بین‌المللی محاسبات نرَم. گیلان، ایران: صص 1287-1293، 1396.
6- حبیب‌پور، نازنین و نعمت بخش، ناصر. بهبود زمانبندی وظایف در رایانش ابری با استفاده از الگوریتم‌های فراابتکاری. سومین کنفرانس ملی نوین در مهندسی کامپیوتر و برق، باشگاه پژوهشگران جوان و نخبگان، 1396.
7- غریبی، الهام و جعفری نویمی‌پور. زمانبندی کارهای اولویت‌دار دارای مهلت زمانی در رایانش ابری به کمک الگوریتم بهینه‌سازی گرگ خاکستری. علوم رایانشی. شماره 7: صص 24-33، 1396.
8- نوری یگانه، نسیم و روستایی، رسول. زمانبندی وظایف در رایانش ابری. دومین کنفرانس ملی تحقیقات کاربردی در مهندسی. شیراز، 1396.
9- طهماسبی، مسعود و خیام باشی، محمدرضا. ارائه مدل رایانش ابری وسایل نقلیه برای بهینه‌سازی هزینه و زمان پاسخگویی. کنفرانس بین‌المللی وب‌پژوهی. تهران، ایران، 1397.
10- جمالی، سمیرا و شاکری، مجتبی. زمانبندی ایستای وظایف در محیط رایانش ابری با استفاده از الگوریتم ترکیبی بهینه‌سازی ازدحام ذرات و جستجوی. هشتمین کنفرانس هوش مصنوعی و رباتیک و دهمین سمپوزیوم بین‌المللی ربوکاپ آزاد. قزوین. ایران، 1397.
11- میسوندی، زهرا و و جعفرزاده، نیما. ارائه یک الگوریتم جدید جهت ایجاد تعادل بار روی ماشین‌های مجازی در رایانش ابری. دومین کنفرانس بین‌المللی ترکیبات، رَمزنگاری و محاسبات. تهران، ایران، 1396.
12- رجبی، صدیقه، رشیدا، یاسمن و مردوخی، فرهاد. مروری بر الگوریتم‌های فرااکتشافی در رایانش ابری و ارائه یک الگوریتم هیبریدی برای حل مسأله زمانبندی کارها در ابران. کنفرانس بین‌المللی پژوهش در علوم و تکنولوژی. تهران، ایران، 1395.
13- رجبی، صدیقه، رشیدا، یاسمن و مردوخی، فرهاد. ارائه یک الگوریتم ترکیبی بر مبنای الگوریتم ژنتیک برای زمانبندی کارها در رایانش ابری. کنفرانس بین‌المللی پژوهش در علوم و تکنولوژی. تهران، ایران، 1395.
14- حبیبی، فرشته، موتمنی، همایون و رمضانی، فرهاد.. رویکرد جدید برای حل مسأله زمانبندی کارها در محیط محاسبات ابری با استفاده از ترکیب الگوریتم ژنتیک و جستجوی حرام. نهمین سمپوزیوم پیشرفت‌های علوم و تکنولوژی. مشهد. ایران، 1393.
15- رمدانی، لادن و شیروانی، میرسعید. الگوریتم زمانبندی وظایف مبتنی بر ژنتیک در سیستم‌های توزیعی ناهمگن. اولین کنفرانس مهندسی برق و کامپیوتر، دانشگاه آزاد اسلامی، قائم‌شهر، ایران، 1397.
16- ابراهیمی هردورودی، حامد، نودهی، علی و ابراهیمی، حسن. ارایه روش بهبودسازی زمانبندی وظایف در رایانش ابری با الگوریتم گرگ خاکستری. دومین کنفرانس ملی مهندسی و فناوری ربات‌های پروازی. گرگان، ایران، 1397.
17- اردستانی، پریا و بدیع، کامبیز. زمانبندی در محیط محاسبات ابری با استفاده از الگوریتم‌های تکامل. کنفرانس بین‌المللی مهندسی و علوم کاربردی. تهران، ایران، 1395.
18- کهمره، حسین و مصلی‌نژاد، احمد. ارائه الگوریتم زمانبندی فرایندها در رایانش ابری مبتنی بر هوش جمعی. دومین کنفرانس بین‌المللی و سومین همایش ملی کاربرد فناوری‌های نوین در علوم مهندس. دانشگاه تربیت حیدریه، مشهد، ایران، 1394.
19- امینی، رضا و فاطری، سهیل. روش بهبودیافته زمانبندی منابع در رایانش ابری با استفاده از برنامه‌نویسی ژنتیک. نهمین سمپوزیوم پیشرفت‌های علوم و تکنولوژی. مشهد. ایران، 1393.
20- اسمعیلی رنجبر، خاطره و سلاجقه، مژده. بررسی و نقش رایانش ابری در شرکت‌های دانش‌بنیان ایران. فصلنامه رشد فناوری. شماره 62: صص60- 67، 1399.
21- Tai Wang. S ,Chuan Chen.Y and Ching Lin.Y. Energy Efficient Resource Allocation and Scheduling in Cloud Computing Platform, International Journal of Computer. Electrical, Aulomation, Control and Information Engineering, Volume 10, Issue 10, PP:1823-1827, 2016.
22- Madni, S. H. H., Abd Latiff, M. S., Abdullahi, M., Abdulhamid, S. M., & Usman, M. J. Performance comparison of heuristic algorithms for task scheduling in IaaS cloud computing environment. PLOS ONE, Volume 12, Issue 5, 2017.
23- Calheiros, R. N., Netto, M.A. S De Rose, C. A. F., and R. Buyya, EMUSIM. an integrated emulation and simulation environment for modeling, evaluation, and validation of performance of cloud computing applications. Software-Practice and Experience, Volume 43, Issue5, PP:595-612, 2012.
24- Ben Alla, H., Ben Alla, S., Touhafi, A., & Ezzati, A. A novel task scheduling approach based on dynamic queues and hybrid meta-heuristic algorithms for cloud computing environment. Cluster Computing. Cluster Computing., doi:10.1007/s10586-018-2811-x, 2018.
25- Gawali, M. B., & Shinde, S. K. Task scheduling and resource allocation in cloud computing using a heuristic approach. Journal of Cloud Computing, Volume 7, Issue 1, 2018.
26- Rahman, M. Adaptive Workflow Scheduling for Dynamic Grid and Cloud Computing Environment. Concurrency Computat: Pract. Exper, 25, pp: 1816–1842, 2013.
27- Abualigah, L., & Diabat, A. A novel hybrid antlion optimization algorithm for multi-objective task scheduling problems in cloud computing environments. Cluster Computing, 2020.
28- Milan, S. T., Rajabion, L., Ranjbar, H., & Navimipoir, N. J. Nature inspired meta-heuristic algorithms for solving the load-balancing problem in cloud environments. Computers & Operations Research. , Volume110,PP:159-187, 2019.
29- Mapetu, J. P. B., Chen, Z., & Kong, L. Low-time complexity and low-cost binary particle swarm optimization algorithm for task scheduling and load balancing in cloud computing. Applied Intelligence, 2019.
30- Choudhary, A., Gupta, I., Singh, V., & Jana, P. K. A GSA based hybrid algorithm for bi-objective workflow scheduling in cloud computing. Future Generation Computer Systems, Volume 83, PP:14–26, 2018.
31- Ben Alla, H., Ben Alla, S., Touhafi, A., & Ezzati, A. A novel task scheduling approach based on dynamic queues and hybrid meta-heuristic algorithms for cloud computing environment. Cluster Computing. Cluster Computing. doi:10.1007/s10586-018-2811-x, 2018.
32- Tahrir Younis, M. & Yang, Sh. Hybrid meta- heuristic algorithms for independent job scheduling in grid computing. Applied Soft Computing, Volume 72: PP:498-517, 2018.
33- Velliangiri, S., Karthikeyan, P., Arul Xavier, V. M., & Baswaraj, D. Hybrid electro search with genetic algorithm for task scheduling in cloud computing. Ain Shams Engineering Journal:PP:1-9, 2020.
34- Saeedi,S., Khorsand,R., Ghandi Bidgoli,S., Ramezanpour,M. Improved many-objective particle swarm optimization algorithm for scientific workflow scheduling in cloud computing. Computers & industrial engineering, Volume 147: PP:159–187, 2020.
35- Gawali, M. B., & Shinde, S. K. Task scheduling and resource allocation in cloud computing using a heuristic approach. Journal of Cloud Computing, Volume 7, Issue 1, 2018.
36- Sharma,S., Tyagi,S., A Survey on Heuristic Approach for Task Scheduling in Cloud Computing. International Journal of Advanced Research in Computer Science, Volume8:PP 1089-1092, 2017.