Toán tử lân cận mới cho thuật toán Tabu Search và PSO giải bài toán lập lịch luồng công việc trong môi trường điện toán đám mây
Abstract
Điện toán đám mây là xu thế mới của công nghệ thông tin và truyền thông. Trong mô hình điện toán đám mây mọi khả năng liên quan đến công nghệ thông tin đều được cung cấp dưới dạng dịch vụ, cho phép người sử dụng truy cập đến các dịch vụ công nghệ (phần cứng và phần mềm) từ các nhà cung cấp dịch vụ. Điện toán đám mây là sự tập hợp của nhiều máy chủ vật lý và máy chủ ảo, được cấu hình để làm việc với nhau trên môi trường mạng Internet. Một trong số các vấn đề lớn nhất trong môi trường điện toán đám mây là bài toán lập lịch luồng công việc. Hiệu năng của các hệ thống điện toán đám mây phụ thuộc rất nhiều vào việc sắp xếp các tác vụ trong luồng thực thi trên các máy tính trong môi trường đám mây để hoàn thành luồng công việc một cách tối ưu. Trong bài báo này chúng tôi đề xuất một thuật toán lập lịch luồng công việc mới dựa trên chiến lược tối ưu bày đàn và tìm kiếm Tabu.
References
J. D. Ullman, “NP-complete scheduling problems,” Journal of Computer and System sciences, vol. 10, no. 3, pp. 384– 393, 1975.
G. B. Berriman, E. Deelman, J. C. Good, J. C. Jacob, D. S. Katz, C. Kesselman et al., “Montage: a grid-enabled engine for delivering custom science-grade mosaics on demand,” in Optimizing Scientific Return for Astronomy through Information Technologies, vol. 5493, 2004, pp. 221–232.
P. Maechling, E. Deelman, L. Zhao, R. Graves, G. Mehta, N. Gupta et al., “SCEC CyberShake workflows—automating probabilistic seismic hazard analysis calculations,” in Workflows for e-Science. Springer, 2007, pp. 143–163.
USC Epigenome Center. [Online]. Available: http://epigenome.usc.edu.
LIGO - Laser Interferometer Gravitational Wave Observatory. [Online]. Available: http://www.ligo.caltech.edu.
R. Buyya, R. Ranjan, and R. N. Calheiros, “Modeling and simulation of scalable cloud computing environments and the CloudSim toolkit: Challenges and opportunities,” in IEEE International Conference on High Performance Computing & Simulation, 2009, pp. 1–11.
K. Dubey, M. Kumar, and S. Sharma, “Modified HEFT algorithm for task scheduling in cloud environment,” Procedia Computer Science, vol. 125, pp. 725–732, 2018.
A. M. Manasrah and H. Ba Ali, “Workflow scheduling using hybrid GA-PSO algorithm in cloud computing,” Wireless Communications and Mobile Computing, vol. 2018, no. 1934784, pp. 1–16, 2018.
N. Grigoreva, “Branch and bound method for scheduling precedence constrained tasks on parallel identical processors,” in Proceedings of The World Congress on Engineering, 2014, pp. 832–836.
R. Rajavel and T. Mala, “Achieving service level agreement in cloud environment using job prioritization in hierarchical scheduling,” in International Conf. on Information Systems Design and Intelligent Applications, 2012, pp. 547–554.
S. Singh and M. Kalra, “Task scheduling optimization of independent tasks in cloud computing using enhanced genetic algorithm,” Int’l J. Application or Innovation in Engineering & Management, vol. 3, no. 7, pp. 2319–4847, 2014.
S. Pandey, L. Wu, S. M. Guru, and R. Buyya, “A particle swarm optimization-based heuristic for scheduling workflow applications in cloud computing environments,” in IEEE International Conference on Advanced Information Networking and Applications, 2010, pp. 400–407.
Q. Cao, Z.-B. Wei, and W.-M. Gong, “An optimized algorithm for task scheduling based on activity based costing in cloud computing,” in IEEE International Conference on Bioinformatics and Biomedical Engineering, 2009, pp. 1–3.
F. Glover, “Tabu search– part I,” ORSA Journal on Computing, vol. 1, no. 3, pp. 190–206, 1989.
D. de Werra and A. Hertz, “Tabu search techniques: A tutorial and an application to neural networks,” Operations Research Spektrum, vol. 11, no. 3, pp. 131–141, 1989.
J. Vliet and F. Paganelli, Programming Amazon EC2. O’Reilly Media, Inc, 2011.
Q. Jiang, Y. C. Lee, M. Arenaz, L. M. Leslie, and A. Y. Zomaya, “Optimizing scientific workflows in the cloud: A Montage example,” in IEEE International Conference on Utility and Cloud Computing, 2014, pp. 517–522.
R. Kaur and S. Kinger, “Enhanced genetic algorithm based task scheduling in cloud computing,” International Journal of Computer Applications, vol. 101, no. 14, pp. 1–6, 2014.
E. Upfal, Probability and computing: Randomized algorithms and probabilistic analysis. Cambridge University Press, 2005.
