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

Using the discrete forest optimization algorithm for the problem of scheduling independent jobs on computational grids
Tác giả: ThS. Đỗ 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. Đó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: 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:

The Computational Grid (CG) is a new problem which has appeared recently. The scheduling of independent jobs on CG for the purpose of minimizing makespan is difficult but fascinating. To solve this problem as well as problems in the field of optimization, there has been the latest contribution to the group of well-known evolutionary algorithms such as Genetic Algorithm (GA), Particle Swarm Optimization (PSO), Ant Colony Optimization (ACO), Forest Optimization Algorithm (FOA) [1],... This paper introduces a revised FOA and applies it to the solution of the problem of independent job scheduling on CG with the goal of minimizingmakespan. The results show that FOA is also a good algorithm for solving the above optimization problem.

Keywords: FOA; computational grid; independent job; scheduling; makespan.

Các bài báo khác của tác giả được đăng trên tạp chí

Số thứ tự Bài báo Tạp chí Trang Ngày đăng
113(04) - 201411320-12-14