بهینه‌سازی چند هدفه‌ی مسئله‌ی زمان‌بندی کار در پردازش ابری

نویسندگان
ابوذر زندوکیلی 1
نجمه منصوری 2
محمد‌مسعود جاویدی 3
1 دانشجوی کارشناسی ارشد،علوم کامپیوتر،دانشکده ریاضی و کامپیوتر، دانشگاه شهید باهنر، کرمان، ایران
2 استادیار،دانشکده ریاضی و کامپیوتر، دانشگاه شهید باهنر، کرمان، ایران
3 دانشیار،دانشکده ریاضی و کامپیوتر، دانشگاه شهید باهنر، کرمان، ایران
چکیده
در محیط ابر، زمان‌بندی بهینه کارها، به عوامل زیادی همچون زمان اتمام کارها، تاخیر و تعادل بار روی ماشین‌ها بستگی دارد. اما توجه اصلی سایر مقالات انجام شده فقط به کمینه کردن زمان اتمام کارهاست. در این مقاله، پارامترهای موثر بر کیفیت خدمات یعنی کمینه‌ی زمان اتمام کارها، کمینه‌ی میزان دیرکرد از موعد تحویل و بیشینه‌ی تعادل بار روی ماشین‌ها به عنوان توابع هدف، همزمان در نظر گرفته شده است. زمان‌بندی جزء مسائل پیچیده‌ای است که برای آن، راه‌حل از مرتبه‌ی چندجمله‌ای وجود ندارد و به همین دلیل از الگوریتم‌های فرا اکتشافی مانند بهینه‌سازی گروه ذرات، شبیه‌سازی حرارت، جستجوی ممنوعه و الگوریتم ژنتیک چندهدفه استفاده شده است. نتایج شبیه‌سازی نشان داده است که بین الگوریتم‌های تک‌هدفه، الگوریتم بهینه‌سازی گروه ذرات در زمان کمتری اجرا شده و حتی برای تعداد 30 کار، از نظر بهینه‌سازی تابع هدف، قابل رقابت با الگوریتم‌های چندهدفه می‌باشد. در تعداد کار زیاد، الگوریتم‌های
چندهدفه، از نظر مدت زمان اجرا و همچنین بهینه‌سازی توابع هدف، مناسب‌ترند. زیرا الگوریتم ژنتیک مرتب‌شده یا رتبه‌بندی‌شده‌ی نامغلوب، توابع هدف را به صورت مجزا در نظر گرفته و بنابراین امکان انتخاب جواب‎‎‌های مطلوب را میان جواب‌های غیر برتر در راستای مصالحه بین اهدف مختلف را دارد.

کلیدواژه‌ها

  • [1] P. Helo, Y. Hao, R. Toshev and V. Boldosova, “Cloud manufacturing ecosystem analysis and design,” Robotics and Computer Integrated Manufacturing, 2021.
  • [2] D. Mrozek, “A Review of cloud computing technologies for comprehensive microRNA analyses,” Computational Biology and Chemistry, 2020.
  • [3] M. Lavanya, B. Shanthi and S. Saravanan, ”Multi objective task scheduling algorithm based on SLA and processing time suitable for cloud environment,” Computer Communications, Vol. 67, 2020.
  • [4] N. Mansouri and M. M. Javidi, “Cost-based job scheduling strategy in cloud computing environments,” Distributed and Parallel Databases, Vol. 18, pp. 365-400, 2020.
  • [5] H. Emmons, “One-machine sequencing to minimize certain functions of job tardiness,” Operations Research, Vol. 17, pp. 701–715, 1969.
  • [6] E.L. Lawler, “Efficient implementation of dynamic programming algorithms for sequencing problems,” Report BW 106, Mathematisch Centrum, Amsterdam, 1979,
  • [7] M.L. Fisher, “A dual algorithm for the one machine scheduling problem,” Mathematical Programming, Vol. 11, pp. 229–252, 1976.
  • [8] C.N. Potts and L.N. Van Wassenhove, “A branch and bound algorithm for the total weighted tardiness problem,” Operations Research, Vol. 33, pp. 177–181, 1985.
  • [9] M.S. Akturk and M.B. Yildirim, “A new lower bounding scheme for the total weighted tardiness problem,” Computers and Operations Research, Vol. 25, pp. 265–278, 1998.
  • [10] W. Bozejko, J. Grabowski and M. Wodecki, “Block approach-tabu search algorithm for single machine total weighted tardiness problem,” Computers & Industrial Engineering, Vol. 50, pp. 1–14, 2006.
  • [11] M. Srinivas and L.M. Patnaik, “Genetic algorithms: a survay,” computer, Vol. 27, pp. 17-26, 1994.
  • [12] T. Kellegoz, B. Toklu and J. Wilson, “Comparing efficiencies of genetic crossover operators for one machine total weighted tardiness problem,” Elsesier Applied Mathematics and Computation, Vol. 199, pp. 590–598, 2008.
  • [13] Y. Xing, Zh. Chen and J. Sun, “An improved adaptive genetic algorithm for job-shop scheduling problem,” Third International Conference on Natural Computation (IEEE ICNC 2007), 2007.
  • [14] Y. Xing and Zh.Wang, “An improved genetic algorithm with recurrent Search for the job-shop scheduling problem,” The 6th World Congress on Intelligent Control and Automation IEEE, 2006.
  • [15] S.M. Kamrul Hasan, R. Sarker and D. Cornforth, “Hybrid genetic algorithm for solving iob-shop scheduling problem,” 6th IEEE/ACIS International Conference on Computer and Information Science (IEEE ICIS 2007), 2007.
  • [16] Y. Tsujimura, Y. Mafune and M. Gen, “Effects of symbiotic evolution in genetic algorithms for job-shop scheduling,” Proceedings of the 34th Hawaii International Conference on System Sciences IEEE, 2001.
  • [17] A. Tariq, I. Hussain and A. Ghafoor, “A hybrid genetic akgorithm for job shop scheduling,” Proceedings of the 37th International Conference on Computers and Industrial Engineering October 20-23, 2007.
  • [18] F. Hemasian Etefagh and F. Safi Esfahani, “Dynamic scheduling applying new population grouping of whales meta heuristic in cloud computing,” The Journal of Supercomputing, 2019.
  • [19] Sh. Torabi and F. Safi-Esfahani, “A dynamic task scheduling framework based on chicken swarm and improved raven roosting optimization methods in cloud computing,” The Journal of Supercomputing, 2018.
  • [20] M. Agarwal and G. M. Saran Srivastava, “A cuckoo search algorithm-based task scheduling in cloud computing,” advances in intelligent systems and computing, 2018.
  • [21] J. Li and Y. Han, “A hybrid multi-objective artificial bee colony algorithm for flexible task scheduling problems in cloud computing system,” Cluster Computing, 2018.
  • [22] J. P. Buanga Mapetu, Zh. Chen and L. Kong, “Low-time complexity and low-cost binary particle swarm optimization algorithm for task scheduling and load balancing in cloud computing,” Applied Intelligence, 2019.
  • [23] A. M. Senthil Kumar and M. Venkatesan, “Task scheduling in a cloud computing environment using HGPSO algorithm,” Cluster Computing, 2018.
  • [24] X. Chen and D. Long, “Task scheduling of cloud computing using integrated particle swarm algorithm and ant colony algorithm,” Cluster Comput, 2017.
  • [25] S. J. Nirmala and S. M. S. Bhanu, “Catfish-PSO based scheduling of scientific workflows in IaaS cloud,” Computing, 2016.
  • [26] W. Chen, E. Deelman, “WorkflowSim: a toolkit for simulating scientific workflows in distributed environments,” In: Proceedings of IEEE 8th international conference on e-Science (e-Science), 8–12 October 2012, Hyatt Regency Chicago, Chicago, Illinois, USA, pp 1–8, 2012.
  • [27] R.N. Calheiros, R. Ranjan, A. Beloglazov, “CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms,” Software: Practice and Experience, Vol. 41(1):pp. 23–50, 2011.
  • [28] M. Kumar and S. C. Sharma, “PSO-based novel resource scheduling technique to improve QoS parameters in cloud computing,” Neural Computing and Applications, Vo. 32, pp. 12103-12126, 2020.
  • [29] Z. Zhou, F. Li, H. Zhu, H. Xie, J. H. Abawajy and M. U. Chowdhury, “An improved genetic algorithm using greedy strategy toward task scheduling optimization in cloud environments,” Neural Computing and Applications, Vol. 32, pp. 1531-1541, 2020.
  • [30] Y. Gu, Ch. Budati, “Energy-aware workflow scheduling and optimization in clouds using bat algorithm,” Future Generation Computer Systems, Vol. 113, pp.106-112, 2020.
  • [31] X. Chen, L. Cheng, C. Liu, Q. Liu, J. Liu, Y. Mao, J. Murphy, “A WOA-based optimization approach for task scheduling in cloud computing systems,” IEEE Systems Journal, Vol. 14(3), 2020.
  • [32] Zh. He, J. Dong, Zh. li, W. Guo, “Research on task scheduling strategy optimization based on ACO in cloud computing environment,” IEEE 5th Information Technology and Mechatronics Engineering Conference (ITOEC), 2020.
  • [33] Z. Zong, “An improvement of task scheduling algorithms for green cloud computing,” The 15th International Conference on Computer Science & Education (ICCSE), 2020 August 18-20, 2020.
  • [34] S. P. M. Ziyath and S. Senthilkumar, “MHO: Meta heuristic optimization applied task scheduling with load balancing technique for cloud infrastructure services,” Journal of Ambient Intelligence and Humanized Computing, 2020.
  • [35] A. S. Ajeena Beegom and M. S. Rajasree, “Integer PSO: a discrete PSO algorithm for task scheduling in cloud computing systems,” Evolutionary Intelligence, 2019.
  • [36] Y. Dai, Y. Lou and X. Lu, ”A task scheduling algorithm based on genetic algorithm and ant colony optimization algorithm with multi-QoS constraints in cloud computing,” 7th International Conference on Intelligent Human-Machine Systems and Cybernetics, 2015.
  • [37] Sh. Su and H. Yu, “Authors Info & Affiliations Minimizing tardiness in data aggregation scheduling with due date consideration for single-hop wireless sensor networks,” Wireless Networks, Vol. 21, pp. 1259-1273 , 2015.
  • [38] D. E. Akyol and G. M. Bayhan, “Multi-machine earliness and tardiness scheduling problem: an interconnected neural network approach,” The International Journal of Advanced Manufacturing Technology, Vol. 37, pp. 576-588, 2008.
  • [39] J. Kennedy and R. C. Eberhart, "Particle Swarm Optimization," IEEE International Conference on Neural Networks (Perth, Australia), IEEE Service Center, Piscataway, NJ, 1995, Vol. IV, 1942-1948.
  • [40] S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi, “Optimization by Simulated Annealing,” Science, New Series, Vol. 220, 671-680, 1983.
  • [41] V. Cerny, “Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm,” journal of optimization theory and applications, Vol. 45, pp. 41-51, 1953.
  • [42] F. Glover, “Future paths for integer programming and links to artificial inteligence,” Computers and Operations Research, Vol. 13, pp. 533–549, 1986.
  • [43] K. Deb, “A fast and elitist multiobjective genetic algorithm: NSGA-II,” IEEE transactions on evelutionary computation, Vol. 6, pp. 182-197, 2002
علوم رایانش و فناوری اطلاعات
دوره 18، شماره 2
پاییز و زمستان
پاییز 1399