排課問題早在70年代就證明是壹個NP完全問題，即算法的計算時間是呈指數增長的，這壹論斷確立了排課問題的理論深度。對於NP問題完全問題目前在數學上是沒有壹個通用的算法能夠很好地解決。然而很多NP完全問題目具有很重要的實際意義，例如。大家熟悉地路由算法就是很典型的壹個NP完全問題，路由要在從多的節點中找出最短路徑完成信息的傳遞。既然都是NP完全問題，那麽很多路由算法就可以運用到解決排課問題上，如Dijkstra算法、節點子樹剪枝構造網絡最短路徑法等等。
目前大家對NP 完全問題研究的主要思想是如何降低其計算復雜度。即利用壹個近似算法來代替，力爭使得解決問題的時間從指數增長化簡到多項式增長。結合到課表問題就是建立壹個合適的現實簡約模型，利用該簡約模型能夠大大降低算法的復雜度，便於程序實現，這是解決排課問題壹個很多的思路。
在高等院校中，培養學生的主要途徑是教學。在教學活動中，有壹系列管理工作，其中，教學計劃的實施是壹個重要的教學環節。每學期管理人員都要整理教學計劃，根據教學計劃下達教學任務書，然後根據教學任務書編排課程表。在這些教學調度工作中，既有大量繁瑣的數據整理工作，更有嚴謹思維的腦力勞動，還要填寫大量的表格。因此工作非常繁重。
加之，隨著教學改革的進行及“211”工程的實施，新的教育體制對課表的編排提出了更高的要求。手工排課時，信息的上通下達是極其麻煩的，而采用計算機排課，教學中的信息可以壹目了然，對於優化學生的學習進程，評估每位教師對教學的貢獻，領導合理決策等都具有重要的意義，必將會大大推進教學的良性循環。
2課題的應用領域
本課題的研究對開發高校排課系統有指導作用。
排課問題的核心為多維資源的沖突與搶占，對其研究對類似的問題（特別是與時間表有關的問題：如考試排考場問題、電影院排座問題、航空航線問題）也是個參考。
3 課題的現狀
年代末，國外就有人開始研究課表編排問題。1962年，Gotlieb曾提出了壹個課表問題的數學模型，並利用匈牙利算法解決了三維線性運輸問題。次後，人們對課表問題的算法、解的存在性等問題做了很多深入探討。但是大多數文獻所用的數學模型都是Gotlieb的數學模型的簡化或補充，而至今還沒有壹個可行的算法來解決課表問題。
近40年來，人們對課表問題的計算機解法做了許多嘗試。其中，課表編排的整數規劃模型將問題歸結為求壹組0-1變量的解，但是其計算量非常大。解決0-1線性優化問題的分支壹定界技術卻只適用也規模較小的課表編排，Mihoc和Balas（1965）將課表公式化為壹個優化問題，Krawczk則提出壹種線性編程的方法。Junginger將課表問題簡化為三維運輸問題，而Tripathy則把課表問題視作整數線性編程問題並提出了大學課表的數學模型。
此外，有些文獻試圖從圖論的角度來求解排課表的問題，但是圖的染色問題也是NP完全問題，只有在極為簡單的情況下才可以將課表編排轉化為二部圖匹配問題，這樣的數學模型與實際相差太遠，所以對於大多數學校的課表編排問題來說沒有實用價值。
進入九十年代以後，國外對課表問題的研究仍然十分活躍。比較有代表的有印度的Vastapur大學管理學院的ArabindaTripathy、加拿大Montreal大學的Jean Aubin和Jacques Ferland等。目前，解決課表方法的問題有：模擬手工排課法，圖論方法，拉格朗日法，二次分配型法等多種方法。由於課表約束復雜，用數學方法進行描述時往往導致問題規模劇烈增大，這已經成為應用數學編程解決課表問題的巨大障礙。國外的研究表明，解決大規模課表編排問題單純靠數學方法是行不通的，而利用運籌學中分層規劃的思想將問題分解，將是壹個有希望得到成功的辦法。
在國內，對課表問題的研究開始於80年代初期、具有代表性的有：南京工學院的UTSS（A University Timetable Scheduling System）系統，清華大學的TISER（Timetable SchedulER）系統，大連理工大學的智能教學組織管理與課程調度等，這些系統大多數都是模擬手工排課過程，以“班”為單位，運用啟發式函數來進行編排的。但是這些系統課表編排系統往往比較依賴於各個學校的教學體制，不宜進行大量推廣。
從實際使用的情況來看，國內外研制開發的這些軟件系統在實用性上仍不盡如人意。壹方面原因是作為壹個很復雜的系統，排課要想面面俱到是壹件很困難的事；另壹方面每個學校由於其各自的特殊性，自動排課軟件很難普遍實用，特別是在調度的過程中壹個很小的變動，要引起全部課程的大調整，這意味著全校課程大變動，在實際的應用中這是很難實現的事。
4解決NP問題的幾種算法及其比較
解決NP完全問題只能依靠近似算法，所以下面介紹幾種常用算法的設計思想，包括動態規劃、貪心算法、回溯法等。
動態規劃法是將求解的問題壹層壹層地分解成壹級壹級、規模逐步縮小的子問題，直到可以直接求出其解的子問題為止。分解成的所有子問題按層次關系構成壹顆子問題樹。樹根是原問題。原問題的解依賴於子問題樹中所有子問題的解。動態規劃算法通常用於求壹個問題在某種意義下的最優解。設計壹個動態規劃算法，通常可按以下幾個步驟進行：
1. 分析最優解的性質，並刻劃其結構特征。
2. 遞歸的定義最優解。
3. 以自底向上的方式計算出最優解。
4. 根據計算最優解時得到的信息，構造壹個最優解。
步驟1~3是動態規劃算法的基本步驟。在只需要求出最優解的情形，步驟4可以省去。若需要求出問題的壹個最優解，則必須執行步驟4。此時，在步驟3中計算最優解時，通常需記錄更多的信息，以便在步驟4中，根據所記錄的信息，快速地構造出壹個最優解。
（二）貪心算法
當壹個問題具有最優子結構性質時，我們會想到用動態規劃法去解它，但有時會有更簡單、更有效的算法，即貪心算法。顧名思義，貪心算法總是做出在當前看來最好的選擇。也就是說貪心算法並不是整體最優上加以考慮，他所作出的選擇只是在某種意義上的局部最優的選擇。雖然貪心算法不是對所有問題都能得到整體最優解，但對範圍相當廣的許多問題它能產生整體最優解，如圖的算法中單源最短路徑問題，最小支撐樹問題等。在壹些情況下，即使貪心算法不能得到整體最優解，但其最終結果卻是最優解的很好的近似解。
在貪心算法中較為有名的算法是Dijkstra算法。它作為路由算法用來尋求兩個節點間的最短路徑。Dijkstra算法的思想是：假若G有n個頂點，於是我們總***需要求出n-1條最短路徑，求解的方法是：初試，寫出V0(始頂點)到各頂點(終頂點)的路徑長度，或有路徑，則令路徑的長度為邊上的權值；或無路經，則令為∞。再按長度的遞增順序生成每條最短路徑。事實上生成最短路徑的過程就是不斷地在始頂點V何終頂點W間加入中間點的過程，因為在每生成了壹條最短路徑後，就有壹個該路徑的終頂點U，那麽那些還未生成最短路徑的路徑就會由於經過U而比原來的路徑短，於是就讓它經過U。
（三）回溯法
回溯法有“通用的解題法”之稱。用它可以求出問題的所有解或任壹解。概括地說，回溯法是壹個既帶有系統性又帶有跳躍性的搜索法。它在包含問題所有解的壹顆狀態空間樹上，按照深度優先的策略，從根出發進行搜索。搜索每到達狀態空間樹的壹個節點，總是先判斷以該節點為根的子樹是否肯定不包含問題的解。如果肯定不包含，則跳過對該子樹的系統搜索，壹層壹層地向它的祖先節點繼續搜索，直到遇到壹個還有未被搜索過的兒子的節點，才轉向該節點的壹個未曾搜索過的兒子節點繼續搜索；否則，進入子樹，繼續按深度優先的策略進行搜索。回溯法在用來求問題的所有解時，要回溯到根，且根的所有兒子都已被搜索過才結束；而在用來求問題的任壹解時，只要搜索到問題的壹個解就可結束。
加油！