Bài toán xếp lịch

Bài toán xếp lịch

Lê Thanh Hà

Giới thiệu bài toán

Bài toán xếp lịch có một lịch sửphát triển dài, trải qua nhiều sự thay đổi lớn. Kể từ những

thế hệ đầu tiên củamáy tính, người ta đã nghĩ đến việc sử dụng máy tính để trợ giúp người

xếplịch. Ban đầu đó chỉ là những công cụ trợ giúp cho việc phân công những côngviệc

điều hành phối hợp. Sau này mới thực sự được phát triển thành những côngcụ xếp lịch cụ

thể.

Bài toán xếp lịch được chia thành những lớp bài toán cụ thểsau:

- Xếp thời khoá biểu. Thường được sử dụngtrong các trường Phổ thông, Đại học.

- Xếp lịch thi. Được quan tâm mỗi khi kì thi tuyển sinh Đại họchoặc thi học kì ở các

trường Đại học và Cao đẳng.

- Xếp lịch công tác cán bộ. Được sử dụng chủ yếu ở các cơ quan, tổ chức lớn...

Tuy nhiên trong bài báo này chúngta chỉ quan tâm đến bài toán xếp lịch thi trong các

trường Đại học.

Phát biểu bài toán

Bài toán được phát biểu nhưsau: Vào cuối mỗi một học kì, các trường đại học phải tổ chức

một đợt thicho từng khoa hoặc cả trường.

Trường có một nhiều phòng thi,các phòng có kích cỡ khác nhau (khả năng chứa thí sinh).

Mỗi lớp có thể được chia thành nhiều nhóm thi, mỗi nhóm thi thi trong mộtphòng, mỗi

phòng có thể có nhiều nhóm cùng thi. Và tổng số lượng thí sinh củacác nhóm phải nhỏ hơn

hoặc bằng kích cỡ của phòng.

Kì thi được chia thành các đợtthi. Mỗi nhóm sẽ thi một môn trong một đợt thi.

Yêu cầu chặt chẽ: có một số mônthi không được thi cùng đợt với môn thi khác, các nhóm

của cùng một lớp (nếu cóthể) phải thi trong cùng một đợt.

Ta có thể chia bài toán trên thành 2 bài toán đơn giản hơn:

- Phân bổ các nhóm thi vào các đợt thi sao cho chúng không xung đột nhau (không vi phạm

ràng buộc). Xây dựng một đồ thị G, với mỗi đỉnh là một nhóm, nối cạnh giữa hai đỉnh mà

nhóm của chúng có ràng buộc với nhau, tìm cách tô màu và sắc số p của đồ thị G. Số p là

giới hạn dưới của số các đợt thi. Các đỉnh được tô cùng màu có nhóm tương ứng được xếp

vào một đợt thi.