TAILIEUCHUNG - 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 với tìm kiếm cục bộ

Đề tài này giới thiệu thuật toán tối ưu hóa rừng cây (Forest Optimization Algorithm – 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 (thời gian bắt đầu và kết thúc công việc). Kết quả cho thấy FOA áp dụng tốt cho việc giải bài toán tối ưu hóa trên. | TẠP CHÍ KHOA HỌC ĐHSP TPHCM Đỗ Vĩnh Trủc 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 với tìm kiếm cục bộ ĐỖ VĨNH TRÚ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. Đề tài này giới thiệu thuật toán tối ưu hóa rừng cây Forest Optimization Algorithm - FOA 5 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 thời gian bắt đầu và kết thúc công việc . Kết quả cho thấy FOA áp dụng tốt cho việc giải bài toán tối ưu hóa trên. Từ khóa giải thuật tối ưu hóa rừng cây lưới tính toán công việc độc lập lập lịch makespan. ABSTRACT Using discrete forest optimization algorithm for independent jobs scheduling on computational grids with local search Computational Grid CG is a new problem that has appeared recently. Independent jobs scheduling on CG with the goal of minimizing makespan is a very difficult but fascinating problem. This topic introduces hybrid FOA Forest Optimization Algorithm 5 to solve the independent jobs scheduling on CG with the goal of minimizing makespan. The results show that FOA is also a good algorithm for solving the optimization problem. Keywords FOA Computational grid Independent job Scheduling Makespan. 1. Giới thiệu Một CG là một hệ tính toán phân tán theo địa lí bao gồm một tập hợp các tài nguyên máy tính đa dạng quy mô rộng lớn và độc lập 8 15 4 2 chúng được nối kết với nhau bởi các mạng băng thông cao 3 . Việc chia sẻ các công việc tính toán là một ứng dụng chính của tính toán lưới. Trong một CG các nguồn tài nguyên năng động đa dạng và có thể được thêm vào và rút ra bất kì lúc nào. CG được coi là một tiếp cận hiệu quả để giải quyết các ứng dụng của thế giới thực phân tán quy mô lớn 12 . Lập điều độ trong môi trường CG có nghĩa là phân

• Toán học
• Giải thuật tối ưu hóa rừng cây
• Lưới tính toán
• Công việc độc lập
• Bài toán lập lịch
• Giải thuật FOA
• Gieo mầm cục bộ
• Cực tiểu hóa makespan
• Thuật toán FOA
• Giải thuật tối ưu hóa đàn kiến