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

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

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

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

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