Date Log
SỬ DỤNG GIẢI THUẬT TỐI ƯU HÓA RỪNG CÂY RỜI RẠC CHO BÀI TOÁN LẬP LỊCH CÁC CÔNG VIỆC ĐỘC LẬP TRONG LƯỚI TÍNH TOÁN
Corresponding Author(s) : Đỗ Vĩnh Trúc
Tạp chí Khoa học Xã hội, Nhân văn và Giáo dục,
T. 5 S. 1 (2015): TẠP CHÍ KHOA HỌC XÃ HỘI, NHÂN VĂN VÀ GIÁO DỤC
Tóm tắt
Lưới tính toán (Computational Grid-CG) là bài toán mới xuất hiện gần đây. Việc lập lịch (scheduling) với các công việc độc lập (independent jobs) trên CG với mục tiêu cực tiểu makespan là bài toán khó nhưng hấp dẫn. Đóng góp mới nhất vào nhóm các giải thuật tiến hóa nổi tiếng như giải thuật di truyền (Genetic Algorithm-GA), tối ưu bầy đàn (Particle Swarm Optimization-PSO), giải thuật tối ưu hóa đàn kiến (Ant Colony Optimization-ACO)… để giải quyết bài toán này cũng như các bài toán trong lĩnh vực tối ưu hóa là tối ưu hóa rừng cây (Forest Optimization Algorithm-FOA) [1]. Đề tài này giới thiệu thuật toán FOA có hiệu chỉnh và áp dụng để giải quyết bài toán lập lịch các công việc độc lập trên lưới tính toán với mục tiêu cực tiểu hóa makespan. Kết quả cho thấy FOA có thể áp dụng tốt cho việc giải bài toán tối ưu hóa trên.
Từ khóa
Tải về trích dẫn
Endnote/Zotero/Mendeley (RIS)BibTeX
-
[1] M. Ghaemi and M.-R. Feizi-Derakhshi (2014), “Forest Optimization Algorithm”, Expert Systems with Applications, vol. 41, no. 15, pp. 6676–6687, Nov. 2014.
[2] H. Liu, A. Abrahamc, and A. E. Hassanien (2010), “Scheduling jobs on computational grids using a fuzzy particle swarm optimisation algorithm”, Future Generation Computer Systems, vol. 26, pp. 1336–1343.
[3] F. Xhafa, J. Carretero, B. Dorronsoro, and E. Alba (2009), “A tabu search algorithm for scheduling independent jobs in computational grids”, Computing and informatics, vol. 28, no. 2, pp. 237–250.
[4] I. Foster, C. Kesselman, and S. Tuecke (2001), “The anatomy of the grid,” Berman et al.[2], pp. 171–197.
[5] F. Dong and S. G. Akl (2006), “Scheduling algorithms for grid computing: State of the art and open problems”, Technical report.
[6] I. Foster and C. Kesselman (2003), The Grid 2: Blueprint for a New Computing Infrastructure. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc.
[7] E.-G. Talbi and A. Y. Zomaya, Eds. (2007), “Wiley Series on Bioinformatics: Computational Techniques and Engineering”, in Grid Computing for Bioinformatics and Computational Biology, John Wiley & Sons, Inc, pp. 393–393.
[8] S. B. Nguyen, M. Zhang, and others (2014), “A hybrid discrete particle swarm optimisation method for grid computation scheduling”, in Evolutionary Computation (CEC), 2014 IEEE Congress on, pp. 483–490.
[9] Howard Jay Siegel Tracy D. Braun and N. Beck (2001), “A Comparison of Eleven Static Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed Computing Systems”, Journal of Parallel and Distributed Computing, vol. 61, pp. 810–837.
[10] A. J. Page and T. J. Naughton (2005), “Framework for Task Scheduling in Heterogeneous Distributed Computing Using Genetic Algorithms”, Artif Intell Rev, vol. 24, no. 3–4, pp. 415–429.
[11] G. Ritchie and J. Levine (2003), “A hybrid ant algorithm for scheduling independent jobs in heterogeneous computing environments”.
[12] J. L. Graham Ritchie, “A fast, effective local search for scheduling independent jobs” in heterogeneous computing environments.
[13] F. Xhafa, E. Alba, and B. Dorronsoro (2007), “Efficient Batch Job Scheduling in Grids using Cellular Memetic Algorithms,” in Parallel and Distributed Processing Symposium, 2007. IPDPS 2007. IEEE International, pp. 1–8.
[14] A. YarKhan and J. J. Dongarra (2002), “Experiments with Scheduling Using Simulated Annealing in a Grid Environment”, in Grid Computing — GRID 2002, M. Parashar, Ed. Springer Berlin Heidelberg, pp. 232–242.
[15] H. Izakian and A. Abraham, Performance Comparison of Six Efficient Pure Heuristics for Scheduling Meta-Tasks on Heterogeneous Distributed Environments.
[16] A. Abraham, R. Buyya, and B. Nath (2000), “Nature’s Heuristics for Scheduling Jobs on Computational Grids”, in ieee international conference on advanced computing and communications, pp. 45–52.
[17] H. Izakian, B. T. Ladani, A. Abraham, and V´aclav Sn´aˇsel (2010), “A Discrete Particle Swarm Optimization Approach for Grid Job Scheduling,” International Journal of Innovative Computing, Information and Control, vol. 6, no. 9.