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