Đăng nhập
 
Tìm kiếm nâng cao
 
Tên bài báo
Tác giả
Năm xuất bản
Tóm tắt
Lĩnh vực
Phân loại
Số tạp chí
 

Bản tin định kỳ
Báo cáo thường niên
Tạp chí khoa học ĐHCT
Tạp chí tiếng anh ĐHCT
Tạp chí trong nước
Tạp chí quốc tế
Kỷ yếu HN trong nước
Kỷ yếu HN quốc tế
Book chapter
Bài báo - Tạp chí
Số Công nghệ TT 2013 (2013) Trang: 100-108
Tải về

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.

Các bài báo khác
Số Công nghệ TT 2015 (2015) Trang: 113-120
Tải về
Số Công nghệ TT 2015 (2015) Trang: 25-31
Tải về
Số 53 (2017) Trang: 44-52
Tải về
(2016) Trang: 668-677
Tạp chí: Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin FAIR 2016, ĐH. Cần Thơ 8/2016
1 (2011) Trang: 1
Tạp chí: 5 năm NCKH & Đào tạo
(2008) Trang:
Tạp chí: CORIA 2008, 5e Conférence en Recherche d’Information et Applications
(2008) Trang:
Tạp chí: Revue des Nounelles Technilogies de l’Information RNTI
 

Crossref DOI of CTUJoS


BC thường niên 2018


Con số ấn tượng (VN | EN)


Bản tin ĐHCT


TCKH tiếng Việt


TCKH tiếng Anh

 
 
Vui lòng chờ...