Thông tin chung:

Ngày nhận: 03/09/2013

Ngày chấp nhận: 21/10/2013

Title:

Maximum flow network approach for scheduling problem

Từ khóa:

Xếp lịch biểu, luồng cực đại, chi phí cực tiểu, tối ưu hoá

Keywords:

Scheduling problem, maximum flow, minimum cost, optimization

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.

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.