Trang chủ   Sản phẩm   Phần mềm Dành cho nhà trường   Phần mềm Hỗ trợ học tập   Kho phần mềm   Liên hệ   Đăng nhập | Đăng ký

Tìm kiếm

TKB Application System

Đại Lý - Chi Nhánh
 
Hỗ trợ trực tuyến
Hỗ trợ kỹ thuật
(Bùi Văn Khoa)
Trang thông tin hỗ trợ khách hàng
 
Đăng nhập/Đăng ký
Bí danh
Mật khẩu
Mã kiểm traMã kiểm tra
Lặp lại mã kiểm tra
Ghi nhớ
 
Quên mật khẩu | Đăng ký mới
 
Xem bài viết theo các chủ đề hiện có
  • Hoạt động của công ty (50 bài viết)
  • Hỗ trợ khách hàng (123 bài viết)
  • TKB và bài toán xếp Thời khóa biểu (237 bài viết)
  • Dành cho Giáo viên (9 bài viết)
  • Sản phẩm mới (13 bài viết)
  • Download - Archive- Update (20 bài viết)
  • Thông tin khuyến mại (6 bài viết)
  • Mô hình & Giải pháp (12 bài viết)
  • School@net 15 năm (16 bài viết)
  • Xem toàn bộ bài viết (487 bài viết)
  •  
    Thành viên có mặt
    Khách: 7
    Thành viên: 0
    Tổng cộng: 7
     
    Số người truy cập
    Hiện đã có 54679512 lượt người đến thăm trang Web của chúng tôi.

    Lịch sử phần mềm xếp thời khóa biểu TKB (14): các thuật toán tinh chỉnh tối ưu thời khóa biểu

    Ngày gửi bài: 03/01/2013
    Số lượt đọc: 17358

    thời khóa biểuTrong phần trước tôi đã nói về các công cụ, các tiện ích trong phần mềm TKB có liên quan đến tối ưu hóa, làm đẹp thời khóa biểu. Các khái niệm, công cụ này không được xây dựng ngay một lúc mà được phát triển dần qua các phát triển từ phiên bản TKB 6.0 năm 2006 đến TKB 9.0 năm 2012.

    Tuy nhiên một trong những vấn đề quan trọng nhất của các phát triển này chính là các thuật toán tinh chỉnh dữ liệu thời khóa biểu chính của phần mềm. Đó là các thuật toán tinh chỉnh:

    CX - Conditional eXecution - xếp có điều kiện.

    DPR - Dynamic Position Replacement - dịch chuyển vị trí động.

    FPR - Fix Position Replacement - dịch chuyển vị trí cố định.

    Đây là 3 thuật toán tinh chỉnh dữ liệu chính của phần mềm TKB mà tôi đã từng nhắc đến trong các bài viết trước đây. Chúng đóng vai trò quan trọng không những trong chức năng xếp tự động 100% thời khóa biểu (lệnh SF) mà còn trong toàn bộ việc tinh chỉnh dữ liệu sau khi xếp xong thời khóa biểu.

    Một trong những bài toán đặt ra chính của vấn đề tối ưu hóa thời khóa biểu là:

    Khi cần tinh chỉnh, điều chỉnh dữ liệu cho một giáo viên A (việc này sẽ làm cho A tốt lên), sẽ có một số giáo viên khác bị thay đổi theo, ví dụ các giáo viên bị thay đổi là B, C, ..., Z. Có cách nào để kiểm soát được sự thay đổi dữ liệu thời khóa biểu của các giáo viên B, C, ..., Z này? Có hay không một thuật toán mà sau khi thay đổi giáo viên A nhưng các giáo viên B, C, ...., Z không bị xấu đi?

    Như chúng ta đã biết bài toán trên thoạt đầu có vẻ như không tưởng và mâu thuẫn. Trong mô hình phức tạp của bài toán xếp thời khóa biểu luôn tuân theo nguyên tắc bù trừ: để giáo viên A tốt lên, các giáo viên B, C, ..., Z phải bị xấu đi để cân bằng. Vậy bài toán mà chúng tôi đặt ra ở trên liệu có khả thi hay không? Hay cần hiểu bài toán này theo một nghĩa khác?

    Cách giải quyết của chúng tôi trong vấn đề này như sau:

    - Chúng tôi đã xây dựng được các tiêu chí để đánh giá việc di chuyển 1 tiết trên thời khóa biểu có phải là tối ưu hay không. Có 10 tiêu chí để đánh giá như vậy.

    Có 10 tiêu chí đánh giá dịch chuyển tiết tối ưu như vậy:

    1. Không vi phạm ràng buộc Nghỉ, Hạn chế, Bận

    2. Không vi phạm ràng buộc không dạy theo tiết

    3. Không vi phạm ràng buộc nghỉ các ngày cụ thể

    4. Không vi phạm ràng buộc về số tiết dạy max trong ngày

    5. Không vi phạm ràng buộc không dạy qua trưa

    6. Không vi phạm ràng buộc dạy qua giờ nghỉ giải lao

    7. Không vi phạm ràng buộc tính chất môn học

    8. Không làm tăng tiết trống

    9. Không làm giảm số buổi nghỉ

    10. Không làm giảm số ngày nghỉ

    Theo cách xây dựng của chúng tôi việc di chuyển 1 tiết học được coi là “tốt” hay “tối ưu” nếu thỏa mãn tất cả 10 tiêu chí trên. Nếu chỉ không thỏa mãn 1 trong 10 tiêu chí trên cũng sẽ bị đánh giá việc chuyến tiết này là “không tối ưu”.

    - Khi thực hiện lệnh tinh chỉnh dữ liệu thời khóa biểu, ví dụ: dịch chuyển giáo viên A. Việc tinh chỉnh này sẽ được thuật toán hóa và kéo theo thực hiện N lệnh di chuyển tiết khác, ví dụ cụ thể như sau:

    Thay đổi 1: ô thời khóa biểu p1 được dịch chuyển vị trí.

    Thay đổi 2: ô thời khóa biểu p2 được dịch chuyển vị trí.
    .....

    Thay đổi N: ô thời khóa biểu pN được dịch chuyển vị trí.

    Như vậy bài toán “tinh chỉnh tối ưu hóa” được đặt ra ở trên có thể phát biểu như sau: có hay không một thuật toán mà sau khi thay đổi giáo viên A theo ý muốn thì tất cả các thay đổi tương ứng của các vị trí p1, p2, ..., pN như trên vẫn là “tối ưu”? Như vậy bài toán được đặt ra rất rõ ràng, correct và hoàn toàn nằm trong phạm vi của ngôn ngữ thuật toán. Và chúng tôi đã tìm cách giải quyết theo hướng đi này.


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

    School@net



     Bản để in  Lưu dạng file  Gửi tin qua email


    Những bài viết khác:



    Lên đầu trang

     
    CÔNG TY CÔNG NGHỆ TIN HỌC NHÀ TRƯỜNG
     
    Phòng 1407 - Nhà 17T2 - Khu Trung Hoà Nhân Chính - Quận Cầu Giấy - Hà Nội
    Điện thoại: (04) 62511017 - Fax: (04) 62511081
    Email: school.net@hn.vnn.vn


    Bản quyền thông tin trên trang điện tử này thuộc về công ty School@net
    Ghi rõ nguồn www.vnschool.net khi bạn phát hành lại thông tin từ website này
    Site xây dựng trên cơ sở hệ thống NukeViet - phát triển từ PHP-Nuke, lưu hành theo giấy phép của GNU/GPL.