Phương pháp nhánh cận cho bài toán lập lịch luồng công việc

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.
Nội dung trích xuất từ tài liệu:
Phương pháp nhánh cận cho bài toán lập lịch luồng công việcNghiê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 ứngdụ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âydự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 cungcấ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ầumà chỉ phải trả phí theo lượng tài nguyên mà họ đã sử dụng. Tuy nhiên nhữngthuậ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 công việc. Lập lịch luồng công việc là bài toán đã được nghiên cứu từ những năm 1950,và bài toán này đã được chứng minh thuộc lớp NP-Khó. Nhiều ứng dụng khoahọc được mô hình hóa bởi dạng đồ thị luồng công việc như ứng dụng Montage[1], CyberShake [2], Epigenomics [3], LIGO [4]. Vấn đề lập lịch thực thi luồngcông việc trong môi trường điện toán đám mây về bản chất là tìm phương án ánhxạ những tác vụ của luồng công việc tới các máy chủ của đám mây thỏa mãnràng buộc về thứ tự của các tác vụ trong luồng công việc và chi phí hoàn thànhluồng công việc là nhỏ nhất. Đã có nhiều công trình nghiên cứu xem xét vấn đềnày nhằm tối thiểu hóa các hàm mục tiêu khác nhau như tổng chi phí, tổng thờigian thực thi tại các máy chủ ,... Bài báo này sẽ đề xuất một thuật toán nhằm cựctiểu hóa thời gian hoàn thành luồng công việc (makespan) dựa trên phương phápnhánh cận. Nội dung tiếp theo của bài báo gồm những phần chính như sau. Phần II trìnhbày một số công trình liên quan đến bài toán lập lịch luồng công việc. Phần III môTạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 11 - 2018 63 Công nghệ thông tintả bài toán và trình bày mô hình toán học. Phần IV giới thiệu thuật toán đề xuấtdựa trên phương pháp nhánh cận. Để kiểm chứng thuật toán, phần V trình bày quátrình thực nghiệm trên một số luồng công việc khoa học mẫu trong môi trườngđám mây. Phần VI trình bày kết luận và hướng nghiên cứu tiếp theo. 2. NỘI DUNG NGHIÊN CỨU2.1. Những công trình nghiên cứu liên quan Bài toán lập lịch luồng công việc đã được chứng minh là thuộc lớp NP-Khó[5] vì vậy đã có nhiều công trình nghiên cứu nhằm tìm ra lời giải đúng hoặc gầnđúng của bài toán này. N.S.Grigoreva [6] đã đề xuất thuật toán lập lịch điều phốicác tác vụ của luồng công việc vào thực hiện trên một hệ thống đa bộ vi xử lýnhằm cực tiểu hóa thời gian hoàn thành luồng công việc. Tác giả đã sử dụng kếthợp phương pháp nhánh cận và kỹ thuật tìm kiếm nhị phân để tìm ra phương ánxếp lịch có thời gian hoàn thành luồng công việc là nhỏ nhất. Sadhasivam đã đềxuất thuật toán lập lịch luồng công việc dựa trên sự cân bằng tải trong môi trườngđiện toán đám mây [7]. Thuật toán không chỉ đáp ứng các yêu cầu từ người sửdụng mà còn cung cấp khả năng sử dụng tài nguyên một cách hiệu quả. Đây làthuật toán theo hướng nâng cao hiệu quả dịch vụ dựa trên Meta-heuristic. Các tác giả trong bài báo [8] đã đề xuất thuật toán EGA (Enhanced GeneticAlgorithm) lập lịch bằng phương pháp di truyền. Trong công trình các tác giả sửdụng thuật toán Enhanced Max Min trong bước khởi tạo quần thể nhằm tìm ra cáccá thể tốt cho quá trình tiến hóa. Pandey [9] đã đề xuất thuật toán lập lịch PSO Heuristic (PSO_H) dựa trênchiến lược tối ưu bày đàn trong đó hàm mục tiêu được chọn là tổng chi phí của quá ...