1
CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM
Độc lập – Tự do – Hạnh phúc
TÓM TẮT LUẬN VĂN THẠC SĨ
Tên đề tài (tiếng Việt): Phát triển thuật toán tối ưu hóa cho các bài toán phân công
giảng dạy
Tên đề tài (tiếng Anh): Algorithms for solving course assignment problems
Tác giả luận văn: Nguyễn Trung Kiên
Chuyên ngành: Công nghệ thông tin Khóa: 2018A
Người hướng dẫn:
•
TS. Phạm Quang Dũng, Viện Công nghệ thông tin và Truyền thông, Trường
Đại học Bách khoa Hà Nội
Từ khóa (Keyword): Bài toán phân công giảng dạy, Google Or-Tools, Choco, Quy
hoạch tuyến tính, Quy hoạch ràng buộc, heuristic.
Nội dung tóm tắt:
a)
Lý do chọn đề tài
Bài toán phân công giảng dạy xuất hiện trong nghiệp vụ quản lý đào tạo là một
bài toán thuộc lớp bài toán tối ưu tổ hợp trong đó người quản lý đào tạo cần phân công
các giáo viên giảng dạy các lớp của học kỳ thỏa mãn nhiều tiêu chi như cân bằng khối
lượng giữa các giáo viên, giáo viên không được phân công dạy 2 lớp trùng thời khóa
biểu, giáo viên chỉ được phân công dạy các môn phù hợp với chuyên môn của mình.
b)
Mục đích nghiên cứu của luận văn, đối tượng, phạm vi nghiên cứu.
- Mục đích nghiên cứu:
Mục tiêu của đề tài là khảo sát bài toán phân công giảng dạy thực tế, xây dựng mô
hình toán học cho bài toán và phát triển các phương pháp thuật toán để giải bài toán đặt
ra.
2
- Đối tượng nghiên cứu:
Đối tượng nghiên cứu của luận văn bao gồm: Bài toán phân công giảng dạy, các
thuật toán phân công giảng dạy, các công cụ và thư viện hỗ trợ.
Phạm vi nghiên cứu:
Phạm vi nghiên cứu tập trung vào phát triển các thuật toán phân công giảng dạy,
so sánh đánh giá kết quả của các thuật toán trên các bộ dữ liệu thử nghiệm.
c)
Tóm tắt cô đọng các nội dung chính và đóng góp mới của tác giả
Luận văn nghiên cứu phát triển thuật toán phân công giảng dạy bao gồm những
đóng góp như sau:
- Mô tả mô hình toán học của bài toán.
- Lựa chọn các công cụ, phần mềm, thư viện hỗ trợ giải quyết bài toán.
- Đề xuất 02 thuật toán sử dụng quy hoạch tuyến tính trên Or-Tools, 03 thuật
toán tham lam, 01 thuật toán quy hoạch ràng buộc giải quyết bài toán.
d)
Phương pháp nghiên cứu
Phương pháp nghiên cứu lý thuyết: Đọc, tìm hiểu các tài liệu , kiến thức liên
quan đến:
- Bài toán tối ưu hóa tổ hợp;
- Giải thuật tham lam;
- Quy hoạch tuyến tính;
- Quy hoạch ràng buộc
- Công cụ Or-Tools;
- Thư viện Choco.
Phương pháp thực nghiệm:
- Cài đặt các thuật toán giải quyết bài toán phân công giảng dạy trên Công cụ Or-
Tools và thư viện Choco.
- Thực nghiệm, phân tích, đánh giá kết quả của giải pháp.
e)
Kết luận
Trong luận văn này, tôi đã khảo sát bài toán phân công giảng dạy, cài đặt, thử
nghiệm và đánh giá các thuật toán tham lam khác nhau giải bài toán đặt ra. Hướng phát
triển tiếp theo sẽ là nghiên cứu các thuật toán khác để giải quyết bài toán từ đó đánh giá
và xây dựng nên phương án tối ưu nhất cho bài toán phân công giảng dạy.
