Manuscript ID : 202006218180 Visit : 13890 Page: 71 - 84

Article Type: Original Research

Scheduling tasks in cloud environments using mapping framework - reduction and genetic algorithm

Subject Areas : General

nima khezr ¹ , nima jafari novimipour ^{2
*}

1 -
2 -

Received: 2019-12-25 Accepted : 2019-12-25 Published : 2020-06-21

Keywords: Cloud Computing, Task Scheduling, Execution Reduction, Genetic Algorithm, Mapping-Reduction, Hadoop,

Abstract :

Task scheduling is a vital component of any distributed system such as grids, clouds, and peer-to-peer networks that refer tasks to appropriate resources for execution. Common scheduling methods have disadvantages such as high time complexity, inconsistent execution of input tasks, and increased program execution time. Exploration-based scheduling algorithms to prioritize tasks from

References:

1. Khemka, B., et al., Utility maximizing dynamic resource management in an oversubscribed energy-constrained heterogeneous computing system. Sustainable Computing: Informatics and Systems, 2015. 5: p. 14-30.
2. Arunarani, A.R., Manjula, D. and Sugumaran, V., 2019. Task scheduling techniques in cloud computing: A literature survey. Future Generation Computer Systems, 91, pp.407-415.
3. Zang, X., Sun, J., Zhao, J. and Zeng, W., 2018, May. Research Progress of Cloud Computing Task Scheduling Technology. In 2018 3rd International Conference on Automation, Mechanical Control and Computational Engineering (AMCCE 2018). Atlantis Press.
4. Young Choon, L. and A.Y. Zomaya, A Novel State Transition Method for Metaheuristic-Based Scheduling in Heterogeneous Computing Systems. Parallel and Distributed Systems, IEEE Transactions on, 2008. 19(9): p. 1215-1223.
5. Keshanchi, B. and Navimipour, N.J., 2016. Priority-based task scheduling in the cloud systems using a memetic algorithm. Journal of Circuits, Systems and Computers, 25(10), p.1650119.
6. Dean, J. and S. Ghemawat, MapReduce: a flexible data processing tool. Communications of the ACM, 2010. 53(1): p. 72-77.
7. Khezr, S.N. and Navimipour, N.J., 2017. MapReduce and its applications, challenges, and architecture: a comprehensive review and directions for future research. Journal of Grid Computing, 15(3), pp.295-321.
8. Topcuoglu, H., S. Hariri, and W. Min-You, Performance-effective and low-complexity task scheduling for heterogeneous computing. Parallel and Distributed Systems, IEEE Transactions on, 2002. 13(3): p. 260-274.
9. Mateos, C., E. Pacini, and C.G. Garino, An ACO-inspired algorithm for minimizing weighted flowtime in cloud-based parameter sweep experiments. Advances in Engineering Software, 2013. 56: p. 38-50.
10. Ashouraie, M. and N. Jafari Navimipour, Priority-based task scheduling on heterogeneous resources in the Expert Cloud. Kybernetes, 2015. 44(10): p. 1455-1471.
11. Wang, W., et al., Cloud-DLS: Dynamic trusted scheduling for Cloud computing. Expert Systems with Applications, 2012. 39(3): p. 2321-2329.
12. Xu, Y., et al., A genetic algorithm for task scheduling on heterogeneous computing systems using multiple priority queues. Information Sciences, 2014. 270(0): p. 255-287. , 2014. 270(0): p. 255-287.
13. Abed, I., et al., Optimization of the Time of Task Scheduling for Dual Manipulators using a Modified Electromagnetism-Like Algorithm and Genetic Algorithm. Arabian Journal for Science and Engineering, 2014. 39(8): p. 6269-6285.
14. Lipowski, A. and D. Lipowska, Roulette-wheel selection via stochastic acceptance. Physica A: Statistical Mechanics and its Applications, 2012. 391(6): p. 2193-2196.
15. Ong, B. and M. Fukushima, Genetic algorithm with automatic termination and search space rotation. Memetic Computing, 2011. 3(2): p. 111-127.
16. Hashem, Ibrahim Abaker Targio, Nor Badrul Anuar, Mohsen Marjani, Ejaz Ahmed, Haruna Chiroma, Ahmad Firdaus, Muhamad Taufik Abdullah et al. "MapReduce scheduling algorithms: a review." The Journal of Supercomputing (2018): 1-31.
17. Keshanchi B, Souri A, Navimipour NJ. An improved genetic algorithm for task scheduling in the cloud environments using the priority queues: formal verification, simulation, and statistical testing. Journal of Systems and Software. 2017 Feb 1;124:1-21.
18. Shabestari, F., Rahmani, A. M., Navimipour, N. J., & Jabbehdari, S. (2019). A taxonomy of software-based and hardware-based approaches for energy efficiency management in the Hadoop. Journal of Network and Computer Applications, 126, 162-177.
19. Ashouraei, M., Khezr, S. N., Benlamri, R., & Navimipour, N. J. (2018, August). A new SLA-aware load balancing method in the cloud using an improved parallel task scheduling algorithm. In 2018 IEEE 6th International Conference on Future Internet of Things and Cloud (FiCloud) (pp. 71-76). IEEE.
20. Panahi, V., & Navimipour, N. J. (2019). Join query optimization in the distributed database system using an artificial bee colony algorithm and genetic operators. Concurrency and Computation: Practice and Experience, e5218.
21. Mirjalili, S. (2019). Genetic algorithm. In Evolutionary Algorithms and Neural Networks (pp. 43-55). Springer, Cham.
22. Malik, M., Neshatpour, K., Rafatirad, S., Joshi, R. V., Mohsenin, T., Ghasemzadeh, H., & Homayoun, H. (2019). Big vs little core for energy-efficient Hadoop computing. Journal of Parallel and Distributed Computing, 129, 110-124.

Full-Text:

فصلنامه علمي- پژوهشي

فناوري اطلاعات و ارتباطات ایران

سال دهم، شمارههای 37 و 38، پاییز و زمستان 1397

صص: 71 -84

$E:\E Drive\logo\iicta Logo0.JPG$

زمان‌بندی کارها در محیط‌های ابری با استفاده از چارچوب نگاشت – کاهش و الگوریتم ژنتیک

*سید نیما خضر *نیما جعفری نویمیپور

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

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

تاریخ دریافت: 04/10/1398 تاریخ پذیرش:16/03/1399

چكيده

زمان‌بندی وظایف یک جزء حیاتی هر سیستم توزیع‌شده همچون گرید، ابر و شبکههای نظیر به نظیر میباشد که وظایف را برای اجرا به منابع مناسب ارجاع میدهد. روشهای رایج در زمان‌بندی دارای معایبی از قبیل پیچیدگی زمانی بالا، هم‌زمان اجرا نشدن کارهای ورودی و افزایش زمان اجرای برنامه است. الگوریتمهای زمان‌بندی بر پایه اکتشاف جهت اولویت‌دهی به وظایف از
سیاستهای متفاوتی استفاده میکنند که باعث به وجود آمدن زمانهای اجرای بالا بر روی سیستمهای رایانش توزیعشده ناهمگن میشود. بنابراین، روشی مناسب است که اولویتدهی آن باعث تولید زمان اجرای کل کمینه گردد. الگوریتم ژنتیک به‌عنوان یکی از روش‌های تکاملی به‌منظور بهینه کردن مسائل NP-کامل¹ به کار گرفته میشود. در این مقاله الگوریتم ژنتیک موازی با استفاده از چارچوب نگاشت-کاهش برای زمان‌بندی وظایف بر روی رایانش ابری با استفاده از صفهای اولویت چندگانه ارائه‌شده است. ایده اصلی این مقاله، استفاده از چارچوب نگاشت-کاهش برای کاهش زمان اجرای کل برنامه میباشد. نتایج آزمایش‌ها بر روی
مجموعهای از گرافهای جهتدار بدون دور تصادفی حاکی از آن است که روش پیشنهادی زمان اجرای کل دو روش موجود را با سرعت همگرایی بالا بهبود داده است.

نویسندة عهده‌دار مکاتبات: نیما جعفری نویمیپور jafari@iaut.ac.ir

واژه‌های کلیدی: رایانش ابری، زمان‌بندی وظایف، کاهش زمان اجرا، الگوریتم ژنتیک، نگاشت-کاهش، هادوپ.

[1] . NP-Completeness

1- مقدمه

سیستمهای رایانش توزیعشده ناهمگن¹ نوعی از سیستمهای رایانش توزیعشده است که وظایف را روی چندین
پردازندههای اجرا میکند [1]. زمان‌بندی وظایف در محیط‌های ابری به مجموعه‌ای از زیر وظایف کوچک‌تر اولویتدار، جهت پردازش تجزیه میشود [2]. این زیروظایف نشان‌دهنده محدودیت تقدم² میباشند به این معنی که نتیجه دیگر وظایف قبل از اجرای زیر وظیفه فعلی نیاز است [2]. با تجزیه یک کار رایانش به زیر وظایف و اجرای آنها بر روی چندین پردازنده، زمان اتمام وظیفه میتواند کاهش پیدا کند. بنابراین هدف از این کار، زمان‌بندی زیروظایف بر روی تعدادی پردازنده در دسترس جهت کاهش زمان اتمام وظایف بدون نقض محدودیتهای تقدم میباشد [3]. توسعه³ الگوریتمهای زمان‌بندی وظایف که زیروظایف یک برنامه را به پردازندهها تخصیص میدهند، در سیستمهای ابری یک چالش میباشد. باوجود تلاشهای بسیاری که اخیراً در زمینة زمان‌بندی وظایف صورت گرفته است، همچنان این مسئله در محیطهای رایانش ناهمگن به‌عنوان یکی چالش مهم باقی‌مانده است [4]. تعدادی از چالشهای مهم زمان‌بندی وظایف در سیستمهای ابری در زیر آورده شده است:

· ناهمگن بودن منابع

· زمان اجرای الگوریتم⁴

· زمان اجرای کل⁵

· سرعت همگرایی⁶ راهحلها در روشهای تکاملی

· بهرهوری⁷ الگوریتم زمان‌بندی

با توجه به افزایش حجم داده‌ها در محیط ابری کاهش زمان اجرای الگوریتم زمان‌بندی همچنین به‌عنوان یک چالش مهم باقی‌مانده است. بنابراین الگوریتمهای گوناگونی جهت کاهش زمان اتمام وظایف با موازیسازی زیروظایف و رعایت رابطههای تقدم آن‌ها ارائه‌شده‌اند. معمولاً رابطههای تقدم با گراف جهتدار بدون دور ⁸نشان داده میشوند که از رأسها که نشان‌دهنده کارها و یالهای جهتدار نشانگر وابستگی بین کارها میباشد. گرافهای جهتدار بدون دور برای نشان دادن برنامهها با حجم زیاد و مختلف مناسب و گویا است [5]. از طرف دیگر سیستم هادوپ، اجرا وظایف را در یک مرکز داده مشترک را فراهم می کند[18]. نگاشت-کاهش یک ابزار مؤثر در هادوپ برای پردازش دادههای بزرگ در رایانش ابری می‌باشد که با استفاده از پردازندهها و یا کامپیوترها به‌صورت موازی دستورات و برنامه‌ها را اجرا مینماید [6]. این چهارچوب برنامه نویسی اجازه اجرای پردازش موازی و توزیع شده بروی مجموعه بزرگی از داده‌ها در یک محیط توزیع‌یافته را می‌دهد [16]. این چارچوب با رویکردها مختلفی ارائه‌شده است و در زمینه‌های مختلف کاربردهای مختلفی دارد ازجمله الگوریتم‌هایی که در دادههای بزرگ دارای پیچیدگی زمانی بالایی است که با بهبود پردازش به‌صورت موازی زمان اجرای الگوریتم را کاهش می‌دهد [7]. لذا این مقاله به چگونگی، زمان‌بندی کارهای اولویت‌دار بر روی گراف‌های مستقیم بدون دور بزرگ به کمک الگوریتم ژنتیک و چارچوب نگاشت-کاهش می‌پردازد.

به‌صورت خلاصه اهداف مقاله به‌صورت زیر است:

· استفاده از الگوریتم ژنتیک برای زمان‌بندی در محیط‌های ابری ناهمگن با استفاده چارچوب نگاشت-کاهش

· بهبود زمان اجرای کل برنامه

· افزایش سرعت همگرایی راهحلها و جلوگیری از همگرایی زودرس

ادامه مقاله به صورت زیر سازماندهی خواهد شد: در بخش 2 برخی از روش‎هاي مهم در زمان‌بندی کارها در محیط‌های ابری مورد مطالعه و بررسی قرار خواهد گرفت. در بخش 3 ساختار کلی و روش پیشنهادی با استفاده از چارچوب نگاشت-کاهش و الگوریتم ژنتیک نشان داده خواهد شد. در بخش 4 هم به بررسی نتایج بدست آمده و مقایسه روش پیشنهادی با روش‎های دیگر در زمان اجرای کل برنامه پرداخته خواهد شد. و در نهایت نتیجه گیری و پیشنهاد کارهای آتی نشان داده خواهد شد.

2-پیشینۀ تحقیق

در این بخش روشهای موجود در زمینه زمان‌بندی وظایف و بررسی مزایا و معایب این روشها دارد. همچنین بعد از بررسی روشهای موجود ایده اصلی روش زمان‌بندی پیشنهادی این مقاله شرح داده میشود. طبیعت چندهدفه در مسئله زمان‌بندی در ابر، حل آن مخصوصاً درزمانی که کارها زیاد و پیچیده میباشند را سخت میکند. در میان مسائل مختلف زمان‌بندی، زمان‌بندی ماشین با پردازنده‌های موازی یکی از مسائل بهینه‌سازی NP-سخت است. در مسئله زمان‌بندی پردازنده موازی، مجموعه‌ای از n کار وجود دارد (T1, T2, …, Tn)؛ هرکدام می‌توانند بر روی m پردازنده (P1, P2, …, Pm) پردازش شوند، هر کار باید با رعایت تقدم بر روی پردازنده پردازش شود. هر پردازنده فقط میتواند یک کار را در یک‌زمان معین پردازش کند. در ادامه چندین روش برای زمان‌بندی کارها در محیط‌های ابری بررسی خواهد شد.

پژوهشگران در مقاله [8] جهت رسیدن همزمان به دو معیار کارآیی بالا و زمان‌بندی سریع دو الگوریتم زمان‌بندی بر پایه لیست⁹ HEFT وCPOP ارائه دادهاند. الگوریتم HEFT در هر مرحله یک وظیفه با بیشترین ارزش رتبه رو به بالا¹⁰ را انتخاب و با استفاده از روش درج¹¹ به پردازندهای تخصیص میدهد که زودترین زمان شروع را کاهش دهد. درحالی‌که الگوریتم CPOP برای اولویتدهی از تجمیع مقدارهای رو به بالا و رو به پائین¹² به وظایف استفاده میکند. تفاوت دیگر این دو الگوریتم در قسمت انتخاب پردازنده به وظایف میباشد به‌طوری که الگوریتم CPOP وظایف موجود بر روی مسیر بحرانی را بر روی پردازندهای اجرا میکند که زمان اجرای کل وظایف مسیر بحرانی را کمینه کند. در مقاله [9] یک الگوریتم زمان‌بندی مبتنی بر الگوریتم کلونی مورچه ارائه‌شده است. هدف این زمان‌بند کمینه کردن زمان گردش مجموعهی کارها همزمان با کمینه کردن حداکثر زمان اتمام انجام کل کارها میباشد. این روش ارائه‌شده اجازه پرداختن به کارهای چابک‌تر درحالی‌که زمان تکمیل کاهش مییابد را میدهد. همچنین نتایج ارزیابی نشان میدهد که الگوریتم کلونی مورچه بهتر از الگوریتمهای تصادفی و بهترین تلاش عمل میکند. در مقاله [10] روشی در زمینه زمان‌بندی کارها در ابر خبره ارائه‌شده است. این روش دارای عملکرد سریع‌تر با دقت بالاتر و نرخ شکست پایین‌تر در مقایسه با روشهای بررسی‌شده میباشد. نتایج پیاده‌سازی نشانگر بهبود حداکثر 56 درصدی، 14 درصدی و 7.5 درصدی به ترتیب بر اساس معیارهای زمان کلی اجرا، نرخ شکست و کارایی منابع انسانی در مقایسه با روشهای دیگر میباشد. در مقاله [11] یک الگوریتم زمان‌بندی سطوح پویا ارائه‌شده است. نتایج شبیه‌سازی‌ها اثبات کردهاند که این الگوریتم میتواند به‌صورت کارا نیازهای جریان کار رایانش ابری را ازنظر اعتماد، کاهش هزینههای زمانی و اطمینان از اجرای کارها در یک حالت امن را تأمین کند. پژوهشگران در مقاله [12] یک روش زمان‌بندی وظایف در سیستمهای رایانش ناهمگن با استفاده از الگوریتم ژنتیک و صفهای اولویتدار چندگانه به نام MPQGA را ارائه کردهاند.

ایده اصلی روش ارائه‌شده به‌کارگیری مزیتهای هر دو نوع الگوریتم اکتشافی و تکاملی و اجتناب از ایرادات آن‌ها می‌باشد. روش ارائه‌شده الگوریتم ژنتیک را جهت تخصیص اولویت به هر وظیفه و روش اکتشافی EFT را جهت نگاشت¹³ وظایف به پردازندهها به کار گرفته است. همچنین روش MPQGA عملگرهای ترکیب، جهش و تابع برازندگی مناسبی را جهت زمان‌بندی گراف جهتدار بدون دور طراحی کرده است. نتایج شبیه‌سازی انجام‌شده بر روی گرافهای دنیای واقعی¹⁴ و تصادفی نشان میدهد که الگوریتم MPQGA دو روش غیرتکاملی و یک روش جستجوی تصادفی به نام ¹⁵ BGAرا بهبود بخشیده است. در این ادامه به مقایسه روش‌های موجود پرداخته‌شده است. در الگوریتمHEFT وظایف با استفاده از ارزش رو بالا انتخاب می‌شود و دارای همگرای متوسط می‌باشد، در روش CPOP وظایف با استفاده از ارزش رو بالا و پایین انتخاب می‌شود و مانندHEFT دارای سرعت همگرایی متوسط می‌باشد. در الگوریتم MPQGA که بهبودیافته الگوریتم HEFT است برای بهبود زمان‌بندی از الگوریتم ژنتیک استفاده‌شده است. جدول 1 الگوریتمهای موجود را از جنبه روش مورداستفاده، مزایا و معایب آن‌ها مورد مقایسه قرار میدهد.

جدول1: مقایسه روشهای بررسی‌شده برای زمان‌بندی کارها در محیط‌های ابری

زمان اجرا	مزایا	معایب	الگوریتمهای زمان‌بندی
متوسط	پیچیدگی کمتر	همگرایی کند، عدم تولید نتایج پایدار در مسائل با طیف گسترده	[8]
بالا	پیچیدگی و هزینه ارتباطی کمتر	نتایج نامناسب در گرافهای بر پایه محاسبات	[9]
متوسط	هزینه ارتباطی کمتر	همگرایی کند	[10]
متوسط	هزینه ارتباطی و اجرای کمتر	مناسب برای محیطهای همگن	[11]
متوسط	کارایی بهتر	همگرایی کند و پیچیدگی بیشتر	[12]

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

3-روش پیشنهادی

در این بخش به روش پیشنهادی پرداخته شده است. در ابتدا تعاریف متغییرهای ﻣﺴﺌﻠﻪ بیان شده است در ادامه به معرفی کردن الگوریتم ژنتیک برای ترکیب کردن خدمات ابری پرداخته شده است. در ادامه یک الگوریتم ژنتیک موازی جدید زمان‌بندی وظیفه با استفاده از چارچوب نگاشت-کاهش بر روی رایانش ابری با استفاده از صفهای اولویت چندگانه ارائه‌شده است.

1-3-تعاریف اولیه

روش پیشنهادی دارای یک مجموعه از پردازندههای ناهمگن P میباشد که توسط شبکه پرسرعت به همدیگر متصل شدهاند. در این روش مسئله زمان‌بندی وظایف توسط گراف جهتدار بدون دور G(V,E) نمایش داده‌شده است که شکل 1 نمونه ارائه‌شده در این مقاله را نشان میدهد.

شکل 1: گراف جهتدار بدون دور با 10 زیروظیفه [5]

بهطوری که V نشان‌دهنده زیروظایف برنامه و E نشان‌دهنده لبههای گراف است که وابستگیهای بین زیروظایف را مشخص می‌کنند. هر زیر وظیفه در گراف فقط بر روی یک پردازنده میتواند اجرا شود. مقدارهای لبهها نشانگر مقدار هزینه ارتباطی بین دو زیر وظیفه است و میانگین هزینه محاسباتی هر زیر وظیفه در پردازندهها بر روی هر گره مقدارگذاری شده است. جدول 2 نمادهای استفاده‌شده در رابطهها و الگوریتمهای این مقاله را توضیح میدهد.

جدول 2: نمادهای استفاده‌شده در روش پیشنهادی

درصورتی‌که دو زیر وظیفه متصل به یکدیگر بر روی پردازنده یکسان زمان‌بندی شوند هزینه ارتباطی بین آنها صفر در نظر گرفته میشود. گرههای شروع و خروجی گراف به ترتیب نشان‌دهنده شروع و پایان برنامه هستند. مدل استفاده برای الگوریتم پیشنهادی نامرتبط¹⁶ میباشد، بدین معنی که یک پردازنده ممکن است بعضی از وظایف را در زمان کمتر و بعضی دیگر را در زمان بیشتر اجرا کند که در جدول 3 نشان داده ‌شده است. همچنین برای شروع اجرای یک زیروظیفه میبایست تمام زیر وظایف تقدم¹⁷ آن زمان‌بندی و اجراشده باشند

جدول 3: هزینههای محاسباتی زیروظایف بر روی پردازندهها [17]

2-3-روش پیشنهادی

در این بخش ابتدا ساختار الگوریتم ژنتیک ارائه میشود. سپس به تشریح جزئیات روش پیشنهادی پرداخته خواهد شد. همچنین برای بهبود الگوریتم ژنتیک پیشنهادی از چارچوب برنامه‌نویسی نگاشت-کاهش استفاده‌شده است. الگوریتم تکاملی ژنتیک از عملگرهای مختلفی استفاده میکند که عملگرهای ژنتیک نامیده میشوند. این عملگرها باعث تولید کروموزومهایی بهتر از جمعیت اولیه میشوند. این عملگرها جهت همگرایی راهحلهای مسئله لازم و ضروری هستند [13]. یک الگوریتم ساده ژنتیک دارای سه عملگر اساسی ژنتیک است. این عملگرها شامل عملگرهای انتخاب، ترکیب و جهش هستند. عملگر انتخاب بعضی از راه حل ها را به عنوان والد از میان جمعیت انتخاب می کند. عملگر ترکیب والد های انتخاب شده را جهت تولید فرزندان جدید ترکیب می کند و عملگر جهش مطابق قوانین مشخص شده فرزندان را تغییر می دهد.

برای توسعه و پیاده‌سازی یک الگوریتم جدید زمان‌بندی وظایف، از ترکیب الگوریتم ژنتیک و چارچوب نگاشت-کاهش استفاده‌شده است. با تکنیک نگاشت-کاهش می‌توان الگوریتم‌ها را در فضای موازی پیاده‌سازی نمود. هادوپ ابزاری است که این تکنیک را پیاده‌سازی نموده است و برای هر الگوریتم تنها کافی است دو قسمت نگاشت و کاهش آن را پیاده‌سازی کنیم [22]. مراحل الگوریتم پیشنهادی در شکل 2 نمایش داده‌شده‌اند. الگوریتم پیشنهادی با مقداردهی جمعیت اولیه شروع می‌شود.

Nim a2

شکل 2: مراحل روش پیشنهادی

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

روش پیشنهادی زمان‌بندی وظایف را در دو مرحله انجام میدهد: در مرحله یکم به‌منظور تخصیص وظایف به پردازندهها از روش ژنتیک به همراه روشهای اکتشافی استفاده‌شده است و در مرحله دوم تخصیص وظایف به پردازندهها از روش ژنتیک به همراه چارچوب نگاشت-کاهش استفاده‌شده است. تابع اصلی الگوریتم پیشنهادی جهت زمان‌بندی کردن وظایف بر روی منابع ناهمگن در ابر است.

3-3-مقداردهی جمعیت اولیه

ساختن یک کروموزوم توسط روش رمزنگاری¹⁸ مرحله ابتدایی در مقداردهی جمعیت اولیه میباشد [19]. ساختمان کروموزوم الگوریتم پیشنهادی دارای ژن¹⁹ میباشد که نشاندهنده یک راهحل از مسئله زمان‌بندی وظایف میباشد [20]. ساختمان یک کروموزوم شامل یک جایگشت از اعداد طبیعی 0 تا n-1 میباشد که نشانگر ترتیب اولویت‌های وظایف در گراف جهتدار بدون دور با تعداد n میباشد. علاوه براین ترتیب اولویت وظایف در کروموزوم میبایست یک ترتیب توپولوژیکی معتبر باشد بطوریکه گره شروع بایستی در اول کروموزوم و گره پایانی در آخر کروموزوم قرار گیرد و همچنین سایر وظایف در مکانهایی از کروموزوم قرار گیرند که محدودیتهای تقدم وظایف را نقض نکنند. به‌منظور عملی بودن زمان‌بندی باید تمام زیر وظایف موجود در گراف زمان‌بندی شوند.

جدول 3: اولویتهای وظایف

نماد	شرح
ti	iامین زیر وظیفه در گراف
pk	k امین پردازنده در سیستم
E	مجموعه لبهها در گراف
T	مجموعه زیروظایف در گراف
P	مجموعه پردازندهها در سیستم
tentry	زیر وظیفه ورودی در گراف
texit	زیر وظیفه خروجی در گراف
Succ(ti)	مجموعه تأخرهای زیر وظیفه ti
Pred(ti)	مجموعه تقدمهای زیر وظیفه ti
	میانگین هزینه محاسباتی زیر وظیفه ti
	هزینه محاسباتی زیر وظیفه ti بر روی پردازنده pk
	مقدار هزینه ارتباطی بین وظایف ti و
	رتبه رو به بالای زیروظیفه ti
	رتبه رو به پایین زیروظیفه ti
Rankb+t(ti)	جمع رتبه روبه بالا و پایین زیروظیفه ti
	زودترین زمان شروع زیروظیفه ti بر روی پردازنده pk
	زودترین زمان پایان زیروظیفه ti بر روی پردازنده pk
i ,pk)	زمان شروع واقعی زیروظیفه ti بر روی پردازنده pk
i ,pk)	زمان پایان واقعی زیروظیفه ti بر روی پردازنده pk
	زمان بیکار و در دسترس بودن پردازنده pk
	مخفف کلمه انگلیسی جمعیت
PopSize	مخفف کلمه انگلیسی اندازه جمعیت
	مخفف کلمه انگلیسی اندازه کروموزوم

Subtask (ti)	Rankb	Rankt	Rankb+t	level
t0	129	0	123	0
t1	81	24	105	1
t2	78	23	101	1
t3	100	17	117	1
t4	99	30	129	1
t5	60	50	110	2
t6	67	52	119	2
t7	35	75	110	3
t8	42	77	119	3
t9	12	107	119	4

اندازه جمعیت اولیه الگوریتم پیشنهادی با نماد PopSize نمایش داده میشود و مقدار آن 4 برابر تعداد وظایف موجود در گراف است (n×4). اندازه جمعیت الگوریتم تا پایان یافتن الگوریتم ثابت است یعنی در طول تولید نسلهای جدید این مقدار تغییری نمیکند. در الگوریتم پیشنهادی به‌منظور داشتن تخمریزی²⁰ خوب در مقداردهی جمعیت اولیه از سه سیاست رتبهبندی اکتشافی بنامهای رتبه رو به بالا(رابطه (1))، رتبه رو به پایین (رابطه (2)) و ترکیبی از این دو روش با رتبه سطح (رابطه (3)) برای مقداردهی سه کروموزوم اول جمعیت استفاده‌شده است [12]. در جدول 3 با استفاده از سه سیاست رتبه‌بندی شده است. اولویتهای کروموزومهای باقیمانده با جایگشتهای تصادفی تولید میشوند. کروموزومهای تولیدشده تصادفی به دلیل اینکه اولویت‌هایشان معتبر نیست از سمت چپ به راست به‌طوری‌که زیروظایف محدودیتهای اولویت را نقض نکنند مرتبسازی میشوند. فرآیند تولید جمعیت اولیه درالگوریتم 1 نشان داده‌ شده است.

در این رابطه) میانگین هزینه محاسباتی وظیفه ti، مقدار هزینه ارتباطی بین وظایف ti وtj و رتبه رو به بالای تاخر زیر وظیفه ti است.

(1)

در این رابطه) رتبه رو به پایین زیر وظیفه تقدم ti است.

(2)

در این رابطه) رتبه سطح تقدم زیر وظیفه است.

(3)

الگوریتم 1: مقداردهی جمعیت اولیه

3-4-تخصیص زیروظایف به پردازندهها

در جمعیت اولیه تولیدشده هر کروموزوم باید دارای ترتیب اولویت معتبر باشد یعنی محدودیتهای تقدم در کروموزوم نقض نشود. در روش پیشنهادی به‌منظور تخصیص وظایف به پردازندهها از سیاست تخصیص پردازنده HEFT استفاده‌شده است [8]. در این روش زیروظیفه با بالاترین اولویت از بین زیروظایف کروموزوم انتخاب و به پردازندهای تخصیص داده میشود که زمان اجرای آن از سایر پردازندهها کمینه باشد. این روش تخصیص پردازنده از سیاست زمان‌بندی بر اساس درج استفاده میکند. در ادامه این بخش به تشریح این روش پرداخته‌شده است. زودترین زمان شروع زیر وظیفه ti بر روی پردازنده pk به‌صورت نمادگذاری میشود و از رابطه (4) به دست میآید.

Algorithm 1. Initial population

1: Initial three of the chromosomes by using three heuristic rank policies

2: for i=3 to PopSize-1 do

3: for j=0 to ChSize-1 do

4: generate a genes j randomly that not generated in pervious genes

5: move chromosome i from left to right in first valid place in the queue in order to has a valid topological order

6: end for

7: end for

زمان شروع واقعی زیر وظیفه ti بر روی پردازنده pk با نمادگذاری میشود و از رابطه (5) به دست میآید.

(4)

کهAvail (pk) زمانی است که پردازنده pk بیکار و آماده اجرای وظایف باشد. زودترین زمان پایان زیر وظیفه ti بر روی پردازنده pk با نمادگذاری شده است و از رابطه (6) محاسبه می‌شود.

(5)

که هزینه محاسباتی زیر وظیفه ti بر روی پردازنده pk است. زمان واقعی پایان زیر وظیفه ti بر روی پردازنده pk با نشان داده میشود و از رابطه (7) به دست می‌آید.

(6)

که pk در رابطه بالا مناسبترین²¹ پردازنده برای زیر وظیفه ti می‌باشد. شبه کد تخصیص وظایف به پردازنده‌ها در الگوریتم 2 در تشریح شده است.

(7)

الگوریتم 2 (تخصیص وظایف به پردازنده‌ها

3-5-تابع برازندگی

مقدار برازندگی کروموزومها در تصمیمگیری اینکه کدام کروموزومها به نسل آینده انتقال یابند بسیار مهم است. زمان پایان واقعی آخرین زیر وظیفه در گراف جهت‌دار بدون دور یا به عبارتی گره خروجی گراف زمان اجرای کل برنامه میباشد. زمان اجرای کل برنامه از رابطه (8) به دست میآید. که همان مقدار برازندگی کروموزوم i است.

Algorithm 2. Assigning subtasks to processors function

1: Fill the priority queue with subtasks

2: while the priority queue is not empty do

3: Select the first subtask ti from the priority queue

4: for each processor pk in the processor set do

5: Compute value using the insertion-based HEFT scheduling policy

6: Assign subtask ti to the processor pk that minimizes

7: end for

8: Remove ti from the priority queue

9: end while

10: Return makespan=.

مقدار برازندگی کوچک بیانگر کوتاه بودن زمان اجرای کل است. بنابراین بیشترین و کمترین مقدار برازندگی در میان جمعیت به ترتیب بدترین و بهترین کروموزومها هستند.

3-6-ترکیب

ترکیب، یک عملگر مهم در الگوریتم‌های ژنتیک است که به‌منظور ایجاد تغییر در کروموزوم‌های جمعیت مورداستفاده قرار میگیرد [21]. همچنین عملگر ترکیب به تکامل جمعیت در الگوریتمهای ژنتیک کمک میکند.

عملگر ادغام بیش از یک کروموزوم را برای تولید نسل جدید کروموزوم‌ها ترکیب میکند. کروموزوم جدید برخی ویژگی‌ها را از والد نخست و بقیه ویژگی‌ها را از والد دوم به ارث میبرد. الگوریتم 3 جزئیات عملگر ترکیب الگوریتم پیشنهادی را تشریح میکند.

(8)

Algorithm 3. Crossover operation

Input: Two parents from the current population.

Output: Two new offsprings

1: Choose randomly a suitable crossover point i

2: Cut the father’s chromosome and the mother’s chromosome into left and right segments

3: Generate a new offspring, namely the son

4: Inherit the left segment of the father’s chromosome to the left segment of the son’s chromosome

5: Copy genes in mother’s chromosome that do not appear in the left segment of father’s chromosome to the right segment of son’s chromosome

6: Generate a new offspring, namely the daughter

7: Inherit the left segment of the mother’s chromosome to the left segment of the daughter’s chromosome

8: Copy genes in father’s chromosome that do not appear in the left segment of mother’s chromosome to the right segment of daughter’s chromosome

9: Return the two new offsprings

الگوریتم 3: ترکیب تک نقطهای

در الگوریتم 4 عملگر تک نقطه‌ای به‌صورت چارچوب نگاشت-کاهش در آمده است به صورتی که هر عمکلر ترکیب به یک نگاشت تخصیص داده می شود.

Algorithm 4. Crossover Mapper

1: Run HDFS engine

2: Assign algorithm 5 to each mapper

3: Run the MapReduce job tracker

4: Start the calculation

5: Write the result into M blocks

6: Send the result to the shuffle phase

7: if all individuals have been processed successfully then Write best individual to global file in DFS

8: Copy and send the result to the Reducer

الگوریتم 4: ترکیب تک نقطهای با استفاده از چارچوب نگاشت-کاهش

3-7-جهش

عملگر جهش در الگوریتم ژنتیک برای نگه داشتن تنوع جمعیت بوسیله تغییر کروموزوم بکار میرود. بعد از اعمال عملگر تركيب به منظور اجتناب از همگرايي به بهينه محلي و ايجاد تنوع و گوناگوني درجمعيت با استفاده از عملگر جهش يك تعداد از كروموزومهاي به دست آمده تغيير داده
ميشوند. همچنین دو ژن برای انجام عملیات جهش تعریف میشوند. الگوریتم 5 جزئیات عملگر جهش الگوریتم پیشنهادی را تشریح میکند.

Algorithm 5. Mutation operation

Input: A randomly chosen chromosome.

Output: A new chromosome.

1: Choose randomly a gene Ti

2: Find the first successor Tj member Succ(i)

3: Choose randomly a gene Tk in the interval [i+1, j-1]

4: if l < i for all Tl member Pred(k) then

5: Generate a new offspring by interchanging gene Ti and gene Tk

6: return the new offspring

7: else

8: Go to Step 1

9: end if

الگوریتم 5) عملگر جهش

در الگوریتم 6 عملگر جهش به‌صورت چارچوب نگاشت-کاهش درآمده است به صورتی که هر عملگر ترکیب به یک نگاشت تخصیص داده می‌شود.

Algorithm 6. Mutation Reduce

1: Check the HDFS engine

2: Assign the result of algorithm 6 to each Reducer

3: Run the MapReduce job tracker

4: Start the calculation

5: Write the result into M blocks

6: Check the termination

7: if all individuals have been processed successfully then Write best individual to global file in DFS

8: Send the result to the cluster

الگوریتم 6) جهش با استفاده از چارچوب نگاشت-کاهش

3-8-انتخاب

در الگوریتم پیشنهادی به‌منظور انتخاب بعضی از کروموزومها برای الگوریتم جستجوی محلی از روش انتخاب چرخ رولت با پذیرش اتفاقی²² استفاده‌شده است [14]. این روش دارای پیچیدگی زمانی (1)o میباشد. این الگوریتم انتخاب دارای دو مرحله اصلی است: در مرحله اول یک کروموزوم به‌طور تصادفی از میان جمعیت انتخاب میشود که این انتخاب با احتمال (n/1) صورت میگیرد. در مرحله بعدی مقدار برازندگی کروموزوم ارزیابی‌شده و اگر کروموزوم انتخاب‌شده یکی از نخبههای جمعیت باشد برای جستجوی محلی انتخاب میشود در غیر این صورت کروموزوم انتخاب‌شده پذیرفته نمیشود و تابع انتخاب دوباره از مرحله 1 تکرار میشود. شبه کد روش انتخاب چرخ رولت با پذیرش اتفاقی در الگوریتم 7 آورده شده است.

الگوریتم 7: انتخاب چرخ رولت با پذیرش اتفاقی

9-3- شرط خاتمه

تفاوت اصلی بین تکامل طبیعت و مسئله در تکامل طبیعی میباشد که گونهها در طبیعت تمایل به خاتمه ندارند ولی در حل کردن یک مسئله با توجه به بودجه مشخص‌شده فرآیند را بایستی متوقف کرد [15]. روش‌های معمول مثل تنظیم یک محدودیت بر روی تعداد ارزیابی برازندگیها یا زمان ساعت کامپیوتر و یا دنبال کردن تنوع و توقف آن موقع کم شدن تنوع در جمعیت برای بررسی شرط خاتمه الگوریتمها وجود دارد [12]. در الگوریتم پیشنهادی شرط خاتمه موقعی اتفاق میافتد که تمام کروموزومها یا به عبارتی راه‌حل‌ها به یک مقدار برازندگی یکسان همگرا شوند.

4-نتایج شبیه سازی

در این قسمت روش پیشنهادی با دو الگوریتمMPQGA و جعفری نویمی پور و همکاران از جنبههای زمان کل اتمام کار و مصرف انرژی مقایسه شده است. نتایج آزمایش‌ها مقایسه الگوریتمها با استفاده از گراف جهتدار بدون دور و همچنین گرافهای جهت‌دار بدون دور تولیدشده تصادفی به‌دست‌آمده‌اند.

جدول 4: مشخصات خوشه‌های سخت‌افزاری و نرم‌افزاری در هادوپ

Algorithm 7. Roulette-wheel selection via stochastic acceptance

Input: A current population chromosome.

Output: A selected chromosome

1:do Generate a random number R [0,PopSize-1];

2: if then

3: return ;

4: end if

6: while (founding a one of the fittest solution).

نوع	سیستم‌عامل	پردازنده	حافظه
خوشه 1	ubuntu-14.04.2	4-core, 3.07 GHZ	4G
خوشه 2	ubuntu-14.04.2	4-core, 2.07 GHZ	4G
خوشه 3	ubuntu-14.04.2	4-core, 2.07 GHZ	4G
خوشه 4	ubuntu-14.04.2	4-core, 2.07 GHZ	4G

روش پیشنهادی و سایر الگوریتمها در زبان برنامه‌نویسی جاوا در محیط MapR پیاده‌سازی شدهاند و شبیهسازی و اجرای الگوریتمها بر روی چهار خوشه در جدول 4 با مشخصات زیر اجراشده است.

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

هزینههای محاسباتی و ارتباطی گرافها به‌صورت تصادفی از میان یک بازه انتخاب میشوند. شکل 3 زمانهای اجرای کل گراف تصادفی را با 50 زیر وظیفه و شکل 4 زمانهای اجرای کل گراف تصادفی را با 100 زیر وظیفه را نشان میدهند. با توجه به نتایج نمودارها در شکلها، مشهود است که روش پیشنهادی زمانهای اجرای دو الگوریتم MPQGA و جعفری نویمی پور و همکاران را همواره بهبود میبخشد. بهبود زمانهای اجرای کل گرافها با افزایش تعداد زیر وظایف مشهود است.

شکل 3: زمانهای اجرای کل برنامه با 50 کار

شکل 4: زمانهای اجرای کل برنامه با 100 کار

سدر روش پیشنهادی با استفاده از هادوپ و مدل نگاشت-کاهش کاهش انرژی مصرفی کل را در پی دارد. مصرف انرژی با دو الگوریتم MPQGA و جعفری نویمی پور و همکاران مقایسه شده است. شکل 5 مصرف انرژی با تعداد وظایف مختلف وظیفه را نشان میدهند. محور افقی برابر با تعداد وظایف و محور عمودی برابر مصرف انرژی وظایف در نظر گرفته می شود. در هر باراجرا، تعداد وظایف از 10 تا 50 متغیر فرض شده است که در هر بازه که سیستم اجرا میشود، مقادیر متفاوتی به دست میآید که در شکل 5 قابل مشاهده است.

شکل 5: مصرف انرژی با تعداد وظایف مختلف

5-نتیجه گیری و پیشنهاد کارهای آتی

زمان‌بندی در سیستمهای رایانش توزیعشده یک مسئله مهم میباشد و الگوریتمهای زمان‌بندی گوناگونی در این زمینه ارائه‌شده است. در این مقاله یک الگوریتم ژنتیک موازی با استفاده از چارچوب نگاشت-کاهش برای وظایف ایستا در سیستمهای رایانش ابری ارائه گردید. این الگوریتم با ترکیب الگوریتمهای ژنتیک استفاده از الگوریتم HEFT برای تخصیص زیروظایف به پردازندهها توسعه داده شد. نتایج بدست آمده بر روی یک گراف ساده و همچنین گرافهای تولیدشده تصادفی حاکی از آن است که الگوریتم ارائه‌شده از دو الگوریتم MPQGA و جعفری نویمی پور و همکاران در زمینه زمان اجرای کل بهینه عمل کرده است. لازم به ذکر است که هزینههای محاسباتی و ارتباطی گرافها به‌صورت تصادفی از بین یک بازه انتخاب میشوند از معایب این روش محسوب میشود. از طرف دیگر، نگاشت-کاهش برنامه نویسی سطح پایین است و برای بدست آوردن تابع نگاشت و کاهش باید کدهای زیادی استفاده کرد. در این مقاله مقایسههای الگوریتم پیشنهادی با سایر الگوریتمها بر روی گرافهای جهتدار بدون دور تصادفی و یک گراف ساده صورت گرفته است. به همین دلیل مطالعات بعدی در مورد الگوریتم پیشنهادی میتواند بر روی گرافهای جهان واقعی مانند FFT²³، Molecular dynamics code و غیره صورت گیرد. در شیوه نگاشت-کاهش که از سوی شرکت گوگل در سال 2004 معرفی‌شده است به‌طور مختصر همپوشانی در قسمت فازهای نگاشت و ارتباط دیده میشود. متأسفانه این همپوشانی²⁴ در نرم‌افزارهای نوشته‌شده به شیوه نگاشت-کاهش که دارای فاز ارتباط حجیم‌تری نسبت

منابع

1. Khemka, B., et al., Utility maximizing dynamic resource management in an oversubscribed energy-constrained heterogeneous computing system. Sustainable Computing: Informatics and Systems, 2015. 5: p. 14-30.

2. Arunarani, A.R., Manjula, D. and Sugumaran, V., 2019. Task scheduling techniques in cloud computing: A literature survey. Future Generation Computer Systems, 91, pp.407-415.

3. Zang, X., Sun, J., Zhao, J. and Zeng, W., 2018, May. Research Progress of Cloud Computing Task Scheduling Technology. In 2018 3rd International Conference on Automation, Mechanical Control and Computational Engineering (AMCCE 2018). Atlantis Press.

4. Young Choon, L. and A.Y. Zomaya, A Novel State Transition Method for Metaheuristic-Based Scheduling in Heterogeneous Computing Systems. Parallel and Distributed Systems, IEEE Transactions on, 2008. 19(9): p. 1215-1223.

5. Keshanchi, B. and Navimipour, N.J., 2016. Priority-based task scheduling in the cloud systems using a memetic algorithm. Journal of Circuits, Systems and Computers, 25(10), p.1650119.

6. Dean, J. and S. Ghemawat, MapReduce: a flexible data processing tool. Communications of the ACM, 2010. 53(1): p. 72-77.

7. Khezr, S.N. and Navimipour, N.J., 2017. MapReduce and its applications, challenges, and architecture: a comprehensive review and directions for future research. Journal of Grid Computing, 15(3), pp.295-321.

8. Topcuoglu, H., S. Hariri, and W. Min-You, Performance-effective and low-complexity task scheduling for heterogeneous computing. Parallel and Distributed Systems, IEEE Transactions on, 2002. 13(3): p. 260-274.

9. Mateos, C., E. Pacini, and C.G. Garino, An ACO-inspired algorithm for minimizing weighted flowtime in cloud-based parameter sweep experiments. Advances in Engineering Software, 2013. 56: p. 38-50.

10. Ashouraie, M. and N. Jafari Navimipour, Priority-based task scheduling on heterogeneous resources in the Expert Cloud. Kybernetes, 2015. 44(10): p. 1455-1471.

11. Wang, W., et al., Cloud-DLS: Dynamic trusted scheduling for Cloud computing. Expert Systems with Applications, 2012. 39(3): p. 2321-2329.

12. Xu, Y., et al., A genetic algorithm for task scheduling on heterogeneous computing systems using multiple priority queues. Information Sciences, 2014. 270(0): p. 255-287.

به فاز نگاشت می‌باشند تأثیری چندانی روی کاهش زمان پاسخ این نرم‌افزارها ندارد. اگر بتوان راهکارهایی ارائه دهیم که توانایی همپوشانی فازهای حجیم ارتباط و کاهش را در این‌گونه نرم‌افزارها را داشته باشد میتوان زمان بحرانی اجرای برنامه را کاهش داد و همچنین از منابع در دسترس حداکثر استفاده را نمود.

tool. Communications of the ACM, 2010. 53(1): p. 72-77.

9. Mateos, C., E. Pacini, and C.G. Garino, An ACO-inspired algorithm for minimizing weighted flowtime in cloud-based parameter sweep experiments. Advances in Engineering Software, 2013. 56: p. 38-50.

10. Ashouraie, M. and N. Jafari Navimipour, Priority-based task scheduling on heterogeneous resources in the Expert Cloud. Kybernetes, 2015. 44(10): p. 1455-1471.

11. Wang, W., et al., Cloud-DLS: Dynamic trusted scheduling for Cloud computing. Expert Systems with Applications, 2012. 39(3): p. 2321-2329.

12. Xu, Y., et al., A genetic algorithm for task scheduling on heterogeneous computing systems using multiple priority queues. Information Sciences, 2014. 270(0): p. 255-287.

, 2014. 270(0): p. 255-287.

13. Abed, I., et al., Optimization of the Time of Task Scheduling for Dual Manipulators using a Modified Electromagnetism-Like Algorithm and Genetic Algorithm. Arabian Journal for Science and Engineering, 2014. 39(8): p. 6269-6285.

14. Lipowski, A. and D. Lipowska, Roulette-wheel selection via stochastic acceptance. Physica A: Statistical Mechanics and its Applications, 2012. 391(6): p. 2193-2196.

15. Ong, B. and M. Fukushima, Genetic algorithm with automatic termination and search space rotation. Memetic Computing, 2011. 3(2): p. 111-127.

16. Hashem, Ibrahim Abaker Targio, Nor Badrul Anuar, Mohsen Marjani, Ejaz Ahmed, Haruna Chiroma, Ahmad Firdaus, Muhamad Taufik Abdullah et al. "MapReduce scheduling algorithms: a review." The Journal of Supercomputing (2018): 1-31.

17. Keshanchi B, Souri A, Navimipour NJ. An improved genetic algorithm for task scheduling in the cloud environments using the priority queues: formal verification, simulation, and statistical testing. Journal of Systems and Software. 2017 Feb 1;124:1-21.

18. Shabestari, F., Rahmani, A. M., Navimipour, N. J., & Jabbehdari, S. (2019). A taxonomy of software-based and hardware-based approaches for energy efficiency management in the Hadoop. Journal of Network and Computer Applications, 126, 162-177.

19. Ashouraei, M., Khezr, S. N., Benlamri, R., & Navimipour, N. J. (2018, August). A new SLA-aware load balancing method in the cloud using an improved parallel task scheduling algorithm. In 2018 IEEE 6th International Conference on Future Internet of Things and Cloud (FiCloud) (pp. 71-76). IEEE.

20. Panahi, V., & Navimipour, N. J. (2019). Join query optimization in the distributed database system using an artificial bee colony algorithm and genetic operators. Concurrency and Computation: Practice and Experience, e5218.

21. Mirjalili, S. (2019). Genetic algorithm. In Evolutionary Algorithms and Neural Networks (pp. 43-55). Springer, Cham.

22. Malik, M., Neshatpour, K., Rafatirad, S., Joshi, R. V., Mohsenin, T., Ghasemzadeh, H., & Homayoun, H. (2019). Big vs little core for energy-efficient Hadoop computing. Journal of Parallel and Distributed Computing, 129, 110-124.

[1] . Heterogeneous distributed computing systems

[2] . Precedence constraint

[3] . Development

[4] . Execution time

[5] . Makespan

[6] . Convergence speed

[7] . Efficiency

[8] . Directed acyclic graph

[9] . List-based scheduling

[10] . Upward rank

[11] . Insertion-based approach

[12] . Downward rank

[13] .Mapping

[14] . Real world graphs

[15] Basic genetic algorithm

[16] . Unrelated

[17] . Precedence

[18] . Encoding

[19] . Genes

[20] . Seeding

[21] .Fittest

[22] . Roulette-wheel selection via stochastic acceptance

[23] . Fast Fourier transformation

[24] . Overlapping

Share To

Article Url

Scheduling tasks in cloud environments using mapping framework - reduction and genetic algorithm