TTP在高校排課中的研究與應(yīng)用.pdf

1、時(shí)間表問(wèn)題(TTP)是一個(gè)應(yīng)用廣泛的、典型的組合優(yōu)化和不確定性調(diào)度問(wèn)題，并且已經(jīng)被證明是NP完全問(wèn)題，課程表的編排問(wèn)題是TTP的一種典型實(shí)例。排課是教學(xué)管理中最基本、最重要、同時(shí)也是最復(fù)雜的管理工作之一，其實(shí)質(zhì)就是為學(xué)校所設(shè)置的課程安排一組適當(dāng)?shù)慕虒W(xué)時(shí)間與空間，從而使整個(gè)教學(xué)能夠有計(jì)劃有秩序地進(jìn)行。動(dòng)態(tài)規(guī)劃是解決多階段決策過(guò)程最優(yōu)化問(wèn)題的一種方法，它把比較復(fù)雜的問(wèn)題劃分為若干個(gè)階段，通過(guò)逐段求解，最終求得全局最優(yōu)解。 本文立足農(nóng)

2、林職業(yè)技術(shù)學(xué)院的實(shí)際情況，運(yùn)用多階段決策技術(shù)和動(dòng)態(tài)規(guī)劃技術(shù)對(duì)排課問(wèn)題進(jìn)行了分解，在分析現(xiàn)有軟件系統(tǒng)算法的基礎(chǔ)上，提出了一種新的多階段自動(dòng)排課算法MACA(MultistageAuto-arrangingCourseAlgorithm)，并在此基礎(chǔ)上建立了一個(gè)通用的排課系統(tǒng)，能有效的滿足各種排課需求。 2005年1月，該系統(tǒng)在農(nóng)林職業(yè)技術(shù)學(xué)院投入運(yùn)行，至今為止，運(yùn)行效果良好。2005年7月，系統(tǒng)通過(guò)軟件著作權(quán)申請(qǐng)。2006年初，在

3、該系統(tǒng)基礎(chǔ)上申請(qǐng)通過(guò)了上海市教委項(xiàng)目“通用多學(xué)制型-排課考試費(fèi)用計(jì)算鏈應(yīng)用系統(tǒng)研究”。 本論文主要完成了以下工作：(1)詳紐分析了高校排課問(wèn)題，分析了課表編排過(guò)程中涉及的因素及各種約束條件；(2)根據(jù)數(shù)據(jù)庫(kù)系統(tǒng)設(shè)計(jì)理論，討論了排課系統(tǒng)設(shè)計(jì)過(guò)程，包括數(shù)據(jù)庫(kù)的概念模型設(shè)計(jì)、邏輯設(shè)計(jì)、物理設(shè)計(jì)及其實(shí)施；(3)詳細(xì)分析了排課中各種沖突，并對(duì)每種沖突采取不同的沖突稽核方法；(4)設(shè)計(jì)了教師分配算法：教師等概率分配算法EPDA和首次適應(yīng)分配

4、算法FMDA，并分析比較了這兩種方法的優(yōu)缺點(diǎn)，最后提出了將這兩種分配算法結(jié)合起來(lái)的優(yōu)化算法——等概率首次適應(yīng)分配算法EPFMDA；(5)設(shè)計(jì)了場(chǎng)地最佳適應(yīng)分配算法OADA，把場(chǎng)地按類(lèi)型和大小進(jìn)行分配，實(shí)現(xiàn)了資源的既充分又合理的利用；(6)引入三維時(shí)間片劃分方法，在此基礎(chǔ)上分析了排課問(wèn)題的可行解和近似最優(yōu)解，并設(shè)計(jì)了時(shí)間片分配算法TSDA，采用了加權(quán)分組匹配思想。(7)立足農(nóng)林職業(yè)技術(shù)學(xué)院的實(shí)際情況，實(shí)現(xiàn)了功能強(qiáng)大的排課系統(tǒng)，不僅可以實(shí)現(xiàn)