tailieunhanh - Thuật toán nhánh cận giải bài toán lập lịch luồng công việc

Điện toán đám mây là một môi trường dịch vụ dựa trên nền tảng công nghệ thông tin và truyền thông, mọi tài nguyên trên hệ thống đều được cung cấp cho người sử dụng dưới dạng dịch vụ, và người sử dụng chỉ phải chi trả các tài nguyên thực dùng. Bài viết này đề xuất một thuật toán lập lịch luồng công việc mới nhằm cực tiểu hóa chi hoàn thành luồng công việc trong môi thực thi điện toán đám mây dựa trên phương pháp nhánh cận. | HNUE JOURNAL OF SCIENCE Natural Sciences 2018, Volume 63, Issue 3, pp. 108-116 This paper is available online at DOI: THUẬT TOÁN NHÁNH CẬN GIẢI BÀI TOÁN LẬP LỊCH LUỒNG CÔNG VIỆC Phan Thanh Toàn1, Đặng Quốc Hữu2 và Nguyễn Thế Lộc3 Khoa Sư phạm Kĩ thuật, Trường Đại học Sư Phạm Hà Nội Trung tâm Công nghệ thông tin, Trường Đại học Thương mại 3 Khoa Công nghệ Thông tin, Trường Đại học Sư phạm Hà Nội 1 2 Tóm tắt. Điện toán đám mây là một môi trường dịch vụ dựa trên nền tảng công nghệ thông tin và truyền thông, mọi tài nguyên trên hệ thống đều được cung cấp cho người sử dụng dưới dạng dịch vụ, và người sử dụng chỉ phải chi trả các tài nguyên thực dùng. Với sự ra đời của công nghệ điện toán đám mây rất nhiều các ứng dụng trong lĩnh vực công nghệ thông tin đã có những thay đổi căn bản, chuyển từ dạng cung cấp sản phẩm đóng gói sử dụng riêng rẽ sang dạng cung cấp dịch vụ và được duy trì, vận hành bởi nhà cung cấp dịch vụ qua đó giảm đáng kể chi phí cho người dùng. Trong thực tiễn và nghiên cứu khoa học có nhiều bài toán được biểu diễn dưới dạng mô hình luồng công việc như lập lịch cho dây chuyền sản xuất, lập lịch điều phối tài nguyên trong hệ điều hành, lập lịch thời khóa biểu. Lập lịch là hoạt động nhằm gán các tác vụ vào thực hiện trên các tài nguyên tính toán và thảo mãn các ràng buộc về thứ tự các tác vụ trong luồng công việc cũng như các giới hạn về tài nguyên. Đa số các bài toán thuộc họ lập lịch đã được chứng minh thuộc lớp NP-Khó [1], do vậy việc tìm ra các thuật toán lập lịch nhằm cực tiểu hóa chi phí hoàn thành luồng công việc là một lĩnh vực khó và đã thu hút được sự quan tâm của nhiều nhà khoa học. Bài báo này đề xuất một thuật toán lập lịch luồng công việc mới nhằm cực tiểu hóa chi hoàn thành luồng công việc trong môi trường thực thi điện toán đám mây dựa trên phương pháp nhánh cận. Từ khóa: Lập lịch luồng công việc, ứng dụng 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 .