Cong ty Cong Nghe Tin hoc Nha truong http://www.vnschool.net
Tinh chỉnh dữ liệu trong việc xếp thời khóa biểu và thuật toán tinh chỉnh tối ưu trong phần mềm TKB 7.5
31/05/2009

Bùi Việt Hà, Công ty Công nghệ Tin học Nhà trường

1. Tinh chỉnh dữ liệu trong bài toán xếp thời khóa biểu

Công việc chính của mọi giáo viên xếp thời khóa biểu là "xếp" hay "đặt" các tiết học vào các ô lưới của thời khóa biểu sao cho không tạo ta trùng giờ, trùng tiết. Mỗi "tiết xếp" như vậy bao gồm các thông tin: lớp học, giáo viên, môn học, ngày trong tuần và tiết trong buổi học. Việc xếp vào như vậy không phải được tiến hành một lần là xong. Trên thực tế do cần có những phương án tốt hoặc do nhu cầu thay đổi, người xếp thời khóa biểu phải làm đi làm lại việc xếp này nhiều lần hay cần thay đổi vị trí các tiết học trong tuần sao cho tối ưu hơn.


Thông thường việc xếp thời khóa biểu của nhà trường được chia làm 2 giai đoạn chính:

1. Giai đoạn xếp "đại trà".

Đây là giai đoạn mà công việc xếp thời khóa biểu tương đối dễ. Với những người xếp thời khóa biểu kinh nghiệm, việc xếp được 95-99% công việc thời khóa biểu trong vòng một vài tiếng là hoàn toàn khả thi. Với các phần mềm thời khóa biểu hiện nay, công việc xếp "đại trà" này chỉ mất một vài giây để thực hiện.

2. Giai đoạn hoàn thiện.

Ở giai đoạn hoàn thiện, công việc xếp thời khóa biểu thường là:

- Xếp nốt một vài tiết còn lại của thời khóa biểu.

- Điều chỉnh dữ liệu trên thời khóa biểu theo nhu cầu thay đổi của giáo viên sao cho hợp lý hơn và đẹp hơn.

Đây chính là giai đoạn công việc chính và phức tạp nhất của bài toán xếp thời khóa biểu. Một số ít các tiết cuối cùng cần xếp lại chính là các tiết khó xếp nhất. Thông thường việc xếp một số tiết cuối cùng này được tiến hành đồng thời với việc điều chỉnh thời khóa biểu với các ô có liên quan.

Như vậy có thể nói trong giai đoạn hoàn thiện công việc chính quan trọng nhất của bài toán xếp thời khóa biểu chính là tinh chỉnh và điều chỉnh dữ liệu. Đây là công việc mất công sức nhất, đòi hỏi nhiều thời gian nhất và cũng là khó nhất. Để thực hiện được công việc tinh chỉnh thời khóa biểu, ngoài kinh nghiệm và hiểu biết yêu cầu của công việc, người xếp thời khóa biểu còn cần có trong tay các công cụ trợ giúp.

Đối với người xếp thời khóa biểu bằng tay thì công cụ trợ giúp là giấy, bút chì, tẩy, cái thước, ... Nhiều giáo viên đã sáng tạo ra các công cụ rất hay, độc đáo hỗ trợ đắc lực cho việc xếp thời khóa biểu.

Đối với phần mềm, việc tạo ra các công cụ trợ giúp tinh chỉnh thời khóa biểu là một trong những nhiệm vụ chủ yếu của phần mềm. Có thể nói sức mạnh chính của một phần mềm hỗ trợ xếp thời khóa biểu chính là các công cụ tinh chỉnh dữ liệu này. Phần mềm nào xây dựng được càng nhiều công cụ hay, hữu hiệu thì phần mềm đó càng có giá trị.

2. Các thao tác và thuật toán tinh chỉnh dữ liệu trong phần mềm TKB

TKB là phần mềm hỗ trợ xếp thời khóa biểu nhà trường phổ thông do Công ty Công nghệ Tin học Nhà trường xây dựng. Đây là một trong những phần mềm ra đời sớm nhất tại Việt Namvà đang có ứng dụng rất rộng rãi trong các nhà trường.

Về tính năng "xếp" tiết học, phần mềm TKB đã có và đạt được các tính năng sau:

- Ngay từ những phiên bản đầu tiên, phần mềm TKB đã có chức năng xếp tự động đại trà các tiết học trong thời khóa biểu. Phần mềm có khả năng xếp được 95-99% công việc thời khóa biểu chỉ trong một vài giây mà vẫn đảm bảo thỏa mãn hầu hết các ràng buộc môn học và yêu cầu giáo viên.

- Từ phiên bản TKB 5.0 trở đi, phần mềm TKB đã xây dựng được một tính năng rất hữu ích đó là lệnh tự động phân tích và xếp 100% thời khóa biểu. Đây là chức năng mạnh nhất của phần mềm TKB mà hiện nay chưa có trong các phần mềm hỗ trợ xếp thời khóa biểu khác.

Các tính năng tinh chỉnh và điều chỉnh dữ liệu chính có trong phần mềm TKB bao gồm:

Lệnh di chuyển một tiết trên TKB từ vị trí này sang vị trí khác (gọi là lệnh Move To).

Chức năng này được dùng khi muốn làm đẹp hoặc thỏa mãn nhu cầu của lớp hoặc giáo viên bằng cách dịch chuyển một tiết học từ vị trí ban đầu (xấu) sang một vị trí mới (tốt hơn).

Lệnh giải phóng 1 tiết trên TKB: chuyển tiết này sang một vị trí khác bất kỳ (gọi là lệnh Push Out).

Mục đích của lệnh là giải phóng một ô trên thời khóa biểu bằng cách chuyển tiết tại ô này sang một vị trí khác. Việc chuyển sang vị trí nào không quan trọng (do phần mềm tự động tính), mục đích chính của lệnh là có một ô trên khóa biểu là rỗng để có thể xếp tiết cho các môn học khác hoặc giáo viên khác.

Lệnh xếp bằng được 1 tiết vào ô lưới của một thời khóa biểu lớp hoặc giáo viên (gọi là lệnh CX).

Lệnh này được dùng khi muốn xếp những tiết cuối cùng chưa xếp vào thời khóa biểu. Phần mềm sẽ tự động điều chỉnh và xếp bằng được tiết này (tất nhiên với một số điều kiện như sẽ ảnh hưởng đến các giáo viên khác trong nhà trường. Lệnh này trước kia được gọi là lệnh Xếp tiết có điều kiện).

Như vậy 3 chức năng (hay kỹ thuật) Move To, Push OutCX là các tư duy chính của công việc tinh chỉnh dữ liệu thời khóa biểu. Mọi phần mềm hỗ trợ xếp thời khóa biểu đều phải có đủ cả 3 chức năng này.

Đặc điềm chung nổi bật nhất của các chức năng tinh chỉnh dữ liệu trên đây (Move To, Push Out, CX) là chúng sẽ thực hiện một dãy các thay đổi dữ liệu, hay còn gọi là dãy các bước thay đổi. Để thực hiện được mục đich làm đẹp cho một lớp hoặc một giáo viên sẽ phải có nhiều giáo viên trung gian bị thay đổi dữ liệu.

Trên thực tế khi tinh chỉnh dữ liệu, người xếp thời khóa biểu cũng sẽ phải sử dụng một trong các kỹ thuật trên. Điểm khác biệt duy nhất giữa làm bằng tay và máy tính là khi làm bằng tay con người phải tư duy từng bước và xử lý từng bước, còn phần mềm máy tính có thể làm tự động tất cả các bước này.

Để đảm bảo cho việc tinh chỉnh, điều chỉnh dữ liệu không làm ảnh hưởng, xáo trộn lớn trong nhà trường, một trong những yêu cầu đặt ra là người xếp thời khóa biểu phải quan sát được tất cả các thay đổi của các giáo viên trung gian. Quyết định thực hiện lệnh bao giờ cùng thuộc về con người chứ không phải phần mềm máy tính.

Hình dưới đây cho ta một hình ảnh người dùng có thể quan sát tất cả các giáo viên trung gian bị thay đổi dữ liệu trong khi thực hiện tinh chỉnh.


3. Vì sao cần tinh chỉnh tối ưu?

Trong các phiên bản TKB từ 7.0 trở về trước, khi thực hiện các lệnh tinh chỉnh dữ liệu, phương pháp đánh giá duy nhất các giáo viên trung gian là phải quan sát trực tiếp các thay đổi dữ liệu bằng mắt trên màn hình. Phiên bản TKB 6.5 có thêm chức năng tự động đánh giá sự thay đổi dữ liệu của các giáo viên trung gian. Tuy nhiên chức năng này chỉ trợ giúp được một phần cho các thao tác tinh chỉnh dữ liệu.

Vấn đề quan trọng nhất được đặt ra cho các chức năng tinh chỉnh dữ liệu thời khóa biểu là làm thế nào để điều khiển các thay đổi của các giáo viên trung gian một cách tối ưu hơn? Có cách nào kiểm soát được sao cho tất cả các giáo viên trung gian bị ít xáo trộn nhất hay nói cách khách sự thay đổi dữ liệu của các giáo viên trung gian là tối ưu nhất?

Do vậy bài toán tinh chỉnh dữ liệu thời khóa biểu yêu cầu tìm ra một thuật toán sao cho tất cả các thay đổi của giáo viên trung gian phải là tối ưu nhất, nghĩa là không làm cho các thời khóa biểu của giáo viên trung gian bị xấu đi. Thuật toán tinh chỉnh thỏa mãn các điều kiện nói trên sẽ được gọi là thuật toán tinh chỉnh tối ưu.

Trong phiên bản mới nhất TKB 7.5 đã lần đầu tiên đưa vào một thuật toán tối ưu như vậy, đó là thuật toán OpCX/OpDPR.

4. Thuật toán tinh chỉnh tối ưu OpCX/OpDPR trong phần mềm TKB 7.5

Thuật toán OpCX/OpDPR được đưa vào từ phiên bản TKB 7.5 và được áp dụng cho cả 3 lệnh tinh chỉnh là Move To, Push Out và CX.

Ý tưởng của thuật toán này như sau:

Phần mềm sẽ kiểm tra tất cả các thay đổi của các giáo viên trung gian khi tinh chỉnh dữ liệu. Phần mềm sẽ đưa ra một bộ điều kiện "tối ưu" cho phép kiểm tra tất cả các dịch chuyển tiết của các giáo viên trung gian, nếu các dịch chuyển này thỏa mãn các điều kiện tối ưu thì mới thực hiện. Các tiêu chuẩn "tối ưu" của thuật toán này bao gồm 10 tiêu chí sau:

Tiêu chuẩn này áp dụng cho từng dịch chuyển tiết. Nếu phương án dịch chuyển thỏa mãn tất cả các tiêu chuẩn đã lựa chọn thiư phương án chuyển này được gọi là tối ưu.

Thuật toán OpCX/OpDPR đảm bảo rằng tất cả các dịch chuyển của các giáo viên trung gian đều là tối ưu theo nghĩa trên đây.

Mô tả ngắn thuật toán OpCX/OpDPR:

Thuật toán mới OpCX/OpDPR được đưa ra trong TKB 7.5 đã giải quyết được vấn đề được đặt ra: toàn bộ các giáo viên trung gian sẽ có các thay đổi ít bị ảnh hưởng nhất. Hay nói cách khác, thuật toán mới OpCX/OpDPR thực sự là thuật toán tinh chỉnh tối ưu đúng theo tên gọi của nó.

Như tên gọi của thuật toán đã rõ, thuật toán này là một mở rộng trực tiếp của các thuật toán tinh chỉnh CX, DPR, DPR-1e đã có từ các phiên bản TKB trước đây. Điểm khác biệt nhất của thuật toán OpCX/OpDPR là ở tính tối ưu (ký hiệu Op - Optimal) của thuật toán: toàn bộ các giáo viên trung gian đều được điều chỉnh một cách "tối ưu" nhất. Do vậy thuật toán này đảm bảo ít ảnh hưởng nhất đến các giáo viên trung gian tham gia vào quá trình thay đổi dữ liệu.

Cũng như các thuật toán tinh chỉnh dữ liệu khác của phần mềm TKB (CX, FPR, DPR, DPR-1e), thuật toán OpCX/OpDPR có thể sử dụng với các lệnh: CX, Push Out và Move To. Qui trình thực hiện tương tự như các thuật toán đã có của phần mềm.

Một số chú ý quan trọng khi sử dụng thuật toán OpCX/OpDPR:

1. Khi thực hiện lệnh tinh chỉnh dữ liệu sử dụng OpCX/OpDPR,phần mềm sẽ tìm duyệt tất cả các phương án "tối ưu" và cho phép người dùng quan sát từng phương án trên màn hình. Người dùng có quyền chọn bất kỳ phương án nào nếu muốn.

2. Phần mềm cho phép lựa chọn 1 trong cách thực hiện khác nhau của thuật toán này:

- Cách 1: chỉ tìm 1 phương án đầu tiên và dừng. Người dùng sẽ chỉ quan sát được 1 phương án.

- Cách 2: tìm tất cả các phương án và cho phép người dùng quan sát chi tiết từng phương án để lựa chọn.

3. Thuật toán OpCX/OpDPR có hai phương án/kiểu thực hiện:

OpCX: Các giáo viên thay đổi thời khóa biểu cùng dạy một lớp.

OpDPR: Tổng quát, các giáo viên thay đổi thay đổi thời khóa biểu có thể bất kỳ trong nhà trường.

Hay nói cách khác thuật toán OpCX/OpDPR có hai kiểu thực hiện, một là OpCX - tổng quát thuật toán CX và OpDPR - tổng quát thuật toán DPR-1e. Việc phần mềm sẽ chọn phương án nào để thực hiện được cài đặt trong lệnh Các lựa chọn của phần mềm.

4. Chú ý phân biệt thuật toán tinh chỉnh tối ưu OpCX/OpDPR và lệnh Các phương án chuyển tiết tối ưu, lệnh Chuyển tiết tối ưu đã có trong phiên bản TKB 7.0.

- Lệnh Chuyển tiết tối ưu (hay Các phương án chuyển tiết tối ưu) có trong TKB 7.0 chỉ ra vị trí cần chuyển tiết từ 1 vị xấu đến 1 vị trí tối ưu khác nhưng không liên quan đến thuật toán tinh chỉnh được dùng để dịch chuyển.

- Ngược lại thuật toán OpCX/OpDPR dùng để thực hiện việc tinh chỉnh thông qua các bước dịch chuyển giáo viên trung gian một cách tối ưu.

Do vậy nếu kết hợp lệnh Chuyển tiết tối ưu có từ TKB 7.0 và thuật toán OpCX/OpDPR sẽ được kết quả tối ưu hoàn toàn của việc dịch chuyển tiết trên TKB giáo viên.

5. Các lựa chọn của thuật toán tinh chỉnh tối ưu được thực hiện từ cửa sổ lệnh Các lựa chọn --> Thuật toán tinh chỉnh TKB như hình dưới đây.


Kết luận

Thuật toán tinh chỉnh tối ưu OpCX/OpDPR thực sự là một phát trển mới đột phá của TKB 7.5. Với thuật toán này việc tinh chỉnh dữ liệu trên TKB lớp và giáo viên có thể được thực hiện nhanh chóng đảm bảo ít bị ảnh hưởng nhất đến các giáo viên khác trong nhà trường. Thuật toán tinh chỉnh tối ưu OpCX/OpDPR sẽ là thuật toán trung tâm của các phát triển tiếp theo của phần mềm TKB theo hướng mở rộng các tính năng tối ưu hóa thời khóa biểu giáo viên.
URL của bài viết này::http://www.vnschool.net/modules.php?name=TKB&file=article&sid=3196
© Cong ty Cong Nghe Tin hoc Nha truong contact: sales@schoolnet.vn