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