Tài liệu Luận văn nghiên cứu bài toán lập lịch và ứng dụng xếp thời khóa biểu cho trường phổ thông vùng cao việt bắc

ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG HOÀNG PHÚC LỢI NGHIÊN CỨU BÀI TOÁN LẬP LỊCH VÀ ỨNG DỤNG XẾP THỜI KHÓA BIỂU CHO TRƢỜNG PHỔ THÔNG VÙNG CAO VIỆT BẮC LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Thái Nguyên - 2017 ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG HOÀNG PHÚC LỢI NGHIÊN CỨU BÀI TOÁN LẬP LỊCH VÀ ỨNG DỤNG XẾP THỜI KHÓA BIỂU CHO TRƢỜNG PHỔ THÔNG VÙNG CAO VIỆT BẮC Chuyên ngành: Khoa học máy tính Mã số: 60 48 01 01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Ngƣời hƣớng dẫn khoa học: TS. TRƢƠNG HÀ HẢI Thái Nguyên - 2017 i LỜI CAM ĐOAN Tôi xin cam đoan luận văn là công trình nghiên cứu của riêng cá nhân tôi, không sao chép của ai, do tôi tự nghiên cứu, đọc, dịch tài liệu, tổng hợp và thực hiện. Nội dung lý thuyết trong trong luận văn tôi có sử dụng một số tài liệu tham khảo nhƣ đã trình bày trong phần tài liệu tham khảo. Các số liệu, chƣơng trình phần mềm và những kết quả trong luận văn là trung thực và chƣa đƣợc công bố trong bất kỳ một công trình nào khác. Thái nguyên 19 tháng 06 năm 2017 Học viên thực hiện Hoàng Phúc Lợi ii LỜI CẢM ƠN Lời đầu tiên, em xin gửi lời biết ơn sâu sắc đến TS. Trƣơng Hà Hải ngƣời đã tận tình hƣớng dẫn, chỉ bảo, giúp đỡ em trong suốt quá trình làm luận văn. Em cũng xin gửi lời cảm ơn đến các thầy giáo, cô giáo trƣờng Đại học Công Nghệ Thông Tin và Truyền Thông Thái Nguyên, các thầy giáo, cô giáo Viện Công nghệ thông tin đã truyền đạt những kiến thức và giúp đỡ em trong suốt quá trình học của mình. Và cuối cùng tôi xin gửi lời cảm ơn tới các đồng nghiệp, gia đình và bạn bè những ngƣời đã ủng hộ, động viên tạo mọi điều kiện giúp đỡ để tôi có đƣợc kết quả nhƣ ngày hôm nay. Thái Nguyên 19, tháng 06 năm 2017 Học Viên Hoàng Phúc Lợi iii MỤC LỤC LỜI CAM ĐOAN .......................................................................................... i LỜI CẢM ƠN ............................................................................................... ii MỤC LỤC .................................................................................................... iii DANH MỤC HÌNH ẢNH ............................................................................ v DANH MỤC BẢNG BIỂU ......................................................................... vi MỞ ĐẦU ....................................................................................................... 1 CHƢƠNG 1: TỔNG QUAN VỀ BÀI TOÁN LẬP LỊCH ........................... 4 1.1. Giới thiệu chung về bài toán lập lịch ................................................. 4 1.2. Các đặc trƣng của bài toán lập lịch .................................................... 4 1.3. Một số ví dụ về bài toán lập lịch: ....................................................... 5 1.4. Bài toán xếp thời khóa biểu ở trƣờng phổ thông ............................... 7 1.4.1. Giới thiệu bài toán xếp thời khóa biểu ........................................ 7 1.4.2. Độ phức tạp của bài toán xếp thời khóa biểu .............................. 9 1.4.3. Phân loại mô hình xếp thời khóa biểu....................................... 10 1.4.4. Các đặc thù của thời khóa biểu hệ trung học phổ thông ........... 12 1.4.5. Nhu cầu bài toán xếp thời khóa biểu......................................... 14 CHƢƠNG 2: MỘT SỐ HƢỚNG TIẾP CẬN VÀ THUẬT TOÁN GIẢI BÀI TOÁN XẾP THỜI KHÓA BIỂU. ....................................................... 17 2.1. Đề xuất các giải thuật giải bài toán .................................................. 17 2.1.1. Giải thuật vét cạn. ..................................................................... 17 2.1.2. Giải thuật chia để trị .................................................................. 17 2.1.3. Giải thuật Heuristic: .................................................................. 19 2.2. Đánh giá các phƣơng pháp: .............................................................. 20 2.3. Giới thiệu giải thuật tối ƣu hóa đàn kiến (ANT COLONY OPTIMIZATION: ACO) ........................................................................ 22 2.4. Mô tả giải thuật tối ƣu hóa đàn kiến ................................................ 24 2.4.1. Trình bày giải thuật ................................................................... 24 iv 2.4.2. Một số vấn đề liên quan ............................................................ 29 CHƢƠNG 3: XÂY DỰNG CHƢƠNG TRÌNH XẾP THỜI KHÓA BIỂU CHO TRƢỜNG PHỔ THÔNG VÙNG CAO VIỆT BẮC ......................... 32 3.1. Phân tích quy trình thực hiện bài toán ............................................. 32 3.1.1. Phát biểu bài toán ...................................................................... 32 3.1.2. Bài toán xếp thời khóa biểu trong mô hình tổng thể................. 33 3.1.3. Đặc điểm công tác, kế hoạch đào tạo ........................................ 33 3.1.4. Quy trình xây dựng kế hoạch đào tạo thời khóa biểu ............... 34 3.2. Sơ đồ xây dựng chƣơng trình xếp thời khóa biểu ............................ 35 3.2.1. Xây dựng hệ thống .................................................................... 39 3.2.2. Đánh giá khả năng ứng dụng giải quyết bài toán xếp thời khóa biểu42 3.4. Thiết kế chƣơng trình. ...................................................................... 44 3.4.1. Lớp học ..................................................................................... 49 3.4.2. Giáo viên ................................................................................... 50 3.4.3. Phòng học .................................................................................. 50 3.4.4. Nhân viên phòng đào tạo .......................................................... 50 3.4.5 Mô hình ca sử dụng .................................................................... 50 3.5. Các chức năng chính của chƣơng trình ............................................ 51 3.5.1. Chức năng đăng nhập ( chức năng quản lý user ) ..................... 51 3.5.2. Chức năng Quản lý môn học..................................................... 52 3.5.3. Chức năng Quản lý giáo viên .................................................... 55 3.5.4. Chức năng Quản lý học sinh: .................................................... 58 3.5.5. Chức năng Quản lý lớp học ...................................................... 60 3.6. Kết quả thử nghiệm .......................................................................... 62 ẾT UẬN ................................................................................................. 64 HƢỚNG PHÁT TRIỂN .............................................................................. 65 TÀI LIỆU THAM KHẢO ........................................................................... 66 v DANH MỤC HÌNH ẢNH Hình 2.1: Đồ thị cấu trúc tổng quát cho bài toán cực trị hàm .. 26 Hình 2.2: Lựa chọn đỉnh đi tiếp theo .......................................................... 27 Hình 2.3: Đặc tả thuật toán ACO ................................................................ 28 Hình 3.1: Sơ đồ xây dựng chƣơng trình T B ................................................. 35 Hình 3.2: Chức năng của hệ thống .............................................................. 40 Hình 3.3 Mô hình cơ sở dữ liệu .................................................................. 48 Hình 3.4: Mô hình các ca sử dụng .............................................................. 50 Hình 3.5: Giao diện của chƣơng trình ......................................................... 51 Hình 3.6: Giao diện đăng nhập ................................................................... 52 Hình 3.7: Mô hình chức năng quản lý môn học.......................................... 53 Hình 3.8: Giao diện thêm môn học ............................................................. 54 Hình 3.9:Giao diện chỉnh sửa môn ............................................................. 54 Hình 3.10: Mô hình chức năng quản lý giáo viên....................................... 55 Hình 3.11:Giao diện thêm giáo viên ........................................................... 56 Hình 3.12:Giao diện chỉnh sửa.................................................................... 56 Hình 3.13:Giao diện thời khóa biểu của từng giáo viên ............................. 57 Hình 3.14: Chức năng Quản lý học sinh ..................................................... 58 Hình 3.15:Cập nhật thông tin học sinh ....................................................... 59 Hình 3.16: Cập nhật lại thông tin học sinh ................................................. 59 Hình 3.17: Mô hình chức năng quản lý lớp học ......................................... 60 Hình 3.18: Giao diện môn học .................................................................... 61 Hình 3.19: Kết quả xếp thời khóa biểu theo lớp ........................................ 61 Hình 3.20: Cập nhật thông tin lớp ............................................................... 62 vi DANH MỤC BẢNG BIỂU Bảng 3.1. Ví dụ về TKB của một lớp ......................................................... 36 Bảng 3.2. Ma trận TKB mà kiến xây dựng ................................................. 38 Bảng 3.3. Bảng dữ liệu phân công giảng dạy theo khối ............................. 41 Bảng 3.4. Bảng dữ liệu phân công giảng dạy theo lớp ............................... 41 Bảng 3.5. Bảng dữ liệu phân công giảng dạy theo giáo viên...................... 42 1 MỞ ĐẦU 1. Lý do chọn đề tài Lập lịch biểu là công việc không thể thiếu ở bất kì tổ chức nào hoạt động trong xã hội hiện nay. Cùng với tiến bộ xã hội, khoa học máy tính đã có những bƣớc tiến dài, đem lại sự tiện lợi và hiệu quả kinh tế cao trong rất nhiều lĩnh vực từ công nghiệp cho đến đời sống. Với việc sử dụng máy tính trong lập lịch, con ngƣời có thể xây dựng đƣợc lịch biểu một cách nhanh chóng và tối ƣu hơn. Nhiều phần mềm máy tính có chức năng hỗ trợ lập lịch nhƣ MS.Excel, MS.Project,… nhƣng sự “thiếu thông minh” của chúng vẫn làm cho con ngƣời phải tiêu tốn nhiều thời gian cũng nhƣ công sức khi lập lịch. Nhu cầu cần có phần mềm lập lịch thông minh đã trở thành bức thiết. Tại các trƣờng học, thời khóa biểu kết nối hầu nhƣ toàn bộ các hoạt động của nhà trƣờng. Trƣớc đây công việc xếp thời khóa biểu chủ yếu đƣợc làm bằng tay bởi các cán bộ có kinh nghiệm, nắm vững chuyên môn nghiệp vụ. Do đó việc xây dựng thời khóa biểu phụ thuộc rất lớn vào ngƣời lập lịch, đồng thời hiệu quả tối ƣu cũng còn bị hạn chế.Vì thế bài toán lập thời khóa biểu luôn là một trong những vấn đề quan trọng cần giải quyết. Hiện nay, hầu hết các trƣờng học đã đầu tƣ xây dựng phần mềm xếp thời khóa biểu, mang lại hiệu quả nhất định trong việc xây dựng lịch biểu học tập và làm việc. Đối với các trƣờng Trung học phổ thông thì việc ứng công nghệ thông tin vào xếp thời khóa biểu là rất hạn chế, cụ thể là trƣờng Phổ thông Vùng cao Việt Bắc. Vì vậy ứng dụng xây dựng thời khóa biểu cho trƣờng Phổ thông Vùng cao Việt Bắc là nhu cầu cần thiết. Xuất phát từ nhu cầu đó, em đã lựa chọn đề tài “Nghiên cứu bài toán lập lịch và ứng dụng xếp thời khóa biểu cho trƣờng Phổ Thông Vùng Cao Việt Bắc” làm luận văn tốt nghiệp thạc sỹ. Luận văn nghiên cứu về mô hình bài toán cũng nhƣ quy trình, độ phức tạp của vấn đề xếp thời khóa biểu nói chung và giải quyết bài toán xếp thời khóa 2 biểu chính khóa cho các trƣờng Phổ Thông Trung Học nói chung và trƣờng Phổ Thông Vùng Cao Việt Bắc nói riêng. Sử dụng giải thuật tối ƣu hóa đàn kiến tự động cập nhật thời khóa biểu và đƣa ra phƣơng án khả thi cho bài toán xếp thời khóa biểu. 2. Đối tƣợng và phạm vi nghiên cƣu Đối tƣợng: Nghiên cứu tổng quan bài toán lập lịch và một số thuật toán giải bài toán lập lịch. Phạm vi nghiên cứu: uận văn tập trung nghiên cứu các kiến thức có liên quan, các cơ sở lý thuyết nhƣ: Bài toán lập lịch. Một số thuật toán giải bài toán lập lịch và ứng dụng vào bài toán xếp thời khóa biểu. 3. Mục tiêu và nhiệm vụ - Mục tiêu Hoàn thành sản phẩm là phần mềm xếp thời khóa biểu cho trƣờng Phổ thông Vùng cao Việt Bắc. Tiếp tục phát triển các phần mêm xếp thời khóa biểu cho các trƣờng Phổ thông trung học trên toàn quốc. - Nhiêm vụ Phân tích các số liệu, đề ra giải pháp hợp lý trong việc xây dựng và phát triển hệ thống. Nghiên cứu các giải thuật, áp dụng thuật toán tối ƣu hóa đàn kiến giải quyết bài toán xếp thời khóa biểu cho trƣờng Phổ thông Vùng cao Việt Bắc. Phân tích, đánh giá, đề ra các phƣơng pháp xếp thời khóa biểu một cách tự dộng và chính xác. 4. Phƣơng pháp nghiên cứu - Phƣơng pháp nghiên cứu lý thuyết. - Phƣơng pháp nghiên cứu tài liệu. - Phƣơng pháp quan sát. - Phƣơng pháp phân tích và tổng hợp lý thuyết. - Phƣơng pháp nghiên cứu thực nghiệm. 3 - Phân tích thuật toán đã lựa chọn, xây dựng cấu trúc dữ liệu và cài đặt chƣơng trình. - Tạo các mẫu thử có chất lƣợng để kiểm nghiệm các tính chất của thuật toán, kiểm chúng sự thỏa mãn yêu cầu đặt ra của bài toán. Thực nghiệm: Xây dựng chƣơng trình thời khóa biểu, tích hợp cơ sở dữ liệu với phòng Giáo vụ, tổng hợp lại hệ thống để đƣa ra thời khóa biểu trên Website của trƣờng. 5. Cấu trúc của đề tài Ngoài phần mở đầu và kết luận, bố cục của luận văn đƣợc tổ chức thành 3 chƣơng, gồm: Chương 1: Tổng quan về bài toán lập lịch Giới thiệu về bài toán lập lịch, những đặc trƣng cơ bản và hƣớng tiếp cận nghiên cứu, bài toán xếp thời khóa biểu ở trƣờng phổ thông. Giới thiệu nghiên cứu một dạng cụ thể của bài toán lập lịch là bài toán xếp thời khóa biểu. Chương 2: Một số hướng tiếp cận và thuật toán giải bài toán xếp thời khoá biểu Tìm hiểu về một số giải thuật giải bài toán, đánh giá các giải thuật và đề xuất giải thuật giải bài toán. Chương 3: Thiết kế chương trình xếp thời khóa biểu chính khóa trường Phổ Thông Vùng Việt Bắc Phân tích thiết kế hệ thống, áp dụng giải thuật tối ƣu hóa đàn kiến, đánh giá khả năng ứng dụng để giải quyết bài toán thời khóa biểu. Các bƣớc thực hiện: thiết kế dữ liệu, ý tƣởng thuật toán, xây dựng chƣơng trình, nhận xét. 4 CHƢƠNG 1: TỔNG QUAN VỀ BÀI TOÁN LẬP LỊCH 1.1. Giới thiệu chung về bài toán lập lịch Bài toán cần xác định trình tự thời gian thực hiện các công việc trong điều kiện ràng buộc về tài nguyên cần thiết sử dụng để thực hiện các công việc bài toán đó đƣợc phân loại là Bài toán lập lịch. - Lập lịch có thể đƣợc định nghĩa là một bài toán tìm kiếm chuỗi tối ƣu để thực hiện một tập các hoạt động chịu tác động của một tập các ràng buộc cần phải đƣợc thỏa mãn. Ngƣời lập lịch thƣờng cố gắng thử đến mức tối đa sự sử dụng các cá thể, máy móc và tối thiểu thời gian đòi hỏi để hoàn thành toàn bộ quá trình nhằm sắp xếp lịch. Vì thế bài toán lập lịch là một vấn đề rất khó để giải quyết. Hiện nay có nhiều khả năng để phát triển các kỹ thuật hiện tại để giải quyết bài toán này. Những kỹ thuật đó bao gồm: Các tiếp cận Trí tuệ nhân tạo nhƣ hệ thống tri thức cơ sở (knowledge-based systems), bài toán thoả mãn ràng buộc, hệ chuyên gia, mạng Nơron và các tiếp cận của các nghiên cứu hoạt động: lập trình tính toán, lập trình động, tìm kiếm nhánh và đƣờng biên, kỹ thuật mô phỏng, tìm kiếm Tabu và phƣơng pháp nút cổ chai 1.2. Các đặc trƣng của bài toán lập lịch Khi nghiên cứu về bài toán lập lịch cần làm rõ các đặc trƣng cơ bản của bài toán. Các đặc trƣng cơ bản đó bao gồm: Tập công việc, tài nguyên, tác vụ, ràng buộc và mục tiêu. - Tập công việc: Mô tả tính chất công việc (lập danh sách môn học, lập danh sách giáo viên, lập danh sách phòng học, lập bảng thông tin môn học.....) - Tài nguyên: Là các dữ liệu đầu vào để giải quyết bài. Các tài nguyên này có thể phục hồi hoặc không. 5 - Thời gian giới hạn: Mô tả các dạng thời gian (trình tự, thời điểm, khoảng thời gian – ca học – tiết học,....) - Ràng buộc: Đây là những điều kiện cần thỏa mãn để bài toán có thể đƣa đƣợc lời giải tốt nhất. - Mục tiêu: Đánh giá độ tối ƣu của lịch trình lời giải của bài toán. Khi các mục tiêu đƣợc thỏa mãn thì các ràng buộc cũng đƣợc thỏa mãn. Đánh giá độ phức tạp của bài toán lập lịch: vấn đề ràng buộc tài nguyên trong bài toán lập lịch rất đa dạng và phức tạp. Thông thƣờng các vấn đề liên quan đến ràng buộc về tài nguyên trong bài toán lập lịch thƣờng xảy ra trong tình huống lƣợng tài nguyên là khan hiếm, hạn chế. Nhƣ vậy đặc trƣng công việc đối với vấn đề tài nguyên đó là lƣợng thời gian hoàn thành công việc, yêu cầu phân bổ tài nguyên cho công việc. Các công việc có thể đƣợc thực hiện theo một số phƣơng pháp khác nhau nhƣng có điểm chung đó là đƣợc xác định bởi một quy tắc ràng buộc, các công việc đƣợc thực hiện theo dây chuyền, một số công việc chỉ đƣợc thực hiện sau khi đã thực hiện xong một số công việc khác. 1.3. Một số ví dụ về bài toán lập lịch: a. Bài toán lập lịch cho 2 máy: phải đƣợc lần lƣợt gia công trên 2 Xét mỗi một chi tiết máy A, B. Thời gian gia công chi tiết trên máy A là trên máy B là (i=1,2,...,N). Hãy tìm lịch trình tự gia công) các chi tiết trên hai máy sao cho việc hoàn thành gia công tất cả các chi tiết là sớm nhất. Thuật toán Johnson: Chia các chi tiết thành 2 nhóm: nhóm < , tức là tức là và nhóm gồm các chi tiết thoả mãn gồm các chi tiết thoả mãn thoả mãn xếp vào . Các chi tiết nhóm nào cũng đƣợc. Sắp xếp các chi tiết trong theo chiều tăng của các 6 và sắp xếp các chi tiết trong đuôi theo chiều giảm của các nối vào , dãy thu đƣợc đọc từ trái sang phải) sẽ là lịch gia công. b. Bài toán lập lịch cho 3 máy: Xét bài toán gia công N chi tiết trên 3 máy theo thứ tự A,B,C với bảng thời gian (i=1,2,..N) thoả mãn: hoặc Thuật toán: Lịch gia công tối ƣu trên 3 máy sẽ trùng với lịch gia công tối ƣu trên 2 máy: máy thứ nhất với thời gian thời gian và máy thứ hai với . Thuật toán More Có n ôtô đƣa vào xƣởng sửa chữa đƣợc đánh số thứ tự 1,2..,n. Ôtô phải sửa chữa trong thời gian và thời điểm phải bàn giao là . Mỗi thời điểm xƣởng chỉ sửa chữa một cái, xƣởng sửa chữa không ngừng và thời điểm bắt đầu sửa chữa là 0. Hãy đƣa ra một thứ tự sửa chữa sao cho số lƣợng ôtô đúng hạn là lớn nhất. Sắp xếp theo thứ tự tăng dần của thời điểm bàn giao. Duyệt từ đầu cho đến khi gặp ôtô quá hạn đầu tiên (Giả sử là ôtô thứ k). Tìm từ đầu cho đến ôtô thứ k, ôtô nào có lớn nhất (Giả sử đó là ôtô thứ m). Nếu ôtô này đã đƣợc chuyển một lần rồi thì dừng chƣơng trình, còn nếu không thì ta chuyển ôtô này xuống cuối. Rồi trở lại bƣớc 2. Bài toán lập lịch là dạng bài toán quan trọng đƣợc nghiên cứu trong các môi trƣờng tính toán. Quá trình lập lịch là quá trình quyết định sẽ thực thi công việc tại một nguồn tài nguyên cụ thể nào và vào thời điểm nào là thích hợp nhất bởi công việc đó sẽ ảnh hƣởng rất lớn đến hiệu năng hoạt động của hệ thống. Nhu cầu cần sử dụng bài toán lập lịch là rất lớn trên thực tế. Hầu nhƣ mọi lĩnh vực liên quan đến quản lý, điều hành đều phải sử dụng đến bài toán lập lịch. 7 Hiện nay có nhiều phƣơng pháp nghiên cứu, phát triển để giải quyết bài toán này. Những kỹ thuật đó bao gồm: - Các tiếp cận trí tuệ nhân tạo nhƣ: Hệ thống cơ sở tri thức (knowledgebased systems), bài toán thoả mãn ràng buộc, hệ chuyên gia, mạng Neural, tìm kiếm, tìm kiếm chọn lọc, thuật toán Heuristic, thuật toán tô màu đồ thị, thuật toán luồng… - Các tiếp cận dựa trên những nghiên cứu hoạt động: Lập trình tính toán, lập trình động, tìm kiếm nhánh và đƣờng biên, kỹ thuật mô phỏng, tìm kiếm Tabu search, phƣơng pháp nút cổ chai... Bài toán lập lịch có rất nhiều ứng dụng trong thực tế nhƣ: Bài toán lập lịch xếp thời khóa biểu cho các trƣờng đại học, cao đẳng, các trƣờng phổ thông…, lập lịch phân công công tác cho một công ty, doanh nghiệp, lập lịch cho hệ thống tính toán lƣới trắc địa, lập lịch cho bộ xử lý CPU… 1.4. Bài toán xếp thời khóa biểu ở trƣờng phổ thông 1.4.1. Giới thiệu bài toán xếp thời khóa biểu Trong một cơ quan, một tổ chức, một trƣờng học công việc quản lý và sắp xếp công việc cho các cá nhân, các nhóm trong từng giai đoạn và thời điểm cũng nhƣ địa điểm một cách hợp lý và khoa học là hết sức cần thiết và cấp bách. Công việc đó dựa trên các bài toán lập lịch và việc tìm lời giải tối ƣu cho các bài toán này vẫn là hƣớng nghiên cứu mà rất nhiều cá nhân, tổ chức hƣớng tới và cũng có nhiều công trình nghiên cứu về vấn đề này. Trong phạm vi một trƣờng học cũng có nhiều bài toán lập lịch, trong đó tiêu biểu là bài toán xếp thời khóa biểu. Bài toán này nhằm sắp xếp lịch hoạt động giảng dạy và học tập của giáo viên và học sinh. Sau đây chúng ta đi tìm hiểu bài toán lập thời khóa biểu chính khóa, theo tuần, theo học kỳ, theo năm học của trƣờng Phổ thông trung học: - Bƣớc 1: Lập kế hoạch đào tạo (dựa vào khung chƣơng trình đào tạo của Nhà trƣờng theo các qui định của Ngành giáo dục). 8 - Bƣớc 2: Lập kế hoạch đào tạo theo tuần, theo học kỳ. - Bƣớc 3: Xây dựng bảng phân công giáo viên. - Bƣớc 4: Xây dựng bảng phân công từng lớp, từng khối. - Bƣớc 5: Xây dựng thời khóa biểu. - Bƣớc 6: Hoàn chỉnh thời khóa biểu tổng thể cho giáo viên, lớp học. Bài toán xếp thời khóa biểu trong các nhà trƣờng là bài toán cần phải thỏa mãn những ràng buộc hết sức phức tạp và nhiều khi là mâu thuẫn của các đối tƣợng. Việc đƣa ra một bảng thời khóa biểu hợp lý không những làm mất nhiều thời gian và công sức của ngƣời lập lịch mà đôi khi còn gây ra mâu thuẫn nhƣ thỏa mãn nhu cầu của ngƣời hay nhóm ngƣời này lại phạm vào nhu cầu của ngƣời hay nhóm ngƣời khác. Vấn đề xây dựng thời khóa biểu tự động hoặc bán tự động cho các loại công việc khác nhau bao gồm cả các hoạt động dạy và học trong một trƣờng học là một vấn đề cấp thiết đã thu hút nhiều sự chú ý trong cả hai lĩnh vực nghiên cứu và ứng dụng. Tuy nhiên kết quả nghiên cứu đạt đƣợc trong lĩnh vực này vẫn chƣa đƣợc ứng dụng rộng rãi bởi các nguyên nhân sau: - Về mặt học thuật, bài toán xếp thời khóa biểu tự động là một bài toán có độ phức tạp giải thuật rất cao. Chƣa có giải thuật xếp thời khóa biểu một cách tổng quát. - Khi áp dụng vào các trƣờng học, mỗi trƣờng có mô hình đào tạo, đặc thù khác nhau dẫn đến các mối quan hệ ràng buộc khác nhau. Việc đƣa ra một mô hình biểu diễn đặc trƣng tổng quát cho tất cả các mối quan hệ ràng buộc này là rất khó. - Bài toán thời khóa biểu là mô hình quan hệ ràng buộc giữa các đối tƣợng liên quan trực tiếp đến thời khóa biểu bao gồm giáo viên ngƣời dạy), học sinh ngƣời học), môn học hay học phần (nội dung dạy và học), phòng học địa điểm) và cuối cùng là dạy, học nội dung gì, học ở đâu, diễn 9 ra ở thời điểm nào. Các đối tƣợng trên quyết định đến mô hình chung của bài toán xếp thời khóa biểu do những đặc thù riêng biệt của chúng. Bài toán đặt ra bao gồm tất cả các vấn đề có liên quan đến việc xếp thời khóa biểu ở một trƣờng học. Chẳng hạn nhƣ đặt số học sinh vào một phòng sao cho tƣơng ứng về sức chứa của nó, tránh việc học trùng giờ tại một phòng của các lớp chuyên ngành, giáo viên sẽ dạy theo giờ quy định trong bảng phân công hay đăng ký giảng dạy. Thông thƣờng, công việc này có thể đƣợc làm bằng tay, nhƣng phải mất nhiều thời gian và phải có kinh nghiệm xếp lịch nếu không muốn xảy ra sai sót, chẳng hạn nhƣ: chỗ này thừa phòng, chỗ khác lại thiếu, sai giờ, sai chỗ… vấn đề của bài toán là ngoài việc thực hiện đúng, chính xác, còn phải tốt hơn, nhanh hơn và hiệu quả hơn công việc xếp lịch bằng tay mà chúng ta vẫn làm. 1.4.2. Độ phức tạp của bài toán xếp thời khóa biểu Khi nhắc đến bài toán xếp thời khóa biểu, hầu hết tất cả những ai quan tâm đến bài toán này đều quan tâm đến độ phức tạp của nó. Bài toán xếp thời khóa biểu trong các nhà trƣờng là bài toán cần phải thỏa mãn những ràng buộc hết sức phức tạp và nhiều khi là mâu thuẫn của các đối tƣợng. "Độ phức tạp " của bài toán đã trở nên nổi tiếng không chỉ bởi độ khó của nó, mà còn ở tính thực tiễn, khả năng áp dụng rất cao vào thực tế. Tại tất cả các trƣờng học, thời khóa biểu học tập của học sinh, giảng dạy của giáo viên là quyết định hoạt động chính của nhà trƣờng, chính vì vậy xếp thời khóa biểu đã trở thành vấn đề chính và quan trọng trong mỗi nhà trƣờng. Việc xếp thời khóa biểu thực sự là một công việc rất khó và mất rất nhiều thời gian. Xếp thời khóa biểu thể hiện cái khó ở các lý do sau: - Thứ nhất: Việc xếp thời khóa biểu đòi hỏi tƣ duy, tính toán, suy luận rất phức tạp, dễ xảy ra nhầm lẫn nhƣ: trùng giờ trùng tiết, thiếu giờ thiếu 10 tiết,... Nhƣ vậy, việc xếp thời khóa biểu đòi hỏi ngƣời phải có nhiều kinh nghiệm và hiểu biết về công việc này mới có thể làm đƣợc. - Thứ hai: Các ràng buộc của giáo viên trong trƣờng rất mâu thuẫn, chồng chéo lẫn nhau. - Thứ ba: Công việc xếp thời khóa biểu đòi hỏi phải có tƣ duy đặc biệt. Ngƣời xếp thời khóa biểu, ngoài việc phải am hiểu về các môn học cũng nhƣ quy định của Bộ Giáo Dục và Đào Tạo đối với nhà trƣờng về chƣơng trình môn học, hiểu rõ yêu cầu cầu của các giáo viên trong nhà trƣờng, phải có tƣ duy nghề nghiệp của công việc xếp thời khóa biểu. Mỗi trƣờng lại có một đặc thù riêng về công tác đào tạo, số lƣợng giáo viên, lớp học, phòng học. Do vậy việp xếp thời khóa biểu của các trƣờng hoàn toàn khác nhau, không thể áp dụng chung cho các trƣờng. Hiện nay cả nƣớc ta có khoảng 25,000 trƣờng học với các cấp bậc đào tạo khác nhau nhƣ: cấp Tiểu học, Trung học cơ sở, Phổ thông trung học. Những điều trên đã khiến cho bài toán xếp thời khóa biểu càng trở nên phức tạp hơn. 1.4.3. Phân loại mô hình xếp thời khóa biểu a. Phân loại theo khuôn dạng thời gian thời khóa biểu Phân loại theo mẫu biểu của thời khóa biểu đƣợc in ra. Trên thực tế có rất nhiều dạng thời khóa biểu khác nhau, rất đa dạng và tuỳ thuộc vào hoàn cảnh, điều kiện của từng trƣờng. Có thể liệt kê ra đây một vài kiểu (mẫu) thời khóa biểu nhƣ sau: + Thời khóa biểu TUẦN: Là mẫu dạng thời khóa biểu cho một tuần và đƣợc dùng làm chuẩn cho tất cả các tuần của học kỳ hoặc năm học. Đa số các nhà trƣờng của Việt Nam đều sử dụng khuôn mẫu này. 11 + Thời khóa biểu HỌC KỲ: Là mẫu khuôn dạng thời khóa biểu đƣợc biểu diễn chi tiết đến từng ngày trong suốt một học kỳ hoặc năm học. Một số các trƣờng đại học, cao đẳng tại Việt Nam, đặc biệt là các trƣờng quân đội sử dụng khuôn dạng này của thời khóa biểu. + Thời khóa biểu cho mỗi TUẦN: Là loại thời khóa biểu mô hình tuần nhƣng mỗi tuần lại có một Thời khóa biểu riêng. Nhƣ vậy ví dụ trong một học kỳ có 25 tuần thì mỗi lớp học sẽ có đúng 25 thời khóa biểu. Đây là mô hình rất phức tạp và về bản chất chính là mô hình Thời khóa biểu Học kỳ (loại B), điểm khác duy nhất là khuôn dạng in ra của thời khóa biểu là TUẦN. b. Phân loại theo đối tượng xếp thời khóa biểu Phân loại theo các đối tƣợng trực tiếp liên quan đến dữ liệu bài toán xếp thời khóa biểu, đó là các đối tƣợng chính bao gồm: giáo viên, học sinh, học phần (môn học), phòng học. + Giáo viên: à ngƣời trực tiếp giảng dạy theo các học phần, môn học đƣợc quy định chặt chẽ về thời lƣợng, kiến thức và hình thức học. + Học sinh: Đối tƣợng học tập trực tiếp của giáo viên giảng dạy. Học sinh tham gia học tập ở các lớp học. + Môn học: Là nội dung các bài giảng của giáo viên và nội dung mà học sinh học tập, mỗi môn học có đặc trƣng riêng để phân biệt với các môn học khác. + Phòng học: à địa điểm tổ chức các môn học, học phần và bài giảng do giáo viên đảm nhiệm. Chính việc phân loại theo khuôn dạng thời gian và phân loại theo đối tƣợng đã tạo ra sự khác biệt cơ bản của mô hình thời khóa biểu. 12 c. Yêu cầu đối với các mô hình xếp thời khóa biểu - Các đối tƣợng chính cần quan tâm là lớp học, giáo viên, phòng học, môn học. - Các mô hình đều có các ràng buộc về giáo viên, phòng học do vậy đều phải kiểm soát đƣợc các trạng thái ràng buộc này trên cơ sở ràng buộc cứng và mềm. - Các môn học của cùng một lớp không đƣợc xếp trùng giờ, trùng tiết. - Phải kiểm soát các môn học để không xảy ra 2 môn học của lớp trùng nhau về thời gian. - Có sự phân chia các môn học theo thứ tự ƣu tiên về ý nghĩa môn học để sắp xếp. - Với mỗi môn học của thời khóa biểu đƣợc gắn cho một hay nhiều lớp 1.4.4. Các đặc thù của thời khóa biểu hệ trung học phổ thông Phân tích các đặc thù của thời khóa biểu trên cơ sở các ràng buộc. Ràng buộc về cơ bản vẫn là các yêu cầu từ phía đối tƣợng đặt ra, bắt buộc bài toán phải thỏa mãn tất cả, nhƣng phần nghiệp vụ cũng mang lại một ràng buộc cần thiết nhằm tránh một số trƣờng hợp sai sót để giúp quá trình thực thi cho ra kết quả đúng. Vậy liệt kê đƣợc đầy đủ các ràng buộc có thể có trong bài toán là công việc quan trọng cần làm. Các thành phần ràng buộc của bài toán có thể kể đến đó là: - Ràng buộc dữ liệu nhập vào. - Ràng buộc môn học, thời gian. a. Ràng buộc dữ liệu nhập vào Các dữ liệu chính của thời khóa biểu bao gồm: - Danh sách môn học. - Danh sách khối học. - Danh sách lớp học.