【文章內(nèi)容簡介】 個學(xué)院不同的特殊情況，以教師為重點，學(xué)院可以隨意調(diào)整。另一個功能，學(xué)院在這塊可以查詢本學(xué)院的課表，還有學(xué)院內(nèi)班級的課表。還有對已排好的課程做一些調(diào)整操作。 這一模塊主要完成課程上課時間、上課地點的安排。它的實現(xiàn)運用了遺傳算法中的選擇、交叉、變異等操作，對算法得出的結(jié)果中最好的一個個體保留，就是要求的結(jié)果，雖然不是最完美符合的，但是它的適應(yīng)度值已經(jīng)完全可以符合學(xué)校教學(xué)所要求的了。然后，對這個（班級，教師，課程，時間）記錄做變換，讓位置表去填充它，當(dāng)然是按條件填充，就可以完成整個排課的大部分工作了，從而得到課表。此圖描述了功能模塊圖，如圖2示：圖2 功能模塊圖Chart 2 the function model chart 排課是將教師與學(xué)生在時間和空間上根據(jù)不同的約束條件進行排列組合，在此同時也要安排課程，以使教學(xué)正常進行。在本文約束條件主要為避免沖突，所謂沖突，它所包含的內(nèi)容很廣泛，幾乎發(fā)生在所有兩個或多個排課涉及因素之間。避免沖突也是排課問題中要解決的核心問題。只有在滿足全部約束條件和避免所有沖突的基礎(chǔ)上，才能保證整個教學(xué)計劃合理正常進行。而對教師、教室、學(xué)生及時間等幾部分資源進行最優(yōu)化組合配置，才能保證充分發(fā)揮各資源的優(yōu)勢和提高教學(xué)質(zhì)量。在本文中，我們把排課過程中的約束條件分為三類:基本硬約束、硬約束和軟約束。其中基本硬約束是指教師、學(xué)生和教室在時空概念上發(fā)生了不可能發(fā)生的事情，既是時間，空間，人之間的矛盾，它是排課過程中最基本的約束條件，也是眾多排課模型中都要涉及的約束條件；硬約束是根據(jù)學(xué)校的實際情況，排課時必須遵循的原則，否則將會導(dǎo)致排課結(jié)果無意義，所以要因地制宜；軟約束是指排課過程中滿足更佳但不滿足又無妨的約束條件，這些條件的目的就是使課表更加人性化，每個排課都是要突出解決軟約束這個問題的，違背這些約束就與實際情況相悖。所以，可知在三類約束條件之中，前兩者是衡量排課方案是否切實可行的基本標(biāo)準(zhǔn)，軟約束是衡量排課方案是否人性化的標(biāo)準(zhǔn)，通常判別一個排課方案的優(yōu)劣標(biāo)準(zhǔn)有多個。可以把排課過程常見的約束條件分類羅列如下表22所示，這些約束條件也比較符合排課過程的實際情況。表22 約束表Table 22 constraint table基本硬約束B1同一時間，同一班級不能上兩門不同的課程B2同一時間，同一個教師不能上兩門不同的課程B3同一個時間，同一個教室不能上兩門不同的課程硬約束H1課程的學(xué)時在每周要均勻化H2滿足每門課的特定教學(xué)資源H3教室足夠大，能夠容納學(xué)生H4某些課程要特定安排，如某些教師的課程要固定H5教師學(xué)生上課不能用于在路途上的奔波H6體育課盡量安排在下午軟約束S1課程的分布要做到離散化S2一周有些時段處于最佳利于學(xué)習(xí)時間S3盡量不讓老師連著上課S4班級相鄰上課地點盡量近些3 自動排課系統(tǒng)的設(shè)計在本課題中，遺傳算法解決的問題只是求出班級+課程+教師+時間的記錄集，得到比較優(yōu)的一個解，然后再去按條件用教室去填充這個記錄集，就形成了可行可用的課表。這塊的設(shè)計在整個系統(tǒng)是最重要的，效率的高低，課表的優(yōu)劣都由本模塊確定。整個系統(tǒng)的流程分為以下幾個主要的過程:(1)初始種群的產(chǎn)生:首先基因的編碼，根據(jù)制定的編碼方案，對每條染色體進行初始化，其次一條條染色體組成一個個體，既是形成一個二維表（可稱為課表，但是適應(yīng)度值不高）。(1)沖突檢測和消除:初始化種群后，先對其進行各類沖突的檢測，如存在沖突則消除它，而且在每次產(chǎn)生下一代后都要進行沖突檢測。(2)計算出每個個體的適應(yīng)度函數(shù)值，以進行優(yōu)勝劣汰。(3)遺傳操作:包括選擇算子、交叉算子和變異算子，產(chǎn)生子代，逐漸優(yōu)化。(4)迭代第四步，直到進化停止，就是generation=終止代數(shù)N。(5)班級+課程+教師+時間的記錄集的產(chǎn)生。圖3 遺傳算法流程圖實施遺傳算法的第1步，就是把與求解目標(biāo)相關(guān)的實際參數(shù)進行基因編碼，這是算法的關(guān)鍵與難點。構(gòu)造合適的基因結(jié)構(gòu)是遺傳算法能否順利實現(xiàn)的關(guān)鍵，設(shè)定混合式的教師編碼作為本系統(tǒng)遺傳算法的“基因”。二進制基因構(gòu)成規(guī)則為:是否固定*教師編號號*課程編號*課程性質(zhì)分別對應(yīng)的寬為1+15+16+16共6B。下面我們給了很清晰的解釋：圖4 編碼結(jié)構(gòu)圖下面我們對每個字段給予解釋： 有些教師的課程是固定在某個時間段的，所以在排課過程中，判斷第一位就可以得知可否移動此基因片。這也反應(yīng)了排課要人性化，畢竟有些教師有特殊的要求，例如，年齡、事物等等。 我們給了15bit去表示教師，15bit能表示215個數(shù)，足矣滿足任何一所高校的教師編號，所以，在數(shù)據(jù)庫里，教師表里教師編號的數(shù)據(jù)項要為短整型。 唯一確定一門課程，216個數(shù)，也足以表示一個學(xué)校的課程。 為了解決“特定資源”沖突問題，可在教師編碼中加上2B表示該教師所教授的課程的性質(zhì)。每一門課程都有其各自不同的特點，比如上機課需要在機房上課，英語口語需要在語音室上課，體育課需要在操場上課，為此我們規(guī)定：把16bits分開，前后8bits各有不同的意思； 圖5比特信息圖在此我們把課程分為專業(yè)必修課，專選科，公共課，上機實驗課，專業(yè)實驗課，體育課，英語語音課，前三個屬于理論課，不在此分配教室。區(qū)分：計算機專業(yè)的實驗課是和非計算機專業(yè)的上節(jié)實驗課不同的，他們有自己的實驗室，屬于專業(yè)實驗課。 前8位編碼不同時表示不同的意思：表31 編碼課程關(guān)聯(lián)表Table 31 the relational table of coding and course編碼值表示課程類10000000專業(yè)必修課11000000專業(yè)選修課11100000公共課11110000上機實驗課11111000專業(yè)實驗課11111100體育課11111110語音課后8位編碼表示當(dāng)此教師固定在這個時間片上課時，所在的時間片值。對于每一門課程既可能只上一次(規(guī)定2學(xué)時課占用一個時間片)，也可能上多次，如4學(xué)時、6學(xué)時等。上2學(xué)時課時，該教師編碼只能出現(xiàn)1次，上4學(xué)時課時該教師編碼出現(xiàn)2次，依次類推。在大多數(shù)，每周上6學(xué)時的課程不會太多，大多數(shù)時4學(xué)時和2學(xué)時； 通過以上把課程與教師等同的處理后，原課表的五要素(班級、教室、課程、時間、教師)轉(zhuǎn)化為四要素(班級、課程、時間）和班級。功能室(實驗室機房、語音室等)已經(jīng)在編碼時分配好，而理論課的那些，要等到后面再去分配。為了更好地闡述排課遺傳算法，定義排課遺傳算法名詞：a.“基因”——混合型的教師編碼，即TIT25時間片中的值；b.“染色體”——班級名稱與TlT25中的“基因”組成的串；c.“個體”——由bjs（班級數(shù)）個染色體組合而成的二維數(shù)據(jù)表，即對應(yīng)于一張課表。其中BJS為參與課表編排的班級總數(shù)；d.“種群”——由ZQS個個體構(gòu)成。其中ZQS為種群大小。 初始化種群每一個“染色體”都是班級的一個課表，是開課任務(wù)書中的一個班級所有記錄組成的，形成的是班級+教室+課程+時間一條記錄。 對每一個課程表可以形成一個二維數(shù)組kcb (25,bjs)，每一列就表示一個班級的課表。首先把固定教學(xué)時間的教師編碼填入該行中，然后使用隨機函數(shù)產(chǎn)生一個1—25的數(shù)，將該班的其它教師編碼填入其中。如產(chǎn)生的隨機數(shù)對應(yīng)的時間片中己有數(shù)據(jù)，則重新產(chǎn)生，直到將所有教師編碼無重復(fù)地填入該行中。這樣就有了一條染色體(一個初始的班課程表)。如此循環(huán)bjs次，產(chǎn)生了與班級數(shù)目對等的染色體數(shù)目。于是，一個初始個體便產(chǎn)生了。按種群規(guī)模的大小ZQS，產(chǎn)生一定數(shù)量的個體，每個個體都存放到一個按序編號的表中，由這些個體組成初始種群。很明顯，由上述方式產(chǎn)生的個體通常含有大量的沖突。另外，在初始化種群時，基于容器的容器使其更加簡捷。對于數(shù)據(jù)庫中教學(xué)樓，教室，班級等一些數(shù)量都未知的數(shù)據(jù)進行存儲，運用數(shù)組顯然不能解決，會出現(xiàn)很多的冗余，浪費內(nèi)存，并且處理繁瑣。關(guān)聯(lián)容器的使用方法如圖6所示：圖6容器結(jié)構(gòu)圖完成種群初始化后，個體的數(shù)據(jù)結(jié)構(gòu)如下圖示：圖7 個體結(jié)構(gòu)圖4 數(shù)據(jù)庫問題 數(shù)據(jù)庫設(shè)計 數(shù)據(jù)庫設(shè)計是建立系統(tǒng)數(shù)據(jù)庫及其應(yīng)用系統(tǒng)的重要環(huán)節(jié)，系統(tǒng)的各個部分能否緊密地結(jié)合在一起以及如何結(jié)合，關(guān)鍵在數(shù)據(jù)庫，只有對數(shù)據(jù)庫進行合理的邏輯設(shè)計和有效的物理設(shè)計才能開發(fā)出完善而高效的排課系統(tǒng)。本文的數(shù)據(jù)庫設(shè)計及其實現(xiàn)如下： 概念模型設(shè)計 因為概念結(jié)構(gòu)是面向現(xiàn)實世界的，用戶容易理解，能夠參加設(shè)計討論，提出意見，在將分析結(jié)果抽象為邏輯數(shù)據(jù)庫時可以降低設(shè)計的難度。這會將數(shù)據(jù)庫的概念結(jié)構(gòu)轉(zhuǎn)換為邏輯結(jié)構(gòu)方法簡單，易于實現(xiàn)。對于排課問題要進行的分析主要有:教學(xué)計劃、各學(xué)院教學(xué)任務(wù)、教室基礎(chǔ)數(shù)據(jù)、時間模式、開課任務(wù)、及各種課表等數(shù)據(jù)。 這些關(guān)系用ER圖表示如圖8，9，10:圖8 院管理ER圖圖9 校管理ER圖圖10 總ER圖 邏輯模型設(shè)計 在邏輯模型設(shè)計中，并不是劃分?jǐn)?shù)據(jù)的粒度越小越精確就會越好，而是要符合設(shè)計現(xiàn)狀要求和系統(tǒng)實現(xiàn)便捷，也就是說，范式越高也不一定越好。具體來說創(chuàng)建了以下各表:表 41 用戶表:UserTable 41 user table:User編號數(shù)據(jù)項數(shù)據(jù)項別名數(shù)據(jù)類型數(shù)據(jù)項含義1用戶名username Char(12)唯一2密碼passwdChar(20)3學(xué)院academyChar(20)學(xué)院名，如果空的話就是代表教務(wù)處表42 教學(xué)計劃表:TeachPlanTable 42 teaching plan table:TeachPlan編號數(shù)據(jù)項數(shù)據(jù)項別名數(shù)據(jù)類型數(shù)據(jù)項含義1班級classChar(15)主屬性2班級編號CnoChar(10)主屬性3課程courseChar(15)4課程編號courseNoSmallint(2)主屬性5學(xué)院academyChar(15)6人數(shù)Pnoint7課程屬性courseAtrrChar(15)8周節(jié)數(shù)pitchNumSmallint(2)9周數(shù)weekSumSmallint(2)10開課學(xué)期semesterChar(15)表43 教室表：ClassroomTable 43 classroom table：Classroom編號數(shù)據(jù)項數(shù)據(jù)項別名數(shù)據(jù)類型數(shù)據(jù)項含義1教學(xué)樓TbuildingChar(10)主屬性2門號houseNoChar(10)主屬性3容納人數(shù)containSumint4教室屬性houseAtrrChar(10)表44語音課體育課上機課位置表：Y_T_STable 44 the place table：Y_T_S編號數(shù)據(jù)項數(shù)據(jù)項別名數(shù)據(jù)類型數(shù)據(jù)項含義1類別categoryChar(1)區(qū)別三類教室2教室名roomnameChar(15)3教室編號roomIDsmallint4班級classChar(15)加上班級就可以確定班級上課的位置范圍5學(xué)院academyChar(15)表 45 理論課教室表：LLKAddressTable 45 the classroom table of theory cour