ĐẠI HỌC QUỐC GIA TP.HCMTRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TINĐỒ ÁN MÔN HỌC THUẬT TOÁN VÀ PHƯƠNG PHÁPGIẢI QUYẾT VẤN ĐỀXÂY DỰNG GIẢI PHÁP LẬP THỜI KHÓA BIỂU TẠI TRƯỜNG ĐẠI HỌCTÀI NGUYÊN VÀ MÔI TRƯỜNG TP.HCMGVHD : PGS. TS. Đỗ Văn NhơnHVTH : Lê Thành NguyênMSHV : CH1301102TP HCM, Tháng 09 năm 2014MỤC LỤC2DANH MỤC BẢNG3DANH MỤC HÌNH4GVHD: PGS. TS. Đỗ Văn Nhơn HVTH: Lê Thành NguyênPHẦN 1: MỞ ĐẦUNước ta đang thực hiện công cuộc công nghiệp hóa hiện đại hóa nhằm thúc đẩynền kinh tế phát triển mạnh mẽ. Trong quá trình này, vai trò nền tảng của giáo dục, đặcbiệt là giáo dục Đại học đã được xã hội ghi nhận và phát huy. Từ đó, nhiệm vụ giáo dụcvà cấu trúc quản lý của hệ thống đào tạo đại học đang đối mặt với một thử thách to lớntrước sự tăng trưởng theo cấp số nhân của số lượng sinh viên và yêu cầu ngày càng caocủa xã hội. Để đáp ứng nhu cầu trên, hệ thống đào tạo theo tín chỉ đã ra đời và được hầu hếtcác trường đại học trong cả nước áp dụng. Song song đó đã phát sinh hàng loạt nhữngthách thức trước yêu cầu thay đổi cơ sở hạ tầng quản lý. Trong đó, việc xếp thời khóabiểu và chương trình xếp thời khóa biểu môn học là một trong những yêu cầu không thểthiếu trong hệ thống đào tạo theo học chế tín chỉ.Trường Đại học Tài nguyên và Môi trường TP. Hồ Chí Minh không phải là ngoạilệ, được nâng cấp từ trường Cao đẳng Tài nguyên và Môi trường TP. Hồ Chí Minh với cơsở hạ tầng quản lý đào tạo áp dụng cho hệ niên chế. Theo xu thế phát triển chung, trườngđã áp dụng hệ thống học chế tín chỉ, tuy nhiên, hệ thống phần mềm quản lý đào tạo chưađược nâng cấp kịp thời gây khó khăn nhất định trong công tác quản lý, đặc biệt là côngtác lập và quản lý thời khóa biểu giảng dạy. Với số lượng sinh viên ngày càng tăng gâysức ép lớn trong phân bổ nguồn tài nguyên và sẽ rất khó khăn nếu xếp lịch thủ công. Như chúng ta đã biết việc xếp thời khóa biểu theo phương pháp thủ công của conngười phải tốn rất nhiều thời gian và công sức,… nhưng hiệu quả đem lại không cao.Chính vì điều đó đã thu hút nhiều nhà khoa học, các chuyên gia đã nghiên cứu ứng dụngkhoa học máy tính vào việc xếp thời khóa biểu cho các trường đại học, cao đẳng, phổthông…và đã đạt được một kết quả thỏa mãn nhất định. Tuy nhiên, mỗi trường có nhữngđặc thù về quy trình công việc, cơ sở vật chất,…cần giải quyết khác nhau.Từ những khó khăn trên, đề tài này đã được thực hiện từ tháng 12/2013 nhằm đưara giải pháp lập thời khóa biểu tự động và phát triển ứng dụng lập thời khóa biểu học kỳđáp ứng nhu cầu đào tạo cũng như tối ưu hóa việc sử dụng tài nguyên hạn hẹp hiện cócủa nhà trường.5B1. Phân công giảng dạy B2. Tổng hợp phân công giảng dạyB3. Lập kế hoạch bố trí buổiB4. Xếp thời khóa biểuB5. Lấy ý kiến GV B6. Điều chỉnh và phát hànhGVHD: PGS. TS. Đỗ Văn Nhơn HVTH: Lê Thành NguyênPHẦN 2: BÀI TOÁNBài toán xếp thời khóa biểu là quá trình xếp lịch cho các lớp môn học dựa trênnguồn tài nguyên hạn hẹp của trường thỏa mãn những ràng buộc đã đưa ra. Tài nguyêncủa trường ở đây có thể hiểu: phòng học, lớp học, giảng viên, ca học…. Tại trường ĐHTài nguyên và Môi trường TP.HCM quy trình xếp thời khóa biểu được thực hiện như sơđồ ở Hình 1, được tiến hành qua các bước sau:B1: Vào cuối mỗi học kỳ, Phòng Đào tạo sẽ thông báo đến các Khoa/Bộ mônchuyên ngành lập bảng phân công giảng dạy học kỳ tiếp theo dựa vào kế hoạch đào tạovà chương trình khung của từng ngành đã được Hiệu trưởng phê duyệt, gửi về Phòng Đàotạo.B2: Phòng Đào tạo tổng hợp bảng phân công giảng dạy nhận được.B3: Dựa vào bảng phân công giảng dạy Phòng Đào tạo sẽ lập kế hoạch bố trí buổihọc cho từng ngành/ chuyên ngành nhằm phân phối đều tài nguyên vào từng buổi.B4: Phòng Đào tạo tiến hành xếp thời khóa biểu dựa trên bảng phân công giảngdạy và kế hoạch bố trí buổi.B5: Phòng Đào tạo gửi thời khóa biểu đã lập về các khoa/ bộ môn lấy ý kiến giảngviên.B6: Điều chỉnh lịch dạy theo yêu cầu giảng viên (nếu có thể) và phát hành thờikhóa biểu chính thức.6Hình 1. Quy trình xếp TKB tại trường ĐH TNMT TP.HCMGVHD: PGS. TS. Đỗ Văn Nhơn HVTH: Lê Thành NguyênTrong chuyên đề này sẽ tập trung giải quyết công việc tại bước 4, trong đó sẽ tìmgiải pháp cho các vấn đề gặp phải trong quá trình xếp thời khóa biểu tự động, tối ưu hóathời khóa biểu. Bài toán xếp thời khóa biểu có thể xem là bài toán tối ưu hóa nhằm thỏamãn các ràng buộc trong quá trình lập lịch. 2.1. Đặc điểm và khó khăn khi giải bài toánTrong việc xếp thời khóa biểu có thể chia thành hai loại ràng buộc: ràng buộccứng và ràng buộc mềm. Ràng buộc cứng là các ràng buộc phải được thỏa mãn. Ràngbuộc mềm, tuy có thể vi phạm, nhưng càng thỏa mãn nhiều ràng buộc mềm càng tốt.Như đã biết việc xếp thời khóa biểu theo phương pháp thủ công của con ngườiphải tốn rất nhiều thời gian và công sức,… nhưng hiệu quả đem lại không cao. Vì vậy,nhiều nghiên cứu khoa học và thực tiễn đã tập trung nghiên cứu ứng dụng khoa học máytính vào việc xếp thời khóa biểu cho các trường đại học, cao đẳng, phổ thông…và đã đạtđược một kết quả nhất định. Nhưng do mỗi trường có những đặc thù về quy trình côngviệc, cơ sở vật chất,…cần giải quyết khác nhau và hầu như không có ngoại lệ.Do đó, để thực hiện được công việc này với kết quả khả thi, chúng ta phải dựa trêntập các ràng buộc cứng và ràng buộc mềm cũng như yêu cầu về quản lý của mỗi trườngđại học. Với tính đa dạng của bài toán lập thời khóa biểu, hiện nay, vẫn chưa có giải phápcụ thể, hiệu quả giải quyết vấn đề này. Thuật giải đơn giản nhất có thể xây dựng dựa trênphép vét cạn với độ phức tính toán rất cao. Do đó, đối với mỗi trường hợp cụ thể, chúngta phải nghiên cứu xây dựng giải pháp tối ưu nhất phù hợp với yêu cầu quản lý của từngđơn vị. Nội dung tiếp theo sẽ đề cập các ràng buộc trong quá trình xếp thời khóa biểu tạitrường Đại học Tài nguyên và Môi trường TP.HCM.Ràng buộc là những yêu cầu hay điều kiện phải xem xét và thỏa mãn trong quátrình xếp thời khóa biểu. Trong nhiều nghiên cứu về lập lịch, các tác giả thường phân cácràng buộc thành hai loại: ràng buộc cứng và ràng buộc mềm.2.1.1. Ràng buộc cứngRàng buộc cứng được định nghĩa là các yêu cầu, điều kiện trong quá trình xếp thờikhóa biểu không được vi phạm. Thời khóa biểu áp dụng tại trường Đại học Tài nguyênvà Môi trường TP.HCM có một số ràng buộc cứng như sau:7GVHD: PGS. TS. Đỗ Văn Nhơn HVTH: Lê Thành NguyênRàng buộc về thời gian:− Thời gian dạy và học trong thời khóa biểu phải đảm bảo thời lượng của mônhọc được quy định trong chương trình đào tạo.− Lịch dạy không được trùng với lịch bận giảng viên đã thông báo trước.− Một giảng viên không được dạy quá n ca/ngày.− Một sinh viên không được học quá m ca/ngày.− Trong cùng một thời điểm không thể xảy ra một trong các trường hợp sau:+ Một phòng được bố trí cho hai môn học khác nhau.+ Một giảng viên được bố trí dạy ở hai phòng khác nhau.+ Một sinh viên được bố trí học ở hai phòng khác nhau.Ràng buộc về không gian:− Phòng học được bố trí phải đảm bảo đủ chỗ ngồi cho sinh viên trong lớp.− Trong một ngày, không được bố trí một giảng viên dạy ở cả hai cơ sở khácnhau (Trường ĐH Tài nguyên và Môi trường có hai cơ sở đào tạo, trụ sở tại địachỉ 236B Lê Văn Sỹ, Phường 1, Quận Tân Bình TP.HCM và cơ sở 2 tại ấpLong Đức 3, xã Tam Phước, TP. Biên Hòa, Đồng Nai).2.1.2. Ràng buộc mềmRàng buộc mềm được hiểu như là các yêu cầu, điều kiện hạn chế vi phạm trongquá trình lập thời khóa biểu. Ràng buộc mềm cho thời khóa biểu tại trường Đại học Tàinguyên và Môi trường TP.HCM có thể được liệt kê như sau:Ràng buộc về thời gian:− Lịch dạy/học của một giảng viên/sinh viên phải liên lục trọn trong một buổi,không có ca trống xen giữa.− Hạn chế bố trí những ca đơn trong nhiều ngày.− Hai ca học của một một môn học dành cho một lớp không nên bố trí trongcùng một ngày.− Lịch học của một sinh viên hạn chế những ngày học cả hai buổi.− Nhằm tối ưu về thời gian rãnh của giảng viên cũng như sinh viên, nên bố trílịch mới sao cho thời gian bận chung thay đổi ít nhất.Ràng buộc về không gian:− Hạn chế di chuyển xa khi giảng viên/sinh viên đổi ca.− Hạn chế những ngày giảng viên dạy xen kẽ ở hai cơ sở.− Phòng học phải được sử dụng với tần suất cao nhất và tối ưu sức chứa.− Hạn chế bố trí phòng ở tầng cao cho giảng viên lớn tuổi.8GVHD: PGS. TS. Đỗ Văn Nhơn HVTH: Lê Thành Nguyên9GVHD: PGS. TS. Đỗ Văn Nhơn HVTH: Lê Thành NguyênPHẦN 3: GIẢI PHÁP LẬP THỜI KHÓA BIỂU3.1. Dữ liệu cho trước− Tập hợp học kỳ:SM = {(id, startWeek, numberWeek, numberDay, numberSession)}.− Tập hợp khu giảng đường:BD = {(id, name)}.− Tập hợp Phòng/Khoa/Bộ môn:DP = {(id, name)}.− Tập hợp phòng học:RM = {(id, name, capacity, floor, building, dept) | building ∈ BD ∧ dept ∈ DP}.− Tập hợp môn học:CR = {(id, name, theory, exercises, practice, level, dept) | dept ∈ DP}.− Tập hợp giảng viên:LT = {(id, name, birthyear, sex, dept) | dept ∈ DP}.− Danh sách lớp quản lý:CL = {(id, name, level, studentNum, year, dept) | dept ∈ DP}.− Tập các ràng buộc CT, trong đó ct có dạng hàm hoặc luật.3.2. Dữ liệu đầu vàoĐầu vào của quá trình xếp thời khóa biểu là bảng phân công giảng dạy trong họckỳ. Sau khi nhập vào hệ thống sẽ được tập AM. AM = {(id, course, class, lecturer, semester) | course ∈ CR ∧ class ∈ CL ∧lecturer ∈ LT ∧ semester ∈ SM}.Từ tập AM, trải qua bước tiền xử lý tạo tập MT là các ca học chưa xếp lịch. Quátrình này được thực hiện thủ công qua giao diện của chương trình. Dựa vào kế hoạchphân chia buổi học cho từng ngành, người dùng sẽ chỉ định phân công nào diễn ra trước,phân công nào diễn ra sau và trong khoảng thời gian bao lâu. Dựa vào khoảng thời gian10GVHD: PGS. TS. Đỗ Văn Nhơn HVTH: Lê Thành Nguyêndiễn ra và thời lượng của từng môn học, chương trình sẽ tạo ra số lượng ca phù hợp hoàntất việc dạy và học và được tập MT.MT = {(id, assignment, startWeek, numberWeek, day, session, room) | assignment∈ AM ∧ room = null ∧ startWeek + numberWeek < assignment.semester.numberWeek }Tập MT là tập đầu vào của quá trình xếp thời khóa biểu và |MT| ≥ |AM|.3.3. Dữ liệu kết quảKhi quá trình xếp lịch hoàn tất ta sẽ nhận được thời khóa biểu đã được bố trí thờigian và phòng học đầy đủ.MT = {(id, assignment, startWeek, numberWeek, day, session, room) | room ∈RM ∧ day < assignment.semester.numberDay ∧ session < assignment.semester.numberSession}Tập MT được gọi là thời khóa biểu hợp lệ khi:− ∀mt ∈ MT, mt đã được bố trí thời gian và phòng học sao cho:+ Có duy nhất một ca được bố trí tại phòng được xếp cho mt trong khoảngthời gian ca mt diễn ra.+ Các giảng viên/lớp liên quan có duy nhất một ca trong khoảng thời gian camt diễn ra.3.4. Giải thuật lập thời khóa biểuĐối với bài toán lập thời khóa biểu, giải pháp thông thường là xem xét tất cả cáctrường hợp có xảy ra của một ca học và thiết lập thời gian, phòng học cho chúng. Quátrình này nhanh hay chậm phụ thuộc số lượng ràng buộc của bài toán. Chính quá trìnhnày dẫn đến độ phức tạp của giải thuật có dạng O(nk * numberDay * numberSession),trong đó, n = |MT| và k =|CT|. Tuy nhiên, giải thuật vét cạn cho kết quả không tốt.Tuy nhiên, nếu quá trình trên được thực hiện theo một định hướng tốt, kết quả đạtđược có nhiều thay đổi đáng kể nâng cao chất lượng lời giải. Do đó, chuyên đề này sẽứng dụng giải thuật heuristic xây dựng giải pháp xếp thời khóa biểu cho trường Đại họcTài nguyên và Môi trường. 3.4.1. Các định hướngƯu tiên xếp lịch cho các ca có thời gian dài trước, thời gian ngắn sau.Ưu tiên xếp lịch cho các ca bắt đầu sớm trước, muộn sau.11GVHD: PGS. TS. Đỗ Văn Nhơn HVTH: Lê Thành NguyênƯu tiên xếp lịch cho các ca có giảng viên/ lớp có thời gian rãnh ít trước, nhiều sau.Ưu tiên xếp lịch cho các ca có số lượng sinh viên lớn trước nhỏ sau.Ưu tiên xếp lịch cho các ca có độ xung đột về giảng viên/lớp cao trước, thấp sau.Chọn ca có xung đột về lớp/giảng viên với ca đã xếp lịch trước đó nếu hai ca nàythuộc một buổi trong ngày.Không chọn ca có giảng viên/lớp đang bận.Không chọn ca có yêu cầu phòng đã được sử dụng hết.Không chọn ca ở cơ sở này của giảng viên có ca được bố trí ở cơ sở khác.Hạn chế chọn ca có giảng viên/lớp có thời gian dạy/học trong ngày vượt thời giancho phép.Ưu tiên chọn phòng có khoảng cách gần phòng của phân ca trước đó.3.4.2. Giải thuậtfunction scheduling(MT)1. Chọn tuần bắt đầu w nhỏ nhất trong tập MT.//Duyệt tất cả các ngày trong tuần có thể xếp lịchfor(day = 0; day < numberDay; day ++){ //Duyệt tất cả các ca trong ngàyfor(session = 0; session < numberSession; session ++){2. M = {mt | mt ∈ MT ∧ tuần bắt đầu của mt = w}.3. Tính độ xung đột giữa các phần tử trong M.4. Tính độ ưu tiên cho các mt ∈ M5. Sắp xếp M độ ưu tiên tăng dần. while(vẫn con ca có độ ưu tiên > 0 or |M| > 0){6. Chọn mt có độ ưu tiên cao nhất.if( độ ưu tiên > 0){7. Chọn phòng rm cho mt8. Thiết lập thời gian cho mt.9. Cập nhật phòng cho mt.10. Xóa mt khỏi tập M và MT11. Xóa các ca có xung đột với mt}}}12.Chọn tuần bắt đầu w tiếp theo trong tập MT.12GVHD: PGS. TS. Đỗ Văn Nhơn HVTH: Lê Thành Nguyên Trở về bước 2.//Tính độ xung đột giảng viên, lớpfunction computeConflict(MT){for(i= 0, i < |MT|, i++){for(j =0; j < |MT|, j++){if(I <> j){if(M[i].lecturer = M[j].lecturer){conflictLecturer[i][j] = true;conflictLecturer[j][i] = true;}if(M[i].clazz == M[j].clazz){conflictClazz[i][j] = true;conflictClazz[j][i] = true;}}} }}//Tính độ ưu tiên cho mtfunction computeScore(mt, day, session){//Duyệt tập ràng buộc cứngfor(hct in HCT){score *= hct(mt, day, sesion) * whct;}//Duyệt tập ràng buộc mềmfor(sct in SCT){score += sct(mt, day, session) * wsct;}}//Chọn phòng cho mtfunction selectRoom(mt){1. RM’ = {các phòng khả dụng}.2. Tính độ ưu tiên cho từng phòng trong RM’.3. Sắp xếp RM’ theo độ ưu tiên tăng dần.4. Chọn phòng rm có độ ưu tiên cao nhất.}13GVHD: PGS. TS. Đỗ Văn Nhơn HVTH: Lê Thành Nguyên3.4.3. Độ phức tạp giải thuật− Dòng 1, mỗi học kỳ được chia không quá 3 đợt học, do đó, độ phức tạp tính toán ởbước này là 3lg3 + 1 = lg33 + lg2 = lg54.− Dòng 2, là phép duyệt và kiểm tra phần tử tập hợp có độ phức tạp tính toán: |MT|.− Dòng 3, có độ phực tạp tính toán: |M|2.− Dòng 4, có độ phức tạp tính toán: thực hiện |CT| phép kiểm tra luật trên tập ràngbuộc cho mỗi ca: |M| * |CT|.− Dòng 5, có độ phức tạp tính toán |M|lg|M|.− Dòng 6: chọn một phần tử trong tập hợp, có độ phức tạp 1.− Dòng 7, có độ phức tạp tính toán: 2|RM|.− Dòng 8, 9, 10, 11, có độ phức tạp tính toán: thực hiện 2 phép gán giá trị, 1 phéptìm kiếm mt trên M, 1 phép xóa và 10 phép tìm ca xung đột với mt và 10 phépxóa: 13 + 11lg|M| (10 là số ca tối đa xung đột với mt).Giải thuật thực hiện 1 lần dòng 1, numberDay * numberSession lần các dòng 2, 3,4, 5 và |MT| lần các dòng 6, 7, 8, 9, 10, 11. Trong đó, numberDay = 5 vànumberSession = 6.Suy ra: T = lg54 + 30 * (|MT| + |M|2 + |M||CT| + |M|lg|M|) + |MT| (2|RM| + 14 + 11lg|M|) = lg54 + 44|MT| + 30|M|2 + 30|M|(|CT| +lg|M|) + 2|MT||RM| + 11|MT|lg|M| < |MT|2 + 44|MT|2 + 30|MT|2 + 30|MT|2 + 2|MT|2 + 11|MT|2 < 118|MT|2Kết luận, độ phức tạp thời gian của thuật toán xếp thời khóa biểu áp dụng heuristiccó độ phức tạp O(n2) với n là kích thước tập ca học cần xếp lịch.14GVHD: PGS. TS. Đỗ Văn Nhơn HVTH: Lê Thành NguyênPHẦN 4: THỰC NGHIỆM4.1. Dữ liệu thực nghiệmDữ liệu đầu vào cho phần mềm xếp thời khóa biểu là các bảng được lưu trữ trêntập tin định dạng Microsoft Excel, gồm các bảng phòng ban/Khoa/Bộ môn, giảng đường,phòng học, môn học, giảng viên, lớp và phân công giảng dạy. Dữ liệu này được importvào hệ thống và được lưu trữ trong cơ sở dữ liệu. Cấu trúc các bảng trong cơ sở dữ liệu được mô tả chi tiết bên dưới.Lưu trữ thông tin học kỳ đã lập thời khóa biểuTên trường Mô tả Kiểu dữ liệu Tự phát sinhID Khóa chính Số nguyên dương YesYear Năm bắt đầu học kỳ Số nguyên dương NoStartWeek Tuần bắt đầu học kỳ Số nguyên dương NoNumberWeek Số tuần học trong học kỳ Số nguyên dương NoNumberDay Số ngày học/tuần Số nguyên dương NoNumberSessionSố ca học/ngày Số nguyên dương NoBảng 1. Cấu trúc bảng semesterLưu trữ thông tin phòng ban/Khoa/ Bộ mônTên trường Mô tả Kiểu dữ liệu Tự phát sinhID Trường khóa chính Số nguyên dương NoName Tên phòng ban/ Khoa/ Bộ môn Chuỗi NoBảng 2. Cấu trúc bảng dữ liệu departmentLưu trữ thông tin giảng đườngTên trường Mô tả Kiểu dữ liệu Tự phát sinhID Trường khóa chính Số nguyên dương YesName Tên giảng đường Chuỗi NoBảng 3. Cấu trúc bảng dữ liệu buildingLưu trữ thông tin phòng học15GVHD: PGS. TS. Đỗ Văn Nhơn HVTH: Lê Thành NguyênTên trường Mô tả Kiểu dữ liệu Tự phát sinhID Trường khóa chính Số nguyên dương YesName Tên phòng học Chuỗi NoCapacity Sức chứa Số nguyên dương NoType Loại phòng học LT/TH Boolean NoBuilding Mã giảng đường Số nguyên dương NoFloor Tầng cao Số nguyên dương NoDeptID Mã khoa quản lý phòng Số nguyên dương NoBảng 4. Cấu trúc bảng dữ liệu roomLưu trữ thông tin môn họcTên trường Mô tả Kiểu dữ liệu Tự phát sinhID Khóa chính Chuỗi NoName Tên môn học Chuỗi NoLT Số tín chỉ lý thuyết Số nguyên dương NoBT Số tín chỉ bài tập Số nguyên dương NoTH Số tín chỉ thực hành Số nguyên dương NoLevel Hệ đào tạo Số nguyên dương NoDeptID Mã khoa quản lý môn học Số nguyên dương NoBảng 5. Cấu trúc bảng dữ liệu courseLưu trữ thông tin giảng viênTên trường Mô tả Kiểu dữ liệu Tự phát sinhID Khóa chính Chuỗi NoName Họ tên giảng viên Chuỗi NoBirthYear Năm sinh Số nguyên dương NoSex Giới tính Boolean NoDeptID Mã khoa quản lý giảng viên Số nguyên dương NoBảng 6. Cấu trúc bảng dữ liệu lecturerLưu trữ thông tin lớp quản lýTên trường Mô tả Kiểu dữ liệu Tự phát sinhID Khóa chính Số nguyên dương YesName Tên lớp Chuỗi NoStudentNu Sỉ số Số nguyên dương No16GVHD: PGS. TS. Đỗ Văn Nhơn HVTH: Lê Thành NguyênmYear Năm nhập học Số nguyên dương NoLevel Hệ đào tạo Số nguyên dương NoDeptID Khoa quản lý lớp Số nguyên dương NoBảng 7. Cấu trúc bảng dữ liệu clazzLưu trữ thông tin bảng phân công giảng dạyTên trường Mô tả Kiểu dữ liệu Tự phát sinhID Khóa chính Số nguyên dương YesCourseId Mã môn học được phân công Số nguyên dương NoClazzId Mã lớp được phân công Số nguyên dương NoStudentNumSố sinh viên đăng ký Số nguyên dương NoLecturerID Mã GV được phân công Chuỗi NoSemesterID Mã học kỳ Số nguyên dương NoBảng 8. Cấu trúc bảng assignmentLưu trữ thông tin bảng ca họcTên trường Mô tả Kiểu dữ liệu Tự phát sinhID Khóa chính Số nguyên dương YesAssignmentIDMã phân công giảng dạy Số nguyên dương NoStartWeek Tuần bắt đầu học Số nguyên dương NoDay Thứ trong tuần Số nguyên dương NoSession Ca trong ngày Chuỗi NoRoomID Mã phòng học Số nguyên dương NoBảng 9. Cấu trúng bảng meetingDo chương trình được sử dụng trong xếp và quản lý lịch giảng dạy của toàntrường. Dữ liệu này được lưu trữ phục vụ công tác tra cứu khối lượng giảng dạy củagiảng viên và các yêu cầu quản lý khác. Do đó, dữ liệu liên tục tăng trong thời gian thựcsẽ ảnh hưởng tốc độ thực thi của toàn hệ thống và khó khăn trong bảo trì và cập nhật dữliệu.17GVHD: PGS. TS. Đỗ Văn Nhơn HVTH: Lê Thành NguyênNhằm cải thiện hiệu suất của chương trình, cơ sở dữ liệu được chia thành 2 phần:phần dữ liệu dùng chung cho các năm học (dữ liệu có trước) sẽ được lưu trữ trongschema public gồm các bảng dữ liệu chứa thông tin của dữ liệu có trước được mô tảtrong phần 3, phần dữ liệu phân công giảng dạy và thời khóa biểu sẽ được lưu trong cácschema khác nhau – mỗi schema chứa dữ liệu xếp thời khóa biểu của một năm học.4.2. Giao diện chương trìnhChương trình lập thời khóa biểu tại trường Đại học Tài nguyên và Môi trường TP.HCM đã phát triển dựa trên ngôn ngữ lập trình Java, cơ sở dữ liệu được quản lý bởi hệquản trị cơ sở dữ liệu mã nguồn mở PostgreSQL. Chương trình đã cung cấp khá đầy đủcác chức năng quản lý dữ liệu và thời khóa biểu bao gồm các chức năng nhập liệu, xuấtdữ liệu, lọc và sắp xếp dữ liệu theo yêu cầu tác nghiệp của người dùng. Ngoài ra, thờikhóa biểu có thể được xuất theo nhiều mẫu gồm: thời khóa biểu toàn bộ, thời khóa biểutheo khoa/Bộ môn, thời khóa biểu theo lớp hay thời khóa biểu cá nhân dành cho giảngviên,…Hình 2. Giao diện quản lý giảng đường18GVHD: PGS. TS. Đỗ Văn Nhơn HVTH: Lê Thành NguyênHình 3. Giao diện quản lý lớp Hình 4. Giao diện quản lý giảng viên19GVHD: PGS. TS. Đỗ Văn Nhơn HVTH: Lê Thành NguyênHình 5. Giao diện quản lý môn họcHình 6. Giao diện quản lý lịch bận giảng viên20GVHD: PGS. TS. Đỗ Văn Nhơn HVTH: Lê Thành NguyênHình 7. Giao diện quản lý danh sách phân công giảng dạyHình 8. Giao diện quản lý thời khóa biểu21GVHD: PGS. TS. Đỗ Văn Nhơn HVTH: Lê Thành Nguyên4.3. Đánh giáGiải pháp xếp thời khóa biểu học kỳ tại trường Đại học Tài nguyên và Môi trườngTP. HCM đã được sử dụng trong xếp lịch dạy và học từ học kỳ II năm học 2013 – 2014ghi nhận được kết quả như sau:4.3.1. Thời gian thực thiGiải pháp này được phát triển từ giải thuật heuristic và không xây dựng giải phápđối chứng do đó không thể kết luận giải pháp này hiệu quả hơn giải pháp khác về mặtthời gian.Tuy nhiên, thời gian thực thi trung bình trong khoảng 01 giờ với một kết quả khảquan so với quá trình lập lịch thủ công là một ghi nhận đáng quan tâm.4.3.2. Tính hiệu quảThời khóa biểu nhận được hoàn toàn thỏa mãn yêu cầu tại trường Đại học Tàinguyên và Môi trường, với các ưu điểm:− Đã tăng hiệu suất sử dụng phòng học (từ <50% khi xếp lịch bằng tay lên >90% khixếp lịch tự động).− Đáp ứng được đa số yêu cầu của giảng viên, tối ưu hóa thời gian lên lớp của giảngviên cũng như của sinh viên (thỏa mãn đa số ràng buộc mềm cho sinh viên và mộtphần cho giảng viên).Ngoài ra, hệ thống có thể đáp ứng các yêu cầu quản lý khác: cung cấp lịch bậnphòng học, lớp quản lý, kê khai khối lượng giảng dạy,… đã giảm được khối lượng lớncông việc thủ công.4.3.3. Hạn chếDữ liệu phục vụ quá trình xếp thời khóa biểu tương đối lớn, không thể nạp toàn bộvào bộ nhớ máy tính. Do đó, hầu hết các kiểm tra luật trong thời gian thực thi phải truyxuất vào cơ sở dữ liệu là nguyên nhân chính ảnh hưởng đến tốc độ chương trình.Trong quá trình xếp thời khóa biểu, người dùng phải tính toán thủ công để lập kếhoạch phân buổi học cho từng ngành.Thời khóa biểu lập được vẫn còn một lượng nhỏ ca học không thể xếp lịch, phầnnày phải được điều thủ công.22GVHD: PGS. TS. Đỗ Văn Nhơn HVTH: Lê Thành NguyênTÀI LIỆU THAM KHẢO[1] Bài giảng Thuật toán và phương pháp giải quyết vấn đề – PGS. TS Đỗ VănNhơn - Đại học Quốc Gia Thành Phố Hồ Chí Minh.[2] Nguyễn Chí Trung, Nguyễn Thị Thu Thủy(2010), “Phân tích thiết kế thuậttoán và đánh giá độ phức tạp giải thuật”, Đại học sư phạm Hà Nội.23GVHD: PGS. TS. Đỗ Văn Nhơn HVTH: Lê Thành NguyênPHỤ LỤCPhụ lục 1. Danh sách phòng ban/ Khoa/ BMMÃ KHOA/BM TÊN KHOA/BM MÃ KHOA/BM TÊN KHOA/BM2 Phòng Tổ chức Cán bộ 3 Phòng Đào tạo4 Phòng Khảo thí & ĐBCL 5 Phòng Thanh tra6 Phòng Quản lý NCKH 7 Phòng Kế hoạch tài chính8 Phòng Công tác học sinh sinh viên 9 Phòng Quản trị vật tư11 Khoa Khoa học Đại cương 12 Khoa Lý luận chính trị13 Khoa Khí tượng thủy văn – Tài nguyên nước 14 Khoa Môi trường15 Khoa Quản lý đất đai 16 Khoa Trắc địa – Bản đồ17 Khoa Công nghệ thông tin 18 Khoa Kinh tế tài nguyên thiên nhiên19 Khoa Địa chất 20 Bộ môn GDTC - QPANPhụ lục 2. Danh sách giảng viên xếp thời khóa biểuMÃ GV HỌ TÊN NĂM SINH GIỚI KHOA/BM14.11 Nguyễn Vĩnh An 1980 Nam 1419.10 Nguyễn Quốc Khương Anh 1980 Nữ 1915.17 Nguyễn Đức Anh 1980 Nam 1513.07 Vũ Thị Vân Anh 1980 Nữ 1314.17 Bùi Khánh Vân Anh 1980 Nữ 1414.04 Trần Quốc Bảo 1980 Nam 1417.07 Nguyễn Văn Bạo 1980 Nam 1716.10 Nguyễn Danh Cần 1980 Nam 1617.13 Khưu Minh Cảnh 1980 Nam 1707.01 Nguyễn Duy Châu 1980 Nam 711.38 Lại Hoài Châu(TG) 1980 Nữ 1115.18 Lê Minh Chiến 1980 Nam 1501.02 Huỳnh Chức 1980 Nam 114.14 Nguyễn Kim Chung 1980 Nữ 1411.14 Hồ Văn Công 1980 Nam 1115.06 Nguyễn Văn Cương 1980 Nam 1514.15 Nguyễn Huy Cương 1980 Nam 1401.04 Vũ Xuân Cường 1980 Nam 115.02 Nguyễn Hữu Cường 1980 Nam 1519.07 Trần Đức Dậu 1980 Nam 1912.09 Võ Đình Quyên Di 1980 Nữ 1214.27 Lê Thị Ngọc Diễm 1980 Nữ 1411.11 Hà Anh Đông 1980 Nam 1120.03 Đặng Duy Đồng 1980 Nam 2012.11 Nguyễn Bá Đồng 1980 Nam 1219.15 Đỗ Công Dự 1980 Nam 1914.20 Nguyễn Đình Đức 1980 Nam 1416.02 Nguyễn Hữu Đức 1980 Nam 1611.22 Nguyễn Thành Đức 1980 Nam 1111.33 Nguyễn Thị Như Dung 1980 Nữ 1111.31 Nguyễn Lương Tuấn Dũng 1980 Nam 1124GVHD: PGS. TS. Đỗ Văn Nhơn HVTH: Lê Thành NguyênMÃ GV HỌ TÊN NĂM SINH GIỚI KHOA/BM05.01 Nguyễn Tiến Dũng 1980 Nam 517.16 Võ Văn Tuấn Dũng 1980 Nam 1716.14 Đào Mạnh Dũng 1980 Nam 1611.40 Hồ Chí Dũng(TG) 1980 Nam 1111.44 Phạm Tiến Dũng(TG) 1980 Nam 1116.12 Đặng Văn Em 1980 Nam 1614.41 Phạm Thị Thanh Hà 1980 Nữ 1414.30 Đinh Thị Thu Hà 1980 Nữ 1414.42 Hoàng Ngọc Hà 1980 Nam 1414.02 Nguyễn Thị Vân Hà 1980 Nữ 1416.19 Trịnh Ngọc Hà 1980 Nam 1618.08 Đặng Bắc Hải 1980 Nam 1811.46 Nguyễn Minh Hải(TG) 1980 Nam 1114.19 Huỳnh Thị Ngọc Hân 1980 Nữ 1414.05 Huỳnh Thị Ngọc Hân 1980 Nữ 1411.23 Nguyễn Thị Thúy Hằng 1980 Nữ 1111.13 Nguyễn Thanh Hằng 1980 Nữ 1111.25 Nguyễn Thị Hằng 1980 Nữ 1115.05 Huỳnh Thị Thanh Hạnh 1980 Nữ 1519.14 Hoàng Thị Hồng Hạnh 1980 Nữ 1915.03 Trần Mỹ Hảo 1980 Nam 1520.07 Nguyễn Tiến Hảo 1980 Nam 2014.09 Lê Đăng Hảo 1980 Nam 1414.39 Nguyễn Thị Thu Hiền 1980 Nữ 1411.27 Nguyễn Sỹ Hiệp 1980 Nam 1115.08 Ngô Thị Hiệp 1980 Nữ 1512.07 Võ Thị Hồng Hiếu 1980 Nữ 1211.03 Phan Thị Hoa 1980 Nữ 1112.02 Nguyễn Thị Hồng Hoa 1980 Nữ 1219.09 Nguyễn Thị Thanh Hoa 1980 Nữ 1918.07 Sử Thị Oanh Hoa 1980 Nữ 1815.16 Hoàng Thị Thu Hoài 1980 Nữ 1511.19 Trần Bá Lê Hoàng 1980 Nam 1119.12 Nguyễn Kim Hoàng 1980 Nam 1917.04 Huỳnh Thái Học 1980 Nam 1714.10 Nguyễn Thị Hồng 1980 Nữ 1419.05 Vũ Thị Thúy Hồng 1980 Nữ 1916.09 Trần Văn Huân 1980 Nam 1614.07 Dương Hồng Huệ 1980 Nữ 1411.01 Lý Cẩm Hùng 1980 Nam 1115.01 Trần Thanh Hùng 1972 Nam 1519.17 Trần Phú Hưng 1980 Nam 1911.20 Nguyễn Quang Hưng 1980 Nam 1111.02 Nguyễn Thị Mai Hương 1980 Nữ 1115.09 Nguyễn Thu Hương 1980 Nữ 1511.28 Nguyễn Thị Thu Hương 1980 Nữ 1112.01 Nguyễn Tiến Hữu 1980 Nam 1216.13 Đỗ Công Hữu 1980 Nam 1618.02 Nguyễn Bá Huy 1980 Nam 1817.08 Nguyễn Quang Huy 1980 Nam 1711.39 Phan Đông Huyền(TG) 1980 Nữ 1125 |
