摘要
課程表問題(UTP)是一個應用廣泛的、典型的組合優化和不確定性排程問題，並且已經被證明是NP完全問題。隨著高校規模的不斷擴大，和教學管理資訊化的不斷深入，傳統的手工排課和計算機輔助排課已經越來越難以適應現實的需求，而自動化排課系統，因其固有的高難度和複雜性，它的研究與實現成為完善中南大學網路教學管理系統十分重要的一環。本文從實際應用出發，基於動態規劃的思想，提出了一種解決大學課程表問題的混合演算法，並基於此演算法設計並實現了自動化排課系統。
本文首先介紹了UTP問題的研究現狀、涉及的因素、各種約束條件，及其數學模型，然後詳細闡述了將課程表問題劃分為時間片安排和場地安排兩個階段，分別採用智慧演算法和最佳適應演算法逐段求解，並最終求得全域性較優解的混合演算法。然後，對混合演算法與經典遺傳演算法進行了對比實驗分析，結果表明這種分階段決策的演算法在保證課表質量的同時，能夠有效的減小遺傳演算法在求解UTP問題中的複雜度，提高程式的執行速度，也有利於工程應用中對多目標優化的進一步擴
展。
隨後，本文基於混合演算法，根據專案的實際需求，並考慮到和網路教學管理系統中其它子系統的整合，設計了排課系統的資料庫表和各個功能模組，結合圖表和文字說明，給出了詳細的系統實現過程，並對系統實現過程中的關鍵技術進行了說明。
最後，總結了本文所做的工作，分析了當前工作的不足及需進一步研究的工作。
ABSTRACT
University Timetable Problem (UTP) is a ty optimization problem and uncertain management problem, which is applied widely. UTP has been proved a NP-completion problem. With the enlargement of the university and the deepening of the teaching management information, the tranditional way, arranging course by hand,and the way by using computer assistant could hardly meet the current requirement. The antomatic course arranging system, for its inherent high difficulty and complicacy, its research and realization are very important for the whole network teaching management system. In this paper, with the thought of dynamic programming, a mixed algorithm is proposed to solve this problem. And an automatic course arranging system is designed and realized by using this algorithm in the following.
This paper introduces the development, main factors, constraints and mathematic model of university timetable problem first. Then it expounds a mixed algorithm which divides the course timetabling problem into two
phases, arranging time by intelligent algorithm and arranging classroom by best fit algorithm, and gets the whole solution by resolving each phase of the problem. In the following, compared the mixed algorithm with classical genetic algorithm, it shows the mixed algorithm at the same time of ensuring the quality of result, reduces the complicacy, have a better performance and expansibility.
After that, the database table and sub modules are designed based on the mixed algorithm and requirement, the intergration with other sub system of teaching management system is also considered. The detailed realization and the key technique are then explained by using the combination of text and diagram.
Finally, it summarizes the research work, also analyzes the present problems and the work in WORDS university timetable problem, dynamic programming,genetic algorithm, arranging of curriculum schedule。
目錄
摘要..................................................................................................... I
目錄....................................................................................................... III
第一章緒論................................................................................................. 1
I.1課題來源及應用背景........................................................1
1.2國內外研究動態............................:.......................................................... 1
1.3課題的研究內容及意義............................................................................ 2
1.4論文的內容安排和組織結構............................................................... 3
第二章課程表問題...............................................5
2.1時間表問題概述.............................................................................. 5
2.1.1時間表問題及其分類................................................................. 5
2.1.2 School Timetabling問題............................................................5
2.1.3 Course Timetabling問題............................................................7
2.2課程表問題的因素及約束條件........................................................ g
2.3課程表的編排原則............................................................8
第三章基於動態規劃思想的混合演算法.............................................................. 11
3.1最優化原理和動態規劃......................:.......................................................11
3.1.1多階段決策最優化問題......................................................... .11
3.1.2最優化原理...............................................................................11
3.1.3動態規劃理論··……12
3.2混合演算法設計……13
3.2.1演算法的總體設計思想.................................13
3.2.2演算法描述....................................................14
3.3基於遺傳演算法分配時間..............................................................................15
3.3.1遺傳演算法概述....................................................15
3.3.2基因編碼設計....................................................17
3.3.3初始化種群....................................................18
3.3.4遺傳運算元操作設計....................................................19
3.3.5衝突檢測與消除....................................................22
3.4基於最佳適應演算法分配場地................................................................22
3.5對比實驗分析.................................................................................... 24
3.5.1演算法比較..........................................................24
3.5.2實驗設計....................................................25
3.5.3實驗結果及分析................................................................25
第四章基於混合演算法的排課系統.................................................... 27
4.1系統需求分析..................................................27
4.2系統總體設計.................................................................28
4.2.1與其它子系統的整合..............................................28
4.2.2系統架構設計.....................28
4.2.3系統網路體系結構.........................30
4.2.4系統功能模組劃分...................................31
4.3資料庫設計.....................................33
4.3.1資料庫設計方案.......................................33
4.3.2表的'設計..........................................34
4.4系統實現..................................................37
4,4.1表示層的實現............................................37
4.4.2服務層的實現.......................................................38
4.4.3業務邏輯層的實現..............................41
4.4.4資料訪問層的實現.............................. 43
4.5關鍵技術研究.........................................44
4.5.1系統性能優化...............................................44
4.5.2資料庫安全機制...............................................47
第五章回顧與展望.................................... 49
5.1全文總結和工作回顧........................................................49
5.2後續工作與展望...............................................49
參考文獻..................................51
致謝..........................................55
攻讀學位期間主要的研究成果..................................... 56
5.1全文總結和工作回顧
高校招生規模逐年的擴大及計算機在教學工作中的普及應用，用自動化的智慧排課系統代替勞動強度大、工作效率低的手工排課，或是人工介入很大的計算機輔助排課，越來越成為教學管理之中迫切需要解決的研究課題之一。
本文從大學課程表問題的研究與應用出發，設計了基於動態規劃思想的混合演算法，並基於此演算法，結合整個教學管理系統的實際需求，實現了適應中南大學需求的排課系統。具體說來，本人的工作可以歸納如下: