Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Bài viết này đề xuất một thuật toán lập lịch áp dụng cho các luồng công việc trong môi trường điện toán đám mây trong đó sử dụng phương pháp nhánh cận để cực tiểu hóa hàm mục tiêu là chi phí thực thi luồng công việc. | Phương pháp nhánh cận cho bài toán lập lịch luồng công việc Nghiên cứu khoa học công nghệ PHƯƠNG PHÁP NHÁNH CẬN CHO BÀI TOÁN LẬP LỊCH LUỒNG CÔNG VIỆC Đặng Quốc Hữu1, Phan Thanh Toàn2, Nguyễn Thế Lộc3, Nguyễn Doãn Cường4* Tóm tắt: Trong khoa học và thực tế có nhiều quy trình làm việc tồn tại dưới dạng luồng công việc như dây chuyền lắp ráp công nghiệp, dây chuyền dệt may, các tác vụ trong hệ điều hành,. Những quy trình như vậy đòi hỏi phải được tổ chức sao cho hiệu quả nhất, thuật ngữ chuyên môn gọi việc đó là lập lịch. Đó là hoạt động nhằm gán các tác vụ cho các tài nguyên tính toán sao cho việc thực thi tác vụ đạt hiệu quả cao nhất đồng thời thỏa mãn các ràng buộc về thứ tự thực hiện các tác vụ trong luồng công việc cũng như không vượt quá giới hạn về tài nguyên. Nhiều bài toán thuộc họ lập lịch đã được chứng minh là thuộc lớp NP-Khó [1], tuy nhiên do vai trò quan trọng trong thực tiễn nên chúng vẫn thu hút được sự quan tâm của nhiều nhóm nghiên cứu. Bài báo này đề xuất một thuật toán lập lịch áp dụng cho các luồng công việc trong môi trường điện toán đám mây trong đó sử dụng phương pháp nhánh cận để cực tiểu hóa hàm mục tiêu là chi phí thực thi luồng công việc. Từ khóa: Lập lịch; Luồng công việc; Điện toán đám mây; Phương pháp nhánh cận. 1. MỞ ĐẦU Trong những năm gần đây điện toán đám mây (Cloud Computing) được ứng dụng rộng rãi trong nhiều lĩnh vực khác nhau của khoa học kỹ thuật và đời sống. Với điện toán đám mây khách hàng không cần tốn thời gian hay tiền bạc để xây dựng và bảo trì hệ thống vì mọi tài nguyên phần cứng, phần mềm đều được cung cấp sẵn sàng dưới dạng dịch vụ. Khách hàng lập tức có ngay hệ thống theo yêu cầu mà chỉ phải trả phí theo lượng tài nguyên mà họ đã sử dụng. Tuy nhiên những thuận lợi đó chỉ là nhìn từ phía khách hàng, để mang lại được những thuận lợi đó nhà cung cấp dịch vụ đám mây phải giải quyết những vấn đề vô cùng khó khăn, một trong những vấn đề đó là lập lịch cho các luồng .
