- TIẾP CẬN LUỒNG CỰC ĐẠI TRONG MẠNG CHO BÀI TOÁN XẾP LỊCH BIỂU Phạm Nguyên Khang 1 , Võ Trí Thức 1 , Nguyễn Bá Diệp 1 và Bùi Lê Diễm 2. - Xếp lịch biểu, luồng cực đại, chi phí cực tiểu, tối ưu hoá Keywords:. - Trong bài viết này, chúng tôi trình bày một giải pháp cho bài toán xếp lịch các học phần thực hành tại các trường đại học sử dụng mô hình luồng cực đại trong mạng. - Bài toán xếp lịch thực hành là một dạng của bài toán xếp thời khoá biểu tổng quát trong đó liên quan đến việc phân các sinh viên vào các nhóm/phòng thực hành sao cho thoả mãn các ràng buộc về lịch rảnh của sinh viên, giảng viên, sức chứa của phòng và quan trọng nhất là khai thác tối đa hiệu suất sử dụng của các phòng thực hành. - Với các ràng buộc như trên, bài toán xếp lịch thực hành có thể được mô hình hoá về bài toán tìm luồng cực đại trong mạng với độ phức tạp giải thuật đa thức. - Mỗi sinh viên là một đỉnh phát, mỗi phòng thực hành là một đỉnh thu. - Ta cũng có thể thêm vào ràng buộc số lượng sinh viên tối thiểu cho một phòng bằng các cách đặt cận dưới cho các cung. - Vấn đề tối ưu tỉ lệ giữa sức chứa của phòng và số sinh viên được gán vào phòng được giải quyết bằng tiếp cận bài toán luồng cực đại với chi phí thấp nhất (minimum cost maximum flow). - Hiện nay có hai giải pháp chính được sử dụng để giải bài toán này: sử dụng tiếp cận tìm kiếm cục bộ (local search và giải pháp xếp lịch bán tự động. - Xét về bản chất việc làm này đã giảm kích thước đầu vào của bài toán xếp lịch biểu. - Tuy nhiên, đối với các học phần thực hành, hoặc các học phần vừa có lý thuyết vừa có thực hành đều không được xếp lịch thực hành trước. - Lý do cơ bản là lịch thực hành sẽ phụ thuộc rất nhiều số lượng sinh viên đăng ký môn học. - Nếu xếp lịch trước có thể dẫn đến việc sử dụng không hiệu quả các phòng thực hành (do số sinh viên đăng ký quá ít chẳng hạn). - Do đó, hiện nay việc xếp lịch thực hành thường chỉ được thực hiện sau khi sinh viên đã đăng ký các học phần và có thời khóa biểu của các học phần lý thuyết. - tin học), Khoa Công nghệ (thực hành kỹ thuật điện), việc xếp lịch thực hành cho vài trăm sinh viên trở thành vấn đề. - Nhóm thứ nhất, thực hiện thủ công: giáo viên phân nhóm và dán thông báo, sinh viên đăng ký trực tiếp trên giấy và tùy vào tình hình đăng ký mà giáo viên phụ trách giảng dạy sẽ xếp lịch. - Nhóm thứ hai cho sinh viên đăng ký thông qua một hệ thống nào đó (ví dụ một website tự tạo). - Sau khi đã có nhu cầu đăng ký, việc xếp lịch được thực hiện thủ công.. - Tóm lại, cho dù cho sinh viên đăng ký bằng cách nào đi nữa thì việc xếp lịch sau cùng vẫn phải thực hiện thủ công dẫn đến mất nhiều thời gian công sức thậm chí có thể tồn tại sai sót trong khi xếp lịch.. - Trong bài báo này, chúng tôi đề xuất một giải pháp xếp lịch thực hành cho các học phần có thực hành tại Trường Đại học Cần Thơ. - Giải pháp đề xuất sẽ thực hiện việc phân tự động sinh viên vào các nhóm thực hành phù hợp (không bị trùng lịch) và sử dụng các phòng thực hành một cách hiệu quả (khai thác tối đa hiệu suất sử dụng của phòng). - Các đóng góp chính của bài báo gồm: (i) đề xuất quy trình đăng ký và xếp lịch biểu, (ii) mô hình hoá bài toán xếp lịch biểu về bài toán tìm luồng cực đại trên mạng, (iii) đề xuất hàm mục tiêu để tối ưu hiệu quả sử dụng các phòng thực hành cùng với giải thuật cải tiến cho bài toán luồng cực đại với chi phí thấp nhất trong bài toán xếp lịch biểu. - Ngoài ra, các lựa chọn của sinh viên cũng sẽ được xem xét ưu tiên theo thứ tự. - Phần tiếp theo của bài viết được trình bày như sau: phần 2 trình bày ngắn gọn về Bài toán xếp lịch biểu. - phần 3 trình bày mạng và luồng cực đại trong mạng. - phần 4 trình bày ứng dụng của luồng cực đại trong mạng cho bài toán xếp lịch biểu. - 2 GIẢI PHÁP CHO BÀI TOÁN XẾP LỊCH BIỂU. - Các học phần thực hành (hoặc học phần vừa có lý thuyết vừa có thực hành) không được xếp thời biểu trước mà giảng viên (hoặc giảng giáo viên) phụ trách học phần phải tự xếp lịch. - Quy trình xếp lịch thực hành cho mỗi học phần như sau: (i) với số lượng sinh viên đăng ký tham gia học phần đã biết, giảng viên ước lượng số lượng nhóm sao cho phù. - hợp số lượng sinh viên và sức chứa của các phòng thực hành (phòng máy tính, phòng thí nghiệm). - (ii) chọn buổi thực hành cho các nhóm và phân công giảng viên hướng dẫn thực hành (iii) thông báo cho sinh viên đăng ký nhóm và (iv) giảng viên phân sinh viên vào các nhóm. - Giai đoạn (i) được thực hiện khá dễ dàng dựa vào số lượng sinh viên và sức chứa các phòng thực hành. - Giai đoạn cho sinh viên đăng ký nhóm là công việc khá phức tạp. - Giai đoạn cuối cùng là giai đoạn khó nhất: phân sinh viên vào các nhóm sao cho số lượng sinh viên của mỗi nhóm không quá lớn (vượt quá khả năng của phòng thực hành tương ứng với nhóm) và cũng không quá nhỏ (khai thác tối đa hiệu suất sử dụng phòng thực hành). - Với quy trình xếp lịch như thế, chúng ta đã chia nhỏ bài toán xếp thời khóa biểu tổng quát (rất khó) thành các bài toán nhỏ (dễ hơn).. - 3 MẠNG VÀ LUỒNG CỰC ĐẠI TRONG MẠNG. - (4) Bài toán tìm luồng cực đại (trên mạng) là bài toán cực đại hóa | f | với các ràng buộc trên. - Giải thuật đầu tiên được sử dụng để tìm luồng cực đại là giải thuật đường tăng luồng (augmenting path algorithm) của Ford &. - 4 ỨNG DỤNG LUỒNG CỰC ĐẠI CHO BÀI TOÁN XẾP LỊCH BIỂU. - Như đã phân tích ở trên, bài toán xếp lịch thực hành được quy về các bài toán con đơn giản hơn.. - Bài toán phân nhóm cho sinh viên là bài toán khó nhất và đáng được quan tâm. - Trong phân này chúng tôi sẽ mô hình hóa bài toán phân nhóm về bài toán tìm luồng cực đại trên mạng.. - u n } là tập các sinh viên. - d(u,v), u S, v G: hàm đăng ký nhóm của sinh viên. - 1 nếu sinh viên u đăng ký nhóm v, ngược lại d(u,v. - Mỗi sinh viên được mô hình thành một đỉnh- sinh viên, mỗi nhóm cũng tương ứng với một đỉnh- nhóm. - Nếu sinh viên u i đăng ký nhóm v j sẽ có một cung nối từ đỉnh-sinh viên u i đến đỉnh-nhóm v j , khả. - Để tránh trường hợp một nhóm có quá ít sinh viên ta có thể bổ sung thêm ràng buộc sĩ số tối thiểu của một nhóm: tổng số sinh viên của nhóm v không được nhỏ hơn l(v). - Cách đơn giản nhất để giải bài toán luồng cực đại trên mạng với ràng buộc khả năng thông qua nhỏ nhất của các cung là biến đổi về bài toán luồng cực đại chuẩn. - Nếu G’ có luồng bão hòa, nó sẽ có luồng cực đại.. - Hình 1: Mạng phân nhóm sinh viên. - Giải thuật tìm luồng cực đại trong trường hợp khả năng thông qua của cung bị chặn dưới theo các bước như sau:. - Do đó, ngoài ràng buộc về sĩ số thấp nhất, ta cũng muốn số lượng sinh viên được xếp vào nhóm phải tương ứng với sĩ số tối đa của nhóm (ứng với sức chứa của phòng thực hành). - Không xếp quá ít sinh viên vào một nhóm có sĩ số tối đa quá lớn. - (5) Đó là tỉ số giữa sĩ số tối đa và số sinh viên thực. - Như thế bài toán trở thành tìm luồng cực đại trên mạng thỏa mãn ràng buộc (5). - Đây có thể xem như một biến thể của bài toán luồng cực đại với giá thành cực tiểu (minimum-cost maximum-flow). - Giải thuật gốc cho bài toán luồng cực đại với giá thành cực tiểu được mô tả như sau:. - Tìm luồng cực đại f trong mạng G. - Do tính chất đặc biệt của bài toán phân nhóm sinh viên: có cấu trúc đồ thị đơn giản và hàm mục tiêu cần tối ưu khác với hàm mục tiêu của bài toán luồng cực đại với giá thành cực tiểu, chúng tôi đề xuất giải thuật giải quyết bài toán như sau:. - Từ các phân tích được trình bày ở trên, giải pháp tổng thể cho quy trình xếp lịch được mô tả ngắn gọn như sau:. - Cho sinh viên đăng ký. - Tìm luồng cực đại trên mạng. - Gán sinh viên vào nhóm dựa trên kết quả của luồng cực đại.. - Chúng tôi đã triển khai quy trình đăng ký và xếp lịch thực hành trên trên nền tảng công nghệ điện toán đám mây của Google với ngôn ngữ lập trình ngữ Google Apps Script. - Xây dựng đồ thị G’ và tìm luồng cực đại. - Tìm luồng cực đại f r từ s đến t trên G với khả năng thông qua lớn nhất c r. - Luồng cực đại thỏa mãn ràng buộc khả năng thông qua lớn nhất và nhỏ nhất là:. - Tìm luồng cực đại f trong mạng G 2. - Với mỗi đỉnh-sinh viên u S. - Việc tổ chức cho sinh viên đăng ký được thực hiện khá đơn giản với Google Form (bước 2). - Tạo một biểu mẫu đăng ký với Google Form và gởi địa chỉ của biểu mẫu cho sinh viên. - Trong biểu mẫu này, phần quan trọng nhất là mã số sinh viên. - và các lựa chọn của sinh viên. - Tuỳ vào lịch rảnh của mình sinh viên sẽ lựa chọn các nhóm có lịch phù hợp. - Để bài toán dễ có lời giải, có thể khuyến khích sinh viên lựa chọn nhiều nhóm khác nhau.. - Trong thời hạn đăng ký, sinh viên có thể điều chỉnh các lựa chọn. - Sau khi sinh viên đăng ký xong, dữ liệu đăng ký được tự động lưu trong bảng tính (bước 3).. - nhóm sinh viên. - Dữ liệu sẽ được xử lý trước khi chuyển qua bước xây dựng mạng và tìm luồng cực đại trong mạng. - Trong phần tiền xử lý này, ta loại bỏ các sinh viên không có danh sách. - Nếu sinh viên đăng ký nhiều lần ta ghi nhận lần đăng ký sau cùng và bỏ qua các lần đăng ký trước đó. - Bước 2 cũng có thể được thực hiện tự động nếu hệ thống được cung cấp thông tin về lịch rảnh của sinh viên.. - Đầu tiên, có thể cho sức chứa tối thiểu của tất cả các nhóm bằng 0 và thực hiện việc xếp lịch. - Ngoài ra ta cũng có thể bật/tắt chức năng tối ưu tỉ lệ của sức chứa tối đa và số sinh viên gán vào các nhóm. - Nếu chức năng này được bật, hệ thống sẽ tìm luồng cực đại đồng thời tối ưu hàm mục tiêu (5).. - Bảng 2 trình bày kết quả thu được khi kiểm thử hệ thống xếp lịch cho học phần thực hành tin học căn bản với số sinh viên đăng ký 694 trong đó 240 trường hợp ký trùng hoặc không có tên trong danh sách. - Sau khi tiền xử lý (tự động) số sinh viên. - Trường hợp không tối ưu tỉ lệ giữa sức chứa tối đa và số sinh viên được gán vào nhóm, sẽ có trường hợp 1 số nhóm có rất nhiều sinh viên, trong khi các nhóm khác có rất ít sinh viên (so với sức chứa tối đa của nhóm). - Kết quả xếp lịch được lưu trở lại bảng tính (xem Bảng 3) và có thể sử dụng để in kết quả theo từng nhóm như Bảng 4.. - Bảng 1: Dữ liệu đăng ký thực hành học phần tin học căn bản. - Bảng 2: Kết quả xếp lịch trong trường hợp không tối ưu và tối ưu tỉ lệ sức chứa tối đa và số sinh viên trong nhóm. - Bảng 3: Kết quả việc phân sinh viên vào các nhóm. - Xét về mặt thời gian thực hiện giải thuật tìm luồng cực đại, với số sinh viên khoảng 600-1000, thời gian thực hiện khoảng 20-30 giây. - Chúng tôi vừa đề xuất một giải pháp xếp lịch biểu cho các môn học sử dụng tiếp cận Luồng cực đại trong mạng. - Chúng tôi đã mô hình hoá bài toán xếp lịch biểu về bài toán tìm luồng cực đại trên mạng. - Ràng buộc mỗi sinh viên chỉ được gán vào một nhóm được mô hình bằng khả năng thông qua của cung xuất phát từ đỉnh-sinh viên bằng 1. - chứa tối đa và số sinh viên vào nhóm cùng với một giải thuật tìm luồng cực đại với hàm mục tiêu nhỏ nhất. - Chúng tôi đã thực nghiệm giải pháp đề xuất trên dữ liệu đăng ký thực hành của các sinh viên ở các Khoa của Trường Đại học Cần Thơ: Khoa Sư phạm (Tin học căn bản), Khoa Công nghệ Thông tin và Truyền thông (Xử lý ảnh), Khoa Công nghệ (Kỹ thuật điện). - Bảng 4: In danh sách sinh viên theo nhóm