大學(xué)課程表問(wèn)題中的算法研究與應用

摘要
    課程表問(wèn)題(UTP)是一個(gè)應用廣泛的、典型的組合優(yōu)化和不確定性調度問(wèn)題，并且已經(jīng)被證明是NP完全問(wèn)題。隨著(zhù)高校規模的不斷擴大，和教學(xué)管理信息化的不斷深入，傳統的手工排課和計算機輔助排課已經(jīng)越來(lái)越難以適應現實(shí)的需求，而自動(dòng)化排課系統，因其固有的高難度和復雜性，它的研究與實(shí)現成為完善中南大學(xué)網(wǎng)絡(luò )教學(xué)管理系統十分重要的一環(huán)。本文從實(shí)際應用出發(fā)，基于動(dòng)態(tài)規劃的思想，提出了一種解決大學(xué)課程表問(wèn)題的混合算法，并基于此算法設計并實(shí)現了自動(dòng)化排課系統。
    本文首先介紹了UTP問(wèn)題的研究現狀、涉及的因素、各種約束條件，及其數學(xué)模型，然后詳細闡述了將課程表問(wèn)題劃分為時(shí)間片安排和場(chǎng)地安排兩個(gè)階段，分別采用智能算法和最佳適應算法逐段求解，并最終求得全局較優(yōu)解的混合算法。然后，對混合算法與經(jīng)典遺傳算法進(jìn)行了對比實(shí)驗分析，結果表明這種分階段決策的算法在保證課表質(zhì)量的同時(shí)，能夠有效的減小遺傳算法在求解UTP問(wèn)題中的復雜度，提高程序的運行速度，也有利于工程應用中對多目標優(yōu)化的進(jìn)一步擴
展。
    隨后，本文基于混合算法，根據項目的實(shí)際需求，并考慮到和網(wǎng)絡(luò )教學(xué)管理系統中其它子系統的集成，設計了排課系統的數據庫表和各個(gè)功能模塊，結合圖表和文字說(shuō)明，給出了詳細的系統實(shí)現過(guò)程，并對系統實(shí)現過(guò)程中的關(guān)鍵技術(shù)進(jìn)行了說(shuō)明。
    最后，總結了本文所做的工作，分析了當前工作的不足及需進(jì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課題來(lái)源及應用背景........................................................1
    1.2國內外研究動(dòng)態(tài)............................:.......................................................... 1
    1.3課題的研究?jì)热菁耙饬x............................................................................ 2
    1.4論文的內容安排和組織結構............................................................... 3
第二章課程表問(wèn)題...............................................5
    2.1時(shí)間表問(wèn)題概述.............................................................................. 5
      2.1.1時(shí)間表問(wèn)題及其分類(lèi)................................................................. 5
      2.1.2 School Timetabling問(wèn)題............................................................5
      2.1.3 Course Timetabling問(wèn)題............................................................7
    2.2課程表問(wèn)題的因素及約束條件........................................................ g
    2.3課程表的編排原則............................................................8
第三章基于動(dòng)態(tài)規劃思想的混合算法.............................................................. 11
    3.1最優(yōu)化原理和動(dòng)態(tài)規劃......................:.......................................................11
      3.1.1多階段決策最優(yōu)化問(wèn)題......................................................... .11
      3.1.2最優(yōu)化原理...............................................................................11
      3.1.3動(dòng)態(tài)規劃理論··……12
    3.2混合算法設計……13
      3.2.1算法的總體設計思想.................................13
        3.2.2算法描述....................................................14
    3.3基于遺傳算法分配時(shí)間..............................................................................15
      3.3.1遺傳算法概述....................................................15
      3.3.2基因編碼設計....................................................17
        3.3.3初始化種群....................................................18
      3.3.4遺傳算子操作設計....................................................19
      3.3.5沖突檢測與消除....................................................22
    3.4基于最佳適應算法分配場(chǎng)地................................................................22
    3.5對比實(shí)驗分析.................................................................................... 24
        3.5.1算法比較..........................................................24
        3.5.2實(shí)驗設計....................................................25
        3.5.3實(shí)驗結果及分析................................................................25
第四章基于混合算法的排課系統.................................................... 27
    4.1系統需求分析..................................................27
    4.2系統總體設計.................................................................28
      4.2.1與其它子系統的集成..............................................28
      4.2.2系統架構設計.....................28
      4.2.3系統網(wǎng)絡(luò )體系結構.........................30
      4.2.4系統功能模塊劃分...................................31
    4.3數據庫設計.....................................33
      4.3.1數據庫設計方案.......................................33
        4.3.2表的設計..........................................34
    4.4系統實(shí)現..................................................37
      4,4.1表示層的實(shí)現............................................37
      4.4.2服務(wù)層的實(shí)現.......................................................38
      4.4.3業(yè)務(wù)邏輯層的實(shí)現..............................41
      4.4.4數據訪(fǎng)問(wèn)層的實(shí)現.............................. 43
    4.5關(guān)鍵技術(shù)研究.........................................44
      4.5.1系統性能優(yōu)化...............................................44
      4.5.2數據庫安全機制...............................................47
第五章回顧與展望.................................... 49
    5.1全文總結和工作回顧........................................................49
    5.2后續工作與展望...............................................49
參考文獻..................................51
致謝..........................................55
攻讀學(xué)位期間主要的研究成果..................................... 56

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

【大學(xué)課程表問(wèn)題中的算法研究與應用】相關(guān)文章：

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

粗決策樹(shù)動(dòng)態(tài)規則提取算法研究及應用03-17

變換在幾何問(wèn)題中的應用03-07

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

關(guān)于LZW算法的改進(jìn)研究03-25

LDPC碼譯碼算法研究03-07

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

指紋識別算法研究03-08

FFT算法的研究與DSP實(shí)現03-07