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: 13
    Thành viên: 0
    Tổng cộng: 13
     
    Số người truy cập
    Hiện đã có 55263542 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 (15): thuật toán tinh chỉnh tối ưu đầu tiên: OpCX/OpDPR

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

    thời khóa biểuNhư vậy một trong những bài toán chính của việc tối ưu hóa dữ liệu là thiết kế các thuật toán tinh chỉnh dữ liệu tối ưu.

    Không phải ngay từ đầu bài toán "tối ưu hóa" các thuật toán tinh chỉnh dữ liệu đã được đặt ra rõ ràng như ngày hôm nay.


    Năm 2007, phiên bản TKB 6.5 đã đưa vào được khái niệm các tiêu chí đánh giá thay đổi dữ liệu GV (12 tiêu chí dã nói trong các phần trước). Từ phiên bản này trở đi các lệnh tinh chỉnh dữ liệu chính như CX, Push Out, Move To sẽ có thêm bảng đánh giá kết quả thực hiện lệnh bằng các tiêu chí trên cho từng GV bị thay đổi của lệnh.

    Năm 2008, phiên bản TKB 7.0 đã đưa thêm vào các tiêu chí đánh giá một TKB GV bằng cách đưa vảo tiêu chí đánh giá 1 tiết học là xấu hay tốt (10 tiêu chí) và 12 tiêu chí đánh giá định lượng và yêu cầu của GV. Cũng trong TKB 7.0 đã đưa ra khái niệm các tiêu chí Chuyển tiết tối ưu (10 tiêu chí, đã nói trong phần trước). Như vậy phải đến 2 năm sau đó, năm 2009, các công việc chuẩn bị cho việc thiết kế chính thức một thuật toán tinh chỉnh tối ưu mới được đặt ra cụ thể. Thuật toán mà chúng tôi chọn để thiết kế là thuật toán CX và DPR.

    Hai thuật toán CX và DPR có nhiều điểm chung, thực chất CX là một trường hợp riêng của DPR.

    Mô hình đơn giản của thuật toán DPR như sau:

    Giả sử cần chuyển 1 tiết học trên thời khóa biểu của một giáo viên A từ vị trí này sang vị trí khác (do yêu cầu của A). Việc chuyển này được viết thành mô hình như sau:

    P0 ---> P1 (1)

    Nếu vị trí tiết học tại P1 (môn học, lớp, giáo viên) có thể chuyển ngay về P0 thì quá trình (1) sẽ kết thúc ngay:

    P0 --> P1 --> P0 (2)

    Nhưng thực tế không bao giờ xảy ra như vậy, do đó thể thực hiện được bài toán (1) sẽ phải kéo theo thực hiện một dây biến đổi:

    P0 --> P1 --> P2 --> .... --> PN (3)

    Chính xác hơn ở đoạn cuối của (3) phải viết đầy đủ là PN --> P0, tuy nhiên tôi sẽ bỏ qua cách viết này.

    Như vậy bản chất của một thuật toán tinh chỉnh dữ liệu thời khóa biểu là muốn có (1) phải thực hiện (3).

    Thuật toán này được gọi là "tối ưu" nếu toàn bộ các dịch chuyển trung gian Pi-1 --> Pi phải là tối ưu.

    Sau một thời gian mò mẫm thử nghiệm, năm 2009, chúng tôi đã thành công trong việc thiết kế một thuật toán tinh chỉnh tối ưu như vậy. Thuật toán này là một mở rộng trực tiếp của 2 thuật toán CX, DPR và chúng tôi đặt tên thuật toán mới là OpCX/OpDPR.

    Tháng 7 năm 2009, phiên bản TKB 7.5 ra đời với một thuật toán tinh chỉnh tối ưu mới: OpCX/OpDPR. Thật là kỳ diệu vì khi sử dụng thuật toán này, trên các bảng đánh giá tiêu chí mà chúng tôi đưa ra, hầu hết các đánh giá giáo viên trung gian là "Xanh" tức là Tốt lên.
    OpCX/OpDPR là thuật toán tinh chỉnh tối ưu đầu tiên của Công ty School@net cũng như của Việt Nam đã thực hiện được yêu cầu sau:

    - Khi thực hiện thuật toán này thành công cho 1 GV A, tất cả các giáo viên bị thay đổi thời khóa biểu khác B, C, ..., Z sẽ không bị "xấu đi", chỉ có thể bằng hoặc tốt lên.

    Phần mềm TKB 7.5 ra đời với thuật toán tinh chỉnh tối ưu OpCX/OpDPR đã gây 1 tiếng vang lớn và được các nhà trường đón nhận.

    Tuy nhiên hãy còn 1 thuật toán nữa chưa tối ưu được, đó là thuật toán FPR.


    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.