ارائه الگوریتم فرا ابتکاری جدید بر اساس جستجوی ممنوعه برای حل مسئله زمانبندی وظایف در سیستم مبتنی بر محاسبات ابری و مه

نوع مقاله : مقاله کامپیوتر

نویسندگان

1 گروه مهندسی کامپیوتر،واحد تهران جنوب،دانشگاه آزاد اسلامی، تهران، ایران

2 دانشکده کامپیوتر

چکیده

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

کلیدواژه‌ها

عنوان مقاله [English]

A New Meta-Heuristic Algorithm Based on Tabu Search for the Job Scheduling Problem in a Fog-Cloud system

نویسندگان [English]

  • Seydeh Samira Mohammadi 1
  • Mahmood Deypir 2
1 Tehran south branch
2 Computer engineering
چکیده [English]

Today, with the expansion of communications and the high volume of data, the need for processing them at a low time and high speed has increased. On the other hand, conducting this high volume of computing operations requires systems with high processing and storage capacities, which increase total costs. Therefore, proposing a suitable and affordable infrastructure can be very significant. The purpose of this article is to design and build an infrastructure with low cost and low response time using cloud computing and fog computing. In addition, one of the key issues for creating such systems at a high speed and minimum time is to allocate appropriate system resources to user requests and, as a result, load balances in the system. Among the various meta-heuristic methods, the Tabu search makes it a common practice because of its high expansion in various optimization issues, as well as memory and high-speed features. Therefore, in this paper, a new method based on Tabu Search is proposed that is optimized using approximate nearest neighbor (ANN) and Fruit Fly Optimization (FOA) Algorithms. Finally, to evaluate and validate the proposed method, a case study is simulated on a smart home using the proposed infrastructure and the real dataset. Both methods have been implemented in this infrastructure and their performance has been calculated based on runtime and memory consumption. The results show the capability and efficiency of the proposed method for the various problems.

کلیدواژه‌ها [English]

  • cloud computing
  • Fog computing
  • Job scheduling
  • Smart home
  • Tabu Search
  • Fog-Cloud platform

مراجع

[1] B. Varghese and R. Buyya, "Next generation cloud computing: New trends and research directions", Future Generation Computer Systems, Vol. 79, 2018, pp. 849–861.
[2] M. Amadeo, A. Giordano, C. Mastroianni and A. Molinaro, "On the Integration of Information Centric Networking and Fog Computing for Smart Home Services", Springer, Cham, 2019, pp. 75–93.
[3] M. Marjani, F. Nasaruddin, A. Gani, A. Karim and I. Abaker, "Big IoT Data Analytics : Architecture , Opportunities , and Open Research Challenges", Vol. 3536, No. c, 2017, pp. 1–17.
[4] A. Mebrek, L. Merghem-boulahia and M. Esseghir, "Efficient Green Solution for a Balanced Energy Consumption and Delay in the IoT-Fog-Cloud Computing", 2017.
[5] S. Sarkar, S. Chatterjee and S. Misra, "Assessment of the Suitability of Fog Computing in the Context of Internet of Things", IEEE Transactions on Cloud Computing, Vol. 6, No. 1, 2018, pp. 46–59.
[6] A.N. Toosi, R. Mahmud, Q. Chi and R. Buyya, "Management and Orchestration of Network Slices in 5G, Fog, Edge, and Clouds", in Fog and Edge Computing, Hoboken, NJ, USA: John Wiley & Sons, Inc., 2019, pp. 79–101.
[7] S. Bitam, S. Zeadally and A. Mellouk, "Fog computing job scheduling optimization based on bees swarm",
Enterprise Information Systems, Vol. 12, No. 4, 2018, pp. 373–397.
[8] A. Yassine, S. Singh, M.S. Hossain and G. Muhammad, "IoT big data analytics for smart homes with fog and cloud computing", Future Generation Computer Systems, Vol. 91, 2019, pp. 563–573.
[9] S.A.A. Naqvi, N. Javaid, H. Butt, M.B. Kamal, A. Hamza and M. Kashif, "Metaheuristic Optimization Technique for Load Balancing in Cloud-Fog Environment Integrated with Smart Grid", Springer, Cham, 2019, pp. 700–711.
[10] L. Peng, A.R. Dhaini and P.-H. Ho, "Toward integrated Cloud–Fog networks for efficient IoT provisioning: Key challenges and solutions", Future Generation Computer Systems, Vol. 88, 2018, pp. 606–613.
[11] P.G.V. Naranjo, Z. Pooranian, M. Shojafar, M. Conti and R. Buyya, "FOCAN: A Fog-supported smart city network architecture for management of applications in the Internet of Everything environments", Journal of Parallel and Distributed Computing, Jul. 2018.
[12] S.K. Sood and K.D. Singh, "SNA Based Resource Optimization in Optical Network using Fog and Cloud Computing", Optical Switching and Networking, Dec. 2017.
[13] S. Singh and A. Yassine, "IoT Big Data Analytics with Fog Computing for Household Energy Management in Smart Grids", Springer, Cham, 2019, pp. 13–22.
[14] Q. Li, L. Zhao, J. Gao, H. Liang, L. Zhao and X. Tang, "SMDP-Based Coordinated Virtual Machine Allocations in Cloud-Fog Computing Systems", IEEE Internet of Things Journal, Vol. 5, No. 3, 2018, pp. 1977–1988.
[15] Z. Zeng, X. Yu, K. He and Z. Fu, "Adaptive Tabu search and variable neighborhood descent for packing unequal circles into a square", Applied Soft Computing, Vol. 65, 2018, pp. 196–213.
[16] مجید محمّدپور و حمید پروین، «الگوریتم کلونی زنبور مصنوعی آشوب‌گونه مبتنی بر حافظه برای حلّ مسائل بهینه‌سازی پویا»، مجلة مدل‌سازی در مهندسی، دورة 15، شمارة 51، زمستان 1396، صفحة 113- 132.
[17] سید محمّدحسن حسینی و علی‌اکبر حسنی، «توسعة یک الگوریتم شاخه و کران برای حلّ مسئلة زمان‌بندی در سیستم تولید جریان کارگاهی مونتاژی»، مجلة مدل‌سازی در مهندسی، دورة 15، شمارة 51، زمستان 1396، صفحة 85- 98.
[18] حسین شریف‌زاده و نیما امجدی، «توزیع بهینه توان رآکتیو با استفاده از الگوریتم بهینه‌سازی دسته ذرّت»، مجلة مدل‌سازی در مهندسی، دورة 4، شمارة 18، زمستان 1388، صفحة 67- 73.
[19] G.R. Raidl, J. Puchinger and C. Blum, Metaheuristic Hybrids.
[20] F. Glover, "Tabu Search—Part I", ORSA Journal on Computing, Vol. 1, No. 3, 1989, pp. 190–206.
[21] H. Pirim, E. Bayraktar and B. Eksioglu, "Tabu Search: A Comparative Study", Tabu Search, September 2008.
[22] F. Glover, "Tabu search fundamentals and uses", Vasa, 1995.
[23] T-61.5060 Algorithmic methods for data mining Slide set 5: locality-sensitive hashing.
[24] W.-T. Pan, "A new Fruit Fly Optimization Algorithm: Taking the financial distress model as an example", Knowledge-based Systems, Vol. 26, 2012, pp. 69–74.
 
مدل سازی در مهندسی
دوره 18، شماره 62
آبان 1399
صفحه 13-29

فایل ها

سابقه مقاله

  • تاریخ دریافت: 06 تیر 1398
  • تاریخ بازنگری: 15 شهریور 1398
  • تاریخ پذیرش: 21 آبان 1398

هم رسانی

ارجاع به این مقاله

آمار