【文章內(nèi)容簡介】 ， tI， sK） }。最后，根據(jù)限制條件，把班級(jí) 課程 時(shí)間 教師對(duì)關(guān)聯(lián)到教室集合。最后形成完整的課表 TB={（ cb， lr， ti， sp， rj）， ......（ cB， lR， tI， sK， rJ） }，同時(shí)也解決了空間上的沖突。 數(shù)據(jù)流程圖 系統(tǒng)的數(shù)據(jù)流程圖如圖 31， 32， 33， 34 所示 : 圖 31 排課系統(tǒng)數(shù)據(jù)流圖第 1層 Chart 31 the first layer of timetabling system data flow chart 如圖 32所示，用戶在登錄系統(tǒng)時(shí)，根據(jù)自己的用戶名和密碼，去登錄系統(tǒng)。 10 數(shù)據(jù)庫中記錄每一個(gè)登錄者的信息，并會(huì)及時(shí)反饋。 圖 32 排課系統(tǒng)數(shù)據(jù)流 第 2 層 Chart 32 the second layer of timetabling system data flow chart 根據(jù)登錄者不同的身份，進(jìn)入不同的功能模塊，分別進(jìn)行不同的操作，學(xué)院身份進(jìn)入圖33的學(xué)院管理模塊，落實(shí)學(xué)院開課任務(wù)書，教務(wù)處身份進(jìn)入圖 15的校管理模塊，匯聚校開課任務(wù)書，并且進(jìn)行排課。 圖 33 排課系統(tǒng)數(shù)據(jù)流圖第 3層 Chart 33 the third layer of timetabling system data flow chart 正如數(shù)據(jù)流圖的第二層所示，數(shù)據(jù)分流后，在此模塊，學(xué)院會(huì)根據(jù)自己學(xué)院的特殊情況 11 完成學(xué)院的開課任務(wù)書，所謂開課任務(wù)書，既 是課程、班級(jí)和老師的組合，還沒有結(jié)合時(shí)間和地點(diǎn)此二維因素，僅僅表達(dá)此班上哪位老師講授的哪門課程的問題。 圖 34 排課系統(tǒng)數(shù)據(jù)流圖第 3層 Chart 34 the third layer of timetabling system data flow chart 在此層中，所謂的開課任務(wù)書的聚合，并不是人工操作的，而是所有學(xué)院處理好院開課任務(wù)書后，反饋到數(shù)據(jù)庫后，即會(huì)完成校開課任務(wù)書的聚合。完成教室位置規(guī)劃需要考慮整個(gè)學(xué)校教學(xué)樓的情況，所以必須在校模塊中實(shí)現(xiàn)。 12 數(shù)據(jù)庫 設(shè)計(jì) 數(shù)據(jù)庫設(shè)計(jì)是建立系統(tǒng)數(shù)據(jù)庫及其應(yīng)用系統(tǒng)的重要環(huán)節(jié)，系統(tǒng)的各個(gè)部分能否緊密地結(jié)合在一起以及如何結(jié)合，關(guān)鍵在數(shù)據(jù)庫，只有對(duì)數(shù)據(jù)庫進(jìn)行合理的邏輯設(shè)計(jì)和有效的物理設(shè)計(jì)才能開發(fā)出完善而高效的排課系統(tǒng)。 本文的數(shù)據(jù)庫設(shè)計(jì)及其實(shí)現(xiàn)如下： 概念模型設(shè)計(jì) 因?yàn)楦拍罱Y(jié)構(gòu)是面向現(xiàn)實(shí)世界的，用戶容易理解，能夠參加設(shè)計(jì)討論，提出意見，在將分析結(jié)果抽象為邏輯數(shù)據(jù)庫時(shí)可以降低設(shè)計(jì)的難度。這會(huì)將數(shù)據(jù)庫的概念結(jié)構(gòu)轉(zhuǎn)換為邏輯結(jié)構(gòu)方法簡單，易于實(shí)現(xiàn)。對(duì)于排課問題要進(jìn)行的分析主要有 :教學(xué)計(jì)劃、各學(xué)院教學(xué)任務(wù)、教室基礎(chǔ)數(shù)據(jù)、時(shí) 間模式、開課任務(wù)、及各種課表等數(shù)據(jù)。 這些關(guān)系用 ER 圖表示如圖 41， 42， 43: 圖 41 院管理 ER圖 Chart 41 the ER chart of college management 13 圖 42 校管理 ER圖 Chart 42 the ER chart of school management 圖 43 總 ER 圖 Chart 43 the overall ER chart 邏輯模型設(shè)計(jì) 在邏輯模型設(shè)計(jì)中 ， 并不是劃分 數(shù)據(jù) 的 粒度 越小越精確就會(huì) 越好，而是要符合設(shè)計(jì)現(xiàn)狀要求和系統(tǒng)實(shí)現(xiàn)便捷，也就是說，范式越高也不一定越好。具體來說創(chuàng)建了以下各表 : 表 41 用戶表 :User Table 41 user table:User 編號(hào) 數(shù)據(jù)項(xiàng) 數(shù)據(jù)項(xiàng)別名 數(shù)據(jù)類型 數(shù)據(jù)項(xiàng)含義 1 用戶名 username Char(12) 唯一 14 2 密碼 passwd Char(20) 3 學(xué)院 academy Char(20) 學(xué)院名，如果空的話就是代表教務(wù)處 表 42 教學(xué)計(jì)劃表 :TeachPlan Table 42 teaching plan table:TeachPlan 編號(hào) 數(shù)據(jù)項(xiàng) 數(shù)據(jù)項(xiàng)別名 數(shù)據(jù)類型 數(shù)據(jù)項(xiàng)含義 1 班級(jí) class Char(15) 主屬性 2 班級(jí)編號(hào) Cno Char(10) 主屬性 3 課程 course Char(15) 4 課程編號(hào) courseNo Smallint(2) 主屬性 5 學(xué)院 academy Char(15) 6 人數(shù) Pno int 7 課程屬性 courseAtrr Char(15) 8 周節(jié)數(shù) pitchNum Smallint(2) 9 周數(shù) weekSum Smallint(2) 10 開課學(xué)期 semester Char(15) 表 43 教室表： Classroom Table 43 classroom table： Classroom 編號(hào) 數(shù)據(jù)項(xiàng) 數(shù)據(jù)項(xiàng)別名 數(shù)據(jù)類型 數(shù)據(jù)項(xiàng)含義 1 教學(xué)樓 Tbuilding Char(10) 主屬性 2 門號(hào) houseNo Char(10) 主屬性 3 容納人數(shù) containSum int 4 教室屬性 houseAtrr Char(10) 表 44語音課體育課上機(jī)課位置表 ： Y_T_S Table 44 the place table： Y_T_S 編號(hào) 數(shù)據(jù)項(xiàng) 數(shù)據(jù)項(xiàng)別名 數(shù)據(jù)類型 數(shù)據(jù)項(xiàng)含義 1 類別 category Char(1) 區(qū)別三類教室 15 2 教室名 roomname Char(15) 3 教室編號(hào) roomID smallint 4 班級(jí) class Char(15) 加上班級(jí)就可以確定班級(jí)上課的位置范圍 5 學(xué)院 academy Char(15) 表 45 理論課教室表 ： LLKAddress Table 45 the classroom table of theory course： LLKAddress 編號(hào) 數(shù)據(jù)項(xiàng) 數(shù)據(jù)項(xiàng)別名 數(shù)據(jù)類型 數(shù)據(jù)項(xiàng)含義 1 學(xué)院 Academy Char(20) 2 班級(jí) class Char(15) 3 教學(xué)樓 Tbuilding Char(10) 表 46 學(xué)院表 ： Academy Table 46 academy table： Academy 編號(hào) 數(shù)據(jù)項(xiàng) 數(shù)據(jù)項(xiàng)別名 數(shù)據(jù)類型 數(shù)據(jù)項(xiàng)含義 1 學(xué)院 academy Char(20) 2 學(xué)院編號(hào) academyID Char(10) 主鍵 表 47 專業(yè)實(shí)驗(yàn)課位置表 ： ZYSYRoom Table 47 the lab classroom place： ZYSYRoom 編號(hào) 數(shù)據(jù)項(xiàng) 數(shù)據(jù)項(xiàng)別名 數(shù)據(jù)類型 數(shù)據(jù)項(xiàng)含義 1 學(xué)院 academy Char(20) 2 教室名 roomname Char(15) 3 教室編號(hào) roomID smallint 4 班級(jí) class Char(15) 5 容納人數(shù) containSum smallint 表 48 位置表 ： Address 16 Table 48 place table： Address 編號(hào) 數(shù)據(jù)項(xiàng) 數(shù)據(jù)項(xiàng)別名 數(shù)據(jù)類型 數(shù)據(jù)項(xiàng)含義 1 學(xué)院 academy Char(15) 唯一 2 教學(xué)樓 Tbuiding Char(10) 3 班級(jí) Class Char(15) 表 49 教師 _課程表 T_C Table 47 teacher and course table 編號(hào) 數(shù)據(jù)項(xiàng) 數(shù)據(jù)項(xiàng)別名 數(shù)據(jù)類型 數(shù)據(jù)項(xiàng)含義 1 教師名 Tname char(10) 2 教師編號(hào) Tno Smallint 主屬性 3 課程 course Char(15) 4 課程編號(hào) courseNo Smallint 主屬性 表 410 教師表 ： Teacher Table 410 teacher table： Teacher 編號(hào) 數(shù)據(jù)項(xiàng) 數(shù)據(jù)項(xiàng)別名 數(shù)據(jù)類型 數(shù)據(jù)項(xiàng)含義 1 教師名 Tname char(10) 2 教師編號(hào) Tno Smallint 唯一 3 學(xué)院 academy char(15) 4 年齡 Tage Smallint 正整數(shù) 5 職稱 Title char(10) 表 411 開課任務(wù)表 ： ClassTask Table 411 the plan table： ClassTask 編號(hào) 數(shù)據(jù)項(xiàng) 數(shù)據(jù)項(xiàng)別名 數(shù)據(jù)類型 數(shù)據(jù)項(xiàng)含義 1 開課學(xué)期 semester Char(15) 主屬性 2 學(xué)院 academy Char(15) 3 班級(jí) class Char(15) 主屬性 4 教師名 Tname char(10) 17 5 教師編號(hào) Tno Smallint 主屬性 6 課程編號(hào) courseNo Smallint 7 人數(shù) Pno smallint 8 課程 course smallint 9 課程屬性 courseAtrr char(15) 10 周數(shù) weekSum Smallint 11 上課次數(shù) times Smallint 12 是否固定 IsSettled Char(1) 為 0 則不固定 13 固定時(shí)間位置 TimePitch smallint 表 412 課表 ： CourseTable Table 411 course table： CourseTable 編號(hào) 數(shù)據(jù)項(xiàng) 數(shù)據(jù)項(xiàng)別名 數(shù)據(jù)類型 數(shù)據(jù)項(xiàng)含義 1 開課學(xué)期 semester Char(15) 主屬性 2 學(xué)院 academy Char(15) 3 班級(jí) class Char(15) 主屬性 4 教師名 Tname char(10) 5 教師編號(hào) Tno Smallint(2) 主屬性 6 課程 course Char(15) 7 地點(diǎn) address Char(20) 主屬性 8 周數(shù) weekSum Smallint(2) 9 時(shí)間 time Char(15) 主屬性 數(shù)據(jù)庫的物理設(shè)計(jì) 數(shù)據(jù)庫的物理設(shè)計(jì) 這一環(huán)節(jié)也是很重要的，它要綜合考慮 存取時(shí)間、存儲(chǔ)空間利用率和維護(hù)代價(jià)三 方面的因素。消除冗余數(shù)據(jù)雖然能提高空間的利用率，但同時(shí)也會(huì)提高檢索的代價(jià)，因此，這三方面必須權(quán)衡，選擇一個(gè)折中方案。 18 自動(dòng)排課系統(tǒng)的設(shè)計(jì) 遺傳算法的 思想 在本課題中，遺傳算法解決的問題只是求出班級(jí) +課程 +教師 +時(shí)間的記錄集，得到比較優(yōu)的一個(gè)解，然后再去按條件用教室去填充這個(gè)記錄集，就形成了可行可用的課表。這塊的設(shè)計(jì)在整個(gè)系統(tǒng)是最重要的，效率的高低，課表的優(yōu)劣都由本模塊確定。 整個(gè)系統(tǒng)的流程分為以下幾個(gè)主要的過程 : (1)初始種群的產(chǎn)生 :首先基因的編碼，根據(jù)制定的編碼方案，對(duì)每條染色體進(jìn) 行初始化，其次一條條染色體組成一個(gè)個(gè)體，既是 形成 一個(gè) 二維表 （可稱為課表，但是適應(yīng)度值不高） 。 (1)沖突檢測和消除 :初始化種群后，先 對(duì) 其進(jìn)行 各類沖突 的 檢測，如存在沖突則消除它 ，而且在每次產(chǎn)生下一代后都要進(jìn)行沖突檢測 。 (2)計(jì)算 出每個(gè)個(gè)體的 適應(yīng)度函數(shù)值 ，以進(jìn)行優(yōu)勝劣汰 。 (3)遺傳操作 :包括選擇 算子 、交叉 算子 和變異 算子，產(chǎn)生子代，逐漸優(yōu)化。 (4)迭代第四步，直到進(jìn)化停止，就是 generation=終止代數(shù) N。 (5)班級(jí) +課程 +教師 +時(shí)間的記錄集的產(chǎn)生。 圖 44 遺傳算法流程圖 19 Chart 44 geic algorithm flow chart 構(gòu)建基因編碼和染色體 實(shí)施遺傳算法的第 1 步，就是把與求解目標(biāo)相關(guān)的實(shí)際參數(shù)進(jìn)行基因編碼，這是算法的關(guān)鍵與難點(diǎn)。 (1) 混合式編碼 構(gòu)造合適的基因結(jié)構(gòu) 是 遺傳算法能否順利實(shí)現(xiàn)的關(guān)鍵 ， 設(shè)定混合式的教師編碼作為本系統(tǒng)遺傳算法的“基因”。二進(jìn)制基因構(gòu)成規(guī)則為 :是否固定 *教師編號(hào)號(hào) *課程編號(hào) *課程性質(zhì)分別對(duì)應(yīng)的寬為 1+15+16+16 共 6B。下面我們給了很清晰的解釋： 圖 45 編碼結(jié)構(gòu)圖 Chart 45 coding structure chart 下面我們對(duì)每個(gè)字段給予解釋： 有些教師的課程是固定在某個(gè)時(shí)間段的，所以在排課過程中，判斷第一位就可以得知可否移動(dòng)此基因片。這也反應(yīng)了排課要人性化，畢竟有些教師有特殊的要求，例如，年齡、事物等等。 我們給了 15bit去表示教師 ， 15bit能表示 215個(gè)數(shù)，足矣滿足任何一所高校的教師編號(hào)，所以，在數(shù)據(jù)庫里，教師表里教師編號(hào)的數(shù)據(jù)項(xiàng)要為短整型。 唯一確定一門課程， 216個(gè)數(shù)，也足以表示一個(gè)學(xué)校的課程。 20 為了解決“特定資源”沖突問題，可在 教師編碼中加上 2B 表示該教師所