基于優(yōu)先級分類的排課算法設(shè)計

楊 明

（南京鐵道職業(yè)技術(shù)學(xué)院，江蘇 南京 210031）

基于優(yōu)先級分類的排課算法設(shè)計

楊 明

（南京鐵道職業(yè)技術(shù)學(xué)院，江蘇 南京 210031）

文章分析了國內(nèi)外對于排課算法的研究現(xiàn)狀，提出了基于等價分類的優(yōu)先級排課算法的思想，包含確定算法的基本原則、算法的等價分類和優(yōu)先級的確定，最后給出了算法的流程圖和相關(guān)測試數(shù)據(jù)。

教務(wù)系統(tǒng)；算法；優(yōu)先級

1 目前排課算法現(xiàn)狀

對于課表的研究，國外最早于20世紀(jì)50年代出現(xiàn)。直到1962年，戈特利布最早提出了一個數(shù)學(xué)模型，用于求解課表問題。此后大家對此問題進行了深入的討論和廣泛的研究，如印度Vastapur大學(xué)的Arabinda Tripathy和加拿大Montreal大學(xué)的Jean Aubin等。Tripathy，他的主要工作是以“人”為單位進行排課，利用拉格朗日松弛法來解決，這種方法雖然可以減少變量的個數(shù)，但是人為造成課程間的沖突。其他有代表性的算法有遺傳算法、螞蟻算法等，通過實踐表明，單純的運用數(shù)據(jù)方法去解決人為因素過多的課表問題，不是切實可行的辦法。

直到1976年，Even等人證明了此問題本質(zhì)上就是一個NP完全問題。因為對于排課的約束條件太多，而一時也無法找到所有的約束條件，隨著排課時間段和學(xué)生人數(shù)、課程數(shù)的不斷增加，排列組合方案會成幾何數(shù)增長，進而在尋求最優(yōu)解的過程中，系統(tǒng)會消耗大量的時間和資源，最后到了讓人無法忍受的程度，從而導(dǎo)致系統(tǒng)無法使用。

國內(nèi)對排課的研究始于20世紀(jì)80年代初，林漳希、林堯瑞教授于1984年宣布了此課題研究成果，成為國內(nèi)研究的基礎(chǔ)。……