大學課程表問題中的算法研究與應用

大學課程表問題中的算法研究與應用

摘要
    課程表問題(UTP)是一個應用廣泛的、典型的組合優化和不確定性調度問題，并且已經被證明是NP完全問題。隨著高校規模的不斷擴大，和教學管理信息化的不斷深入，傳統的手工排課和計算機輔助排課已經越來越難以適應現實的需求，而自動化排課系統，因其固有的高難度和復雜性，它的研究與實現成為完善中南大學網絡教學管理系統十分重要的一環。本文從實際應用出發，基于動態規劃的思想，提出了一種解決大學課程表問題的混合算法，并基于此算法設計并實現了自動化排課系統。
    本文首先介紹了UTP問題的研究現狀、涉及的因素、各種約束條件，及其數學模型，然后詳細闡述了將課程表問題劃分為時間片安排和場地安排兩個階段，分別采用智能算法和最佳適應算法逐段求解，并最終求得全局較優解的混合算法。然后，對混合算法與經典遺傳算法進行了對比實驗分析，結果表明這種分階段決策的算法在保證課表質量的同時，能夠有效的減小遺傳算法在求解UTP問題中的復雜度，提高程序的運行速度，也有利于工程應用中對多目標優化的進一步擴
展。
    隨后，本文基于混合算法，根據項目的實際需求，并考慮到和網絡教學管理系統中其它子系統的集成，設計了排課系統的數據庫表和各個功能模塊，結合圖表和文字說明，給出了詳細的系統實現過程，并對系統實現過程中的關鍵技術進行了說明。
    最后，總結了本文所做的工作，分析了當前工作的不足及需進一步研究的工作。

ABSTRACT
    University Timetable Problem (UTP) is a tyhttps://p.9136.com/28bination 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 future.KEY WORDS  university timetable problem, dynamic programming,genetic algorithm, arranging of curriculum schedule。

目錄
摘要..................................................................................................... I
ABSTRACT.......................................................................................................II
目錄....................................................................................................... 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全文總結和工作回顧
    高校招生規模逐年的擴大及計算機在教學工作中的普及應用，用自動化的智能排課系統代替勞動強度大、工作效率低的手工排課，或是人工介入很大的計算機輔助排課，越來越成為教學管理之中迫切需要解決的研究課題之一。
    本文從大學課程表問題的研究與應用出發，設計了基于動態規劃思想的混合算法，并基于此算法，結合整個教學管理系統的實際需求，實現了適應中南大學需求的排課系統。具體說來，本人的工作可以歸納如下:

【大學課程表問題中的算法研究與應用】相關文章：

向量在解題中的應用03-07

粗決策樹動態規則提取算法研究及應用03-17

變換在幾何問題中的應用03-07

計數查找算法的研究11-22

關于LZW算法的改進研究03-25

LDPC碼譯碼算法研究03-07

紅外圖像增強算法研究03-07

指紋識別算法研究03-08

FFT算法的研究與DSP實現03-07