高等院校課程優(yōu)化編排.pdf

1、在高等院校中，由于其規(guī)模大、學(xué)科多、課程多、師生比高、校舍資源緊、課程聯(lián)系密切等特點(diǎn)，使教學(xué)調(diào)度工作，即教學(xué)計(jì)劃的實(shí)施與管理，成為一項(xiàng)非常復(fù)雜而又細(xì)致的工作，尤以課程表的編制工作更為突出。近年來，由于高校之間的合并，高校辦學(xué)規(guī)模的擴(kuò)大，以及學(xué)科專業(yè)的不斷細(xì)化等因素，使得教學(xué)資源的爭(zhēng)奪一再緊張，因此，如何編排一張科學(xué)、有效的課程表，就成為一項(xiàng)非常有意義的研究。 排課表問題又稱時(shí)間表問題。排課表問題就是在滿足各種要求和限制的前提下，

2、解決對(duì)時(shí)間和空間資源爭(zhēng)奪而引起的沖突。這是一個(gè)多因素的優(yōu)化決策問題，是組合規(guī)劃中的典型問題。70年代中期，S.Even等人在SIAMJ.COMPUTE雜志上發(fā)表題為《關(guān)于時(shí)間表和雜物流問題的時(shí)間復(fù)雜性》一文，首次論證了排課表問題是NP-完全問題，將排課表問題理論化。之后很多人嘗試采用多種方法對(duì)此問題進(jìn)行求解。但由于排課表問題所涉及的信息較多，并且求解排課表問題最佳解的時(shí)間復(fù)雜性是課程表規(guī)模的指數(shù)級(jí)，所以對(duì)于有一定規(guī)模的排課表問題，一般采

3、用的都是求較佳解的算法。 在排課表問題中涉及到班級(jí)、教師、上課時(shí)間、課程、教室等這五個(gè)制約因素。排課表問題的求解過程就是對(duì)任何一門課程，尋找一個(gè)合適的教師和時(shí)間-教室對(duì)。在安排時(shí)不能發(fā)生沖突，同時(shí)應(yīng)盡量滿足經(jīng)驗(yàn)常識(shí)。在J.A.Bondy的《Graphtheorywithapplications》一書中對(duì)僅有教師和班級(jí)兩個(gè)制約因素的情況進(jìn)行了討論，并用邊染色理論解決了這一問題。本文將對(duì)有教師、班級(jí)以及教室三個(gè)制約因素時(shí)的排課表問題

4、進(jìn)行討論，建立了一個(gè)特殊的三分圖的模型(某兩個(gè)部分之間沒有連線)，并將二分圖中的匹配推廣到特殊三分圖中的獨(dú)立典型路組，對(duì)建立的排課表問題模型進(jìn)行了求解。 本文共分三章，各章的主要內(nèi)容如下： 第一章為引言，介紹了排課表問題的研究背景、發(fā)展概況以及研究現(xiàn)狀。 第二章為模型建立與求解。由于排課表問題涉及到多個(gè)制約因素，在第二章首先說明了排課表問題可以歸結(jié)為教師、班級(jí)以及教室這三者之間的關(guān)系問題。然后建立了一個(gè)特殊三分圖