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

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

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國內(nèi)外研究動態(tài)............................:.......................................................... 1
    1.3課題的研究內(nèi)容及意義............................................................................ 2
    1.4論文的內(nèi)容安排和組織結構............................................................... 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
第三章基于動態(tài)規(guī)劃思想的混合算法.............................................................. 11
    3.1最優(yōu)化原理和動態(tài)規(guī)劃......................:.......................................................11
      3.1.1多階段決策最優(yōu)化問題......................................................... .11
      3.1.2最優(yōu)化原理...............................................................................11
      3.1.3動態(tài)規(guī)劃理論··……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
第四章基于混合算法的排課系統(tǒng).................................................... 27
    4.1系統(tǒng)需求分析..................................................27
    4.2系統(tǒng)總體設計.................................................................28
      4.2.1與其它子系統(tǒng)的集成..............................................28
      4.2.2系統(tǒng)架構設計.....................28
      4.2.3系統(tǒng)網(wǎng)絡體系結構.........................30
      4.2.4系統(tǒng)功能模塊劃分...................................31
    4.3數(shù)據(jù)庫設計.....................................33
      4.3.1數(shù)據(jù)庫設計方案.......................................33
        4.3.2表的設計..........................................34
    4.4系統(tǒng)實現(xiàn)..................................................37
      4,4.1表示層的實現(xiàn)............................................37
      4.4.2服務層的實現(xiàn).......................................................38
      4.4.3業(yè)務邏輯層的實現(xiàn)..............................41
      4.4.4數(shù)據(jù)訪問層的實現(xiàn).............................. 43
    4.5關鍵技術研究.........................................44
      4.5.1系統(tǒng)性能優(yōu)化...............................................44
      4.5.2數(shù)據(jù)庫安全機制...............................................47
第五章回顧與展望.................................... 49
    5.1全文總結和工作回顧........................................................49
    5.2后續(xù)工作與展望...............................................49
參考文獻..................................51
致謝..........................................55
攻讀學位期間主要的研究成果..................................... 56

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

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

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

粗決策樹動態(tài)規(guī)則提取算法研究及應用03-17

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

計數(shù)查找算法的研究11-22

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

LDPC碼譯碼算法研究03-07

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

指紋識別算法研究03-08

FFT算法的研究與DSP實現(xiàn)03-07