Phạm Nguyên Khang * , Bùi Lê Diễm , Nguyễn Bá Diệp Võ Trí Thức

* Tác giả liên hệ (pnkhang@ctu.edu.vn)

Abstract

In this paper, we present a solution for the scheduling problem of pratical courses in Can Tho University using Maximum Flow Network approach. The scheduling problem for practical courses is concerned to assign students to groups/practical rooms under some constraints such as room capacity, teachers? schedule, etc. The problem attempts to optimize the performance criteria and distribute the students fairly to rooms depending on the ratio of room capacity and the number of students enrolled. We model the scheduling problem as a maximum flow problem where each student is modeled as a source node and each room as a sink node. Capacity constraints are represented as maximum capacity of edges connecting source nodes and sink nodes. We have also added constraints on minimum number of students assigned to a room as minimum capacity of edges. The approach is implemented on Google computing platform using Google Apps Script. A case study is experimented by enrollment data of practical courses in Can Tho University. Results show that our solution is tractable.
Keywords: Scheduling problem, maximum flow, minimum cost, optimization

Tóm tắt

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. Sức chứa của phòng có thể được ràng buộc bằng khả năng thông qua của cung tương ứng. 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). Giải pháp được triển khai bằng công nghệ điện toán đám mây của Google sử dụng ngôn ngữ Google Apps Script. Kết quả thực nghiệm trên dữ liệu Đăng ký thực hành cho học phần Thực hành Tin học căn bản của bộ môn Sư phạm Toán, Khoa Sư phạm cho thấy rằng giải pháp mà chúng tôi đề xuất là phù hợp.
Từ khóa: Xếp lịch biểu, luồng cực đại, chi phí cực tiểu, tối ưu hoá

Article Details

Tài liệu tham khảo

Aloul, F., A. Ramani, I.Markov, and K. Sakallah, Generic ILP Versus Specialized 0-1 ILP: An Update, in Proc. of the Int’l Conference on Computer Aided Design, 450-457, 2002.

Cosla, D., A Tabu Search Algorithm for Computing an Operational Timetable, in European Journal of Operational Research, vol. 76, 98-110, 1994.

Dinic, E., A. Algorithm for solution of a problem of maximum flow in a network with power estimation. Soviet Math. Doklady11: 1277–1280, 1970.

Edmonds, J., Karp, Richard M., Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM (Association for Computing Machinery) 19 (2): 248–264, 1972.

Ford, L. R., Fulkerson, D. R. Maximal flow through a network. Canadian Journal of Mathematics 8: 399–404, 1956.

E. Goldberg and Y. Novikov, “BerkMin: A Fast and Robust SAT-solver,” in Proc. of the Design Automation and Test Conference in Europe (DATE), 142-149, 2002.

Goldberg, Andrew V., Robert E. Tarjan. A new approach to the maximum flow problem. Annual ACM Symposium on Theory of Computing, 136–146. ISBN 0-89791-193-8, 1986.

Heineman, George T., Gary Pollice, and Stanley Selkow. Chapter 8:Network Flow Algorithms. Algorithms in a Nutshell. Oreilly Media. p. 226–250, 2008.

Hertz, A., Tabu Search for Large Scale Timetabling Problems, in European Journal of Operation Research, 54(1), 39-47, 1991.

Mooney, E., R. Dargen, and W. Parameter, Large-ScaleClassroom Scheduling, in IIE Trans., 28(5), 369-378, 1996.

Moskewicz, K., C. Madigan, Y. Zho, and S. Malik, Chaff: Engineering an efficient SAT solver, in Proc. of the DesignAutomation Conference (DAC), 503-535, 2001.

Tam V., and D. Ting, Combining the Min-Conflicts and Look- Forward Heuristics to Effectively Solve a Set of Hard University Timetabling Problems, in Proc. of the IEEE International Conference on Tools with Artificial Intelligence, 2003.

Wasfy A. and Fadi A. Aloul, Solving the University Class Scheduling Problem Using Advanced ILP Techniques, in Proc. of IEEE GCC’07, 2007.