Tóm tắt Luận án tiến sĩ Toán học: Các phương pháp gần đúng dựa trên tối ưu bày đàn và tiến hóa vi phân giải bài toán lập lịch luồng công việc trong môi trường điện toán đám mây

Luận án đã đề xuất ba thuật toán gần đúng cho bài toán CLOS, để kiểm chứng các thuật toán đó phải so sánh lời giải của chúng với lời giải tối ưu. Chúng tôi đã tìm lời giải tối ưu thông qua phương pháp vét cạn, tuy nhiên phương pháp này chỉ khả thi đối với những bộ dữ liệu kích thước nhỏ.
Nội dung trích xuất từ tài liệu:
Tóm tắt Luận án tiến sĩ Toán học: Các phương pháp gần đúng dựa trên tối ưu bày đàn và tiến hóa vi phân giải bài toán lập lịch luồng công việc trong môi trường điện toán đám mâyBỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG VIỆN KHOA HỌC VÀ CÔNG NGHỆ QUÂN SỰ PHAN THANH TOÀN CÁC PHƯƠNG PHÁP GẦN ĐÚNG DỰA TRÊN TỐI ƯU BÀY ĐÀN VÀ TIẾN HÓA VI PHÂN GIẢI BÀI TOÁN LẬP LỊCH LUỒNG CÔNG VIỆC TRONG MÔI TRƯỜNG ĐIỆN TOÁN ĐÁM MÂY Chuyên ngành : Cơ sở toán học cho tin học Mã số : 62 46 01 10 TÓM TẮT LUẬN ÁN TIẾN SĨ TOÁN HỌC HÀ NỘI - 2018 Công trình được hoàn thành tại:VIỆN KH&CN QUÂN SỰ - BỘ QUỐC PHÒNG Người hướng dẫn khoa học: 1. TS Nguyễn Thế Lộc 2. TS Nguyễn Doãn Cường Phản biện 1:PGS.TS. Nguyễn Đức Nghĩa Trường Đại học Bách khoa Hà Nội Phản biện 2: PGS.TS. Lê Trọng Vĩnh Trường Đại học Khoa học tự nhiên Đại học Quốc gia Hà Nội Phản biện 3: PGS.TS. Nguyễn Xuân Hoài Trường Đại học Hà NộiLuận án tiến sĩ được bảo vệ trước Hội đồng chấm luận án cấp Viện, họp tại Viện KH&CNQS Vào hồi giờ ngày tháng năm 2018 Có thể tìm hiểu luận án tại thư viện: - Thư viện Viện Khoa học và Công nghệ quân sự - Thư viện Quốc gia Việt Nam 1 MỞ ĐẦUTính cấp thiết của đề tài luận án Điện toán đám mây hoạt động dựa trên nền tảng công nghệ ảo hóa vàmạng internet. Trong môi trường điện toán đám mây mọi tài nguyên phầncứng, phần mềm đều được cung cấp cho khách hàng dưới dạng dịch vụ vàkhách hàng sẽ phải trả chi phí cho các tài nguyên thực dùng. Điện toán đámmây [1] là môi trường phân tán không đồng nhất với sự kết hợp của nhiềumáy chủ vật lý tạo nên các máy chủ ảo để phục vụ khách hàng. Bên cạnhcác lợi ích mang lại như tài nguyên luôn sẵn dùng, giảm thiểu chi phí đầutư hạ tầng và đội ngũ nhân viên công nghệ thông tin, điện toán đám mâycũng phải đối mặt với những thách thức như an toàn và bảo mật dữ liệu,điều phối tài nguyên hiệu quả tại các trung tâm dữ liệu, lập lịch luồng côngviệc,… Bài toán Lập lịch luồng công việc được ứng dụng trong nhiều lĩnh vựccủa khoa học và cuộc sống như lập lịch điều phối tài nguyên trong hệ điềuhành, các hệ thống phân tán, lập lịch biểu cho các dây chuyền sản xuất. Cácnhà khoa học đã sử dụng dữ liệu dạng luồng công việc trong nhiều lĩnh vựckhoa học như nghiên cứu vũ trụ, động đất, tin sinh, vật lý….Đặc trưng củacác loại ứng dụng này là cần phải xử lý một số lượng lớn tác vụ , khốilượng dữ liệu trao đổi giữa các tác vụ cũng rất lớn do vậy các ứng dụng nàythường được triển khai trên các hệ thống tính toán phân tán như điện toánlưới hay điện toán đám mây. Thời gian hoàn thành và chi phí thực thi luồngcông việc phụ thuộc vào nhiều yếu tố đầu vào như:• Số lượng tác vụ của luồng công việc.• Số tài nguyên của môi trường tính toán.• Quan hệ thứ tự giữa các tác vụ trong luồng công việc.• Độ trù mật của đồ thị luồng công việc. 2 Rất nhiều trường hợp riêng của bài toán lập lịch đã được chứng minhlà thuộc lớp NP-Khó [2], do vậy để tìm ra lời giải tối ưu cho các bài toánvới kích thước dữ liệu vào lớn nếu dùng phương pháp vét cạn sẽ mất rấtnhiều thời gian. Một số cách tiếp cận theo Heuristic truyền thống như Min-min, Max-min,… thường cho chất lượng lời giải không tốt. Những giảipháp khác, chẳng hạn GA hay PSO, được các nhà nghiên cứu đề xuất chotới nay đều không hướng tới mục tiêu là tối thiểu hóa thời gian thực hiện(makespan) như luận án này đặt ra. Do vậy việc nghiên cứu và đề xuất cácthuật toán lập lịch tìm được lời giải gần tối ưu trong thời gian ngắn sẽ giúpnâng cao hiệu năng của trung tâm điều phối đám mây trong việc cung cấpdịch vụ tới khách hàng.Cấu trúc luận án Luận án gồm phần mở đầu, phụ lục, 03 chương, phần kết luận vàhướng phát triển, danh mục các công trình khoa học đã công bố và tài liệutham khảo. Phần mở đầu: trình bày tính cấp thiết của đề tài, những khái quátchung về mục tiêu, đối tượng, nội dung, phương pháp nghiên cứu, ý nghĩakhoa học và thực tiễn của luận án.Chương 1: Giới thiệu bài toán và các nghiên cứu liên quan Chương này trình bày các khái niệm cơ bản về luồng công việc, cấutrúc và một số luồng công việc trong các ứng dụng khoa học thực tiễn. Mục1.4 trình bày mô hình bài toán lập lịch luồng công việc trong môi trườngđiện toán đám mây (từ đây gọi là CLOS - Cloud Scheduling), biểu diễn bàitoán dưới dạng kí hiệu Graham và chứng minh độ phức tạp của bài toán.Mục 1.6 trình bày một số nghiên cứu liên quan đến bài toán lập lịch vàđánh giá ưu nhược điểm của các cách tiếp cận giải bài toán lập lịch.Chương 2: Giải bài toán CLOS theo phương pháp Tối ưu bày đàn 3 Dựa theo phương pháp Tối ưu bày đàn, chương 2 trình bày hai thuậttoán mới để giải bài toán CLOS ...