排課系統的設計與實現畢業設計(論文)(編輯修改稿)

　

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