【正文】 8 節(jié)課 4:205:50。 這樣，每周 5天涉及 25個時間 片。 則排課問題類似于填充 5 5的周時間片安排表。全校有 N 個教學(xué)班級，則周課表為 :以 25 個時間片為列，形成一維的時間序列，每個班級為行組成的一個二維數(shù)據(jù) 7 表。 教師和課程問題 每個課程都有自己的編號、名稱以及開課學(xué)院。每門課程都有指定 的教室類型。每門課程都有授課計劃，包括起始周和截止周以及周學(xué)時安排。 (2)“一師多班”沖突問題 :一位教師可能只給一個班講課，也可能同時給多個班級講課，也就是說同一教師可以在多個班出現(xiàn)，這樣可能會出現(xiàn) 同一時間，同一教師在多個班級上課的沖突，在編排課程表時此類沖突必須解決。 (4)“固定課”問題 :有的教師因為某些原因需要安排特定的教學(xué)時一段，如教室受到其他課程的影響，或者某學(xué)院部門領(lǐng)導(dǎo)，因工作性質(zhì)關(guān)系，須指定安排上課時間為“星期五的第 6節(jié)”，這樣的要求在編排課程表時必須滿足，即“固定時段”問題。 教室的問題 如今的大學(xué)都有很多的教學(xué)樓，校園面積也很大，宿舍與教學(xué)樓，教學(xué)樓與教學(xué)樓之間的距離可能會比較大，如果安排不佳的話，會導(dǎo)致學(xué)生上課時要跑動很遠距離，浪費不必要的時間。至于如何去確定一個教室，例如 50122，就表示 5 教學(xué)樓， 1 樓 22號教室。當(dāng)上課的人數(shù)遠遠小于教室容量時，這種情況也往往不合適的。這一模塊由學(xué)院排課工作人員來設(shè)置，如設(shè)置學(xué)年學(xué)期就是設(shè)置即將排課的學(xué)年學(xué)期，合并本學(xué)院的兩個班級組成一個新班一塊上一門公共課，設(shè)置一門課程則為上課周數(shù)、每周上課節(jié)次、有哪位老師講授等等信息 。 另一個功能，學(xué)院在這塊可以查詢本學(xué)院的課表，還有學(xué)院內(nèi)班級的課表。 自動排課模塊 這一模塊主要完成課程上課時間、上課地點的安排。然后，對這個（班級，教師，課程，時間）記錄做變換，讓位置表去填充它，當(dāng)然是按條件填充，就可以完成整個排課的大部分工作了，從而得到課 表。在本文約束條件主要為避免沖突，所謂沖突，它所包含的內(nèi)容很廣泛，幾乎發(fā)生在所有兩個或多個排課涉及因素之間。只有在滿足全部約束條件和避免所有沖突的基礎(chǔ)上，才能保證整個教學(xué)計劃合理正常進行。 在本文中，我們把排課過程中的約束條件分為三類 :基本硬約束、硬約束和軟約束。所以，可知在三類約束條件之中，前兩者是衡量排課方案是否切實可行的基本標準，軟約束是衡量排課方案是否人性化的標準，通常判別一個排課方案的優(yōu)劣標準有多個。 表 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)的一個解，然后再去按條件用教室去填充這個記錄集，就形成了可行可用的課 11 表。 整個系統(tǒng)的流程分為以下幾個主要的過程 : (1)初始種群的產(chǎn)生 :首先基因的編碼，根據(jù)制定的編碼方案，對每條染色體進行初始化，其次一條條染色體組成一個個體，既是形成一個二維表（可稱為課表，但是適應(yīng)度值不高）。 (2)計算出每個個體的適應(yīng)度函數(shù)值，以進行優(yōu)勝劣汰。 (4)迭代第四步，直到進化停止，就是 generation=終止代數(shù) N。 圖 3 遺傳算法流程圖 實施遺傳算法的第 1 步，就是把與求解目標相關(guān)的實際參數(shù)進行基因編碼，這是算法的關(guān)鍵與難點。二進制基因構(gòu)成規(guī)則為 :是否固定 *教師編號號 *課程編號 *課程性質(zhì)分別對應(yīng)的寬為 1+15+16+16 共 6B。這也反應(yīng)了排課要人性化，畢竟有些教師有特殊的要求，例如，年齡、事物等等。 唯一確定一門課程， 216個數(shù)，也足以表示一個學(xué)校的課程。每一門課程都有其各自不同的特點，比如上機課需要在機房上課，英語口語需要在語音室上課，體育課需要在操場上課，為此我們規(guī)定：把 16bits分開，前后8bits 各有不同的意思； 13 圖 5 比特信息圖 在此我們把課程分為專業(yè)必修課，專選科，公共課，上機實驗課，專業(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)此教師固定在這個時間片上課時，所在的時間片值。上 2學(xué)時課時，該教師編碼只能出現(xiàn) 1次，上 4 學(xué)時課時該教師編碼出現(xiàn) 2次，依次類推。功能室 (實驗室機房、語音室等 )已經(jīng) 在編碼時分配好，而理論課的那些，要等到后面再去分配。其中 BJS 為參與課表編排的班級總數(shù)； 14 d.“種群” —— 由 ZQS 個個體構(gòu)成。 初始化種群 每一個“染色體”都是班級的一個課表，是開課任務(wù)書中的一個班級所有記錄組成的 ，形成的是班級 +教室 +課程 +時間一條記錄。首先把固定教學(xué)時間的教師編碼填入該行中，然后使用隨機函數(shù)產(chǎn)生一個 1— 25 的數(shù)，將該班的其它教師編碼填入其中。這樣就有了一條染色體 (一個初始的班課程表 )。于是，一個初始個體便產(chǎn)生了。很明顯，由上述方式產(chǎn)生的個體通常含有大量的沖突。對于數(shù)據(jù)庫中教學(xué)樓，教室，班級等一些數(shù)量都未知的數(shù)據(jù)進行存儲，運用數(shù)組顯然不能解決，會出現(xiàn)很多的冗余，浪費內(nèi)存，并且處理繁瑣。本文的數(shù)據(jù)庫設(shè)計及其實現(xiàn)如下： 概念模型設(shè)計 因為概念結(jié)構(gòu)是面向現(xiàn)實世界的，用戶容易理解，能夠參加設(shè)計討論，提出意見，在將分析結(jié)果抽象為邏輯數(shù)據(jù)庫時可以降低設(shè)計的難度。對于排課問題要進行的分析主要有 :教學(xué)計劃、各學(xué)院教學(xué)任務(wù)、教室基礎(chǔ)數(shù)據(jù)、時間模式、開 課任務(wù)、及各種課表等數(shù)據(jù)。具體來說創(chuàng)建了以下各表 : 表 41 用戶表 :User Table 41 user table:User 編號 數(shù)據(jù)項 數(shù)據(jù)項別名 數(shù)據(jù)類型 數(shù)據(jù)項含義 1 用戶名 username Char(12) 唯一 2 密碼 passwd Char(20) 3 學(xué)院 academy Char(20) 學(xué)院名，如果空的話就 17 是代表教務(wù)處 表 42 教學(xué)計劃表 :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 學(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 編號 數(shù)據(jù)項 數(shù)據(jù)項別名 數(shù)據(jù)類型 數(shù)據(jù)項含義 1 教學(xué)樓 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ū)別三類教室 2 教室名 roomname Char(15) 18 3 教室編號 roomID smallint 4 班級 class Char(15) 加上班級就可以確定班級上課的位置范圍 5 學(xué)院 academy Char(15) 表 45 理論課教室表： LLKAddress Table 45 the classroom table of theory course： LLKAddress 編號 數(shù)據(jù)項 數(shù)據(jù)項別名 數(shù)據(jù)類型 數(shù)據(jù)項含義 1 學(xué)院 Academy Char(20) 2 班級 class Char(15) 3 教學(xué)樓 Tbuilding Char(10) 表 46 學(xué)院表： Academy Table 46 academy table： Academy 編號 數(shù)據(jù)項 數(shù)據(jù)項別名 數(shù)據(jù)類型 數(shù)據(jù)項含義 1 學(xué)院 academy Char(20) 2 學(xué)院編號 academyID Char(10) 主鍵 表 47 專業(yè)實驗課位置表： ZYSYRoom Table 47 the lab classroom place： ZYSYRoom 編號 數(shù)據(jù)項 數(shù)據(jù)項別名 數(shù)據(jù)類型 數(shù)據(jù)項含義 1 學(xué)院 academy Char(20) 2 教室名 roomname Char(15) 3 教室編號 roomID smallint 4 班級 class Char(15) 5 容納人數(shù) containSum smallint 表 48 位置表： Address Table 48 place table： Address 19 編號 數(shù)據(jù)項 數(shù)據(jù)項別名 數(shù)據(jù)類型 數(shù)據(jù)項含義 1 學(xué)院 academy Char(15) 唯一 2 教學(xué)樓 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 學(xué)院 academy char(15) 4 年齡 Tage Smallint 正整數(shù) 5 職稱 Title char(10) 表 411 開課任務(wù)表： ClassTask Table 411 the plan table： ClassTask 編號 數(shù)據(jù)項 數(shù)據(jù)項別名 數(shù)據(jù)類型 數(shù)據(jù)項含義 1 開課學(xué)期 semester Char(15) 主屬性 2 學(xué)院 academy Char(15) 3 班級 class Char(15) 主屬性 4 教師名 Tname char(10) 20 5 教師編號 Tno Smallint 主屬性 6 課程編號 courseNo Smallint 7 人數(shù) Pno smallint 8 課程 course smallint