【正文】 wodimensional coding and the classroom filled method, simplifying the chromosome information and greatly shortening the syetem operation time. In addition, in the system design, we use the programming method of container based on container , realizing the convenient and fast processing of uncertain quantity data. Key word: Geic Algorithm。 Timetabling。 Classroom Arrangement。 1 隨著高校招生逐年擴張，大學課程向著廣度和深度發(fā)展，高校的教師、教室等一些資源越發(fā)顯得緊張，不管是在時間還是效率方面，用人工排課已不能夠解決現有的問題。排課是高校日常教學工作和其他活動的基礎，是教師和學生正?？茖W工作學習的依據。所以計算法自動排課已成為一個重要的研究課題 [1]。 國內學者在自動排課系統(tǒng)方面曾做過一些研究，如用到到退火算法、回溯算法、遺傳算法，但運行結果尚有 待改進的地方，排課效果不盡人意 [5]。我們認為，問題不盡在數學建模上，還與問題的處理方式有關。將遺傳算法應用于排課問題中，首先，初始化課表種群，其次，檢測初試種群中的沖突，然后，對種群做選擇，雜交，突變操作，一直迭代到具體指定的代數，最后就會得到較優(yōu)解。文 [1]中提到編碼時染色體上基因片存儲信息大小為 11 字節(jié)，而本文的編碼方式一個基因片只用了 6 字節(jié)，輕裝運行，經試驗得出，速度更快。還有 ,文 [1]介紹把教室與時間等信息共同處理的思路，這可能會產生空間上的沖突，而本文提出將教室分離出以單獨處理，就完全解決了空間 上的沖突問題。 本文根據高校開課的具體情況，采用優(yōu)化的編碼方案，滿足排課過程中的一些硬性和軟性約束因素，利用遺傳算法對課表進行了優(yōu)化，從而得到了最終的無沖突、更人性的排課方案。 2 分析 排課工作是一項十分繁重而復雜的工作，就以一般高校而言，它涉及到幾千多門課程進行合理的組織安排，而所使用的教室資源卻在學生規(guī)模每年都在增加的趨勢下越發(fā)顯得緊張了。排課的整個過程中充滿了矛盾運動，其中包括上課班級、所開課程、任課教師、上課時間、上課地點這 5 個方面在排列組合中發(fā)生的沖突和矛盾現象。課 程門類多、班級多、教師少、教室少 、教師連續(xù)上課的要求、班級連續(xù)上課的時間合理安排 是排課時發(fā)生沖突和矛盾的主要因素，而班級多、教室少則是矛盾的重要方面。課程表則是解決這些矛盾的舞臺，是提高教學管理水平、組織師生進行有序教學的規(guī)范之一，對有效地提高教育教學質量有重要作用。如果課程表編排得不合理、不科學，將影響課堂教學的效率和教學的整體效果。要想編排好學校的課程表，需要綜合考慮學校的教師、教室、學生、班級、時間等多方面因素，反復調整，避免沖突 。 分析一般高校的排課流程，其過程將如下， 下面將排課整個流程作個介紹 : (1)各學院從教學計劃中導入開課任務書，讓各學院安排好教師及教師的各種相關要求，比如班級、教室類型、時間類型等。同時做好教學樓、教室和時間基礎數據的輸 入 （已存在數據庫中）。這一時間段主要做好班級、課程、教師的協(xié)調。 (2)把各 個 學院開課任務書集合為學校開課任務書， 同時 規(guī)劃好學院上課所在的教學樓形成位置表，以減少 學生的 跑動范圍。 (3)系統(tǒng) 會 根據校開課任務書自動排課。這一過程主要完成班級、課程、教師及上課時間的安排。 (4)把上一步排出的結果 與 位置表結合，就完成了課表的安排 ，中間整個過程都要解決沖突問題。 (5)課表確定后，進行課表的查詢。 3 圖 21 排課流程圖 Chart 21 timetabling flow chart 數據需求分析 排課涉及的相關數據主要包括 :時間、班級、課程、教室 （空間） 、教師等 5 個要素。開始算法設計的基礎 是 對這些數據之間的問題的透徹分析和適當的處理。 時間問題 在本文中 考慮的是周課表， 通過 對全國部分高校做的調查， 綜合 分析了其中大部分高校的教學特點， 我們在此做出了一個較大眾化的且較合理的時間劃分模式 。設定周一至周五，共五天 上課 ，一天有十節(jié)課，上課方式都為 一 大節(jié)包括 2 個相鄰的小節(jié)，不能在上、下午之間跨時段。把每天用于上課的時間劃分為 5 個 時間片，根據學院開課的實際情況，一般每學時是 45 分鐘，為 1 小節(jié)課，每 2 小節(jié)課合為一大節(jié)課，故把每 2 小節(jié)課時間定為一個時間片，一天劃分為 5個時間片 : 4 (1)上午 1, 2 節(jié)課 8:109:50。 (2)上午 3, 4 節(jié)課 10:1011:50。 (3)下午 5, 6 節(jié)課 2: 304:10。 (4)下午 7, 8 節(jié)課 4:205:50。 (5)晚上 9, 10 節(jié)課 7:309:10。 這樣，每周 5天涉及 25 個時間片。用 Tl, T2,......,T25 表示，其中 TI, T2, T3, T4, T5 為星期一的 5個時間片，依次類推。 則排課問題類似于填充 5 5 的周時間片 安排 表。 表 21周時間片分布表 Table21 the management table of the week time slip 周一 周二 周三 周四 周五 T1 T6 T11 T16 T21 T2 T7 T12 T17 T22 T3 T8 T13 T18 T23 T4 T9 T14 T19 T24 T5 T10 T15 T20 T25 根據時間片編號，可進一步轉化為 1 25 的表格。全校有 N 個教學班級，則周課表為 :以 25 個時間片為列， 形成一維的時間序列， 每個班級為行組成的一個二維數據表。我們在此系統(tǒng)的排課都是按 一個大節(jié) 開設的，符合按 25 個時間片劃分的設計，但確有少量的課程的周學時數為單數，如“ 3 學時”或“ 5 學時”， 在此 仍按“ 4 學時”或“ 6 學時”進行編排，雖然這會浪費一小節(jié)課程 。 教師和課程問題 每個課程都有自己的編號、名稱以及開課學院 。每個課程 都要有授課 教師。每門課程都有指定的教室類型。如普通教室、語音室、 操場、 實驗室或機房等等。每門課程都有授課計劃，包括起始周和截止周以及周學時安排。在處理課程與教師時要注意以下幾個問題 : (1)“ 授一班多門課 ”問題 :同一教師可以只上一門課，也可上多門課，如果同一教師在同一個班級教授多門課程，那么把課程和教師作同一變量考慮就會引起課程的混亂，此問題 5 須分情況解決 ， 我們將在系統(tǒng)設計中，學院安排開課任務時解決 此問題 。 (2)“一師多班”沖突問題 :一位教師可能只給一個班講課，也可能同時給多個班級講課，也就是 說同一教師可以在多個班出現，這樣可能會出現同一時間，同一教師在多個班級上課的沖突，在編排課程表時此類沖突必須解決。 (3)“多學時”問題 :對于 有些 課程既可能只上一次， 既 2 學時課程，而有些課程 可能上多次，如 4 學時、 6 學時等，多學時的課程如何處理也是在編排課程表時必須解決的問題 。 (4)“固定課”問題 :有的教師因為某些原因需要安排特定的教學時一段，如 教室受到其他課程的影響，或者 某學院部門領導，因工作性質關系，須指定安排上課時間為“星期五的第 6節(jié)”，這樣的要求在編排課程表時必須滿足，即“ 固定 時段”問題。 (5)“特殊課”問題：像體育課，要跟硬件設施有關，故要妥善處理。 教室的問題 如今的大學都有很多的教學樓，校園面積也很大，宿舍與教學樓，教學樓與教學樓之間的距離可能會比較大，如果安排不佳的話，會導致學生上課時要跑動很遠距離，浪費不必要的時間。 本文在地理位置上 是學校統(tǒng)一規(guī)劃，進而綜合解決位置問題，學校要規(guī)劃好各個學院的學生在哪些教學樓里就近上課，而這樣做的 目的 就 是為了減少學生和教師的走動范圍。至于如何去確定一個教室，例如 50122，就表示 5教學樓， 1 樓 22 號教室。 每個教室在同一時間內只能接納一門課 程的授課，并且教室容量應該大于等于上課的人數。當上課的人數遠遠小于教室容量時，這種情況也 往往 不合適的。 根據業(yè)務分析和數據分析，可得出排課系統(tǒng)主要完成以下幾個功能 : 院管理模塊 這一模塊首先是每個學院從教學計劃中安排自己學院的開課任務書，具體就是對本學院課程和教師的安排。這一模塊由學院排課工作人員來設置，如設置學年學期就是設置即將排課的學年學期，合并本學院的兩個班級組成一個新班一塊上一門公共課，設置一門課程則為 6 上課周數、每周上課節(jié)次、有哪位老師講授等等信息 。 這個模塊很 好的解決了每個學院不同的特殊情況，以教師為重點，學院可以隨意調整。 另一個功能，學院在這塊可以查詢本學院的課表，還有學院內班級的課表。還有對已排好的課程做一些調整操作。 校管理模塊 這一模塊則主要是由教務處管理人員來操作。因為把每個學院的開課任務書聚合成校開課任務書，然后學院在規(guī)劃每個學院在哪個教學樓上課，以合理的安排地理上問題，形成一個學院上課地理位置表。 自動排課模塊 這一模塊主要完成課程上課時間、上課地點的安排。它的實現運用了遺傳算法中的選擇、交叉、變異等操作，對算法得 出的結果中最好的一個個體保留，就是要求的結果，雖然不是最完美符合的，但是它的適應度值已經完全可以符合學校教學所要求的了。然后，對這個（班級，教師，課程，時間）記錄做變換，讓位置表去填充它，當然是按條件填充，就可以完成整個排課的大部分工作了，從而得到課表。 此圖描述了功能模塊圖，如圖 22 示： 7 圖 22 功能模塊圖 Chart 22 the function model chart 排課是將教師與學生在時間和空間上根據不同的約束條件進行排列組合， 在此同時也要安 排課程， 以使教學正常進行。 在本文 約束條件主要為避免沖突，所謂沖突，它所包含的內容很廣泛，幾乎發(fā)生在所有兩個或多個排課涉及因素之間。避免沖突也是排課問題中要解決的核心問題。只有在滿足全部約束條件和避免所有沖突的基礎上，才能保證整個教學計劃合理正常進行。而對教師、教室、學生及時間等幾部分資源進行最優(yōu)化組合配置，才能保證充分發(fā)揮各資源的優(yōu)勢和提高教學質量。 在本文中， 我們把排課過程中的約束條件分為三類 :基本硬約束、硬約束和軟約束。其中基本硬約束是指教師、學生和教室在時空概念上發(fā)生了不可能發(fā)生的事情， 既是時間，空間 ，人之間的矛盾， 它是排課過程中最基本的約束條件，也是眾多排課模型中都 要 涉及的約束條件 ； 硬約束是 根據 學校的實際情況，排課時必須遵循的原則，否則將會導致排課結果無意義 ， 8 所以要因地制宜； 軟約束是指排課過程中滿足更佳但不滿足又無妨的約束條件， 這些條件的目的就是使課表更加人性化，每個排課都是要突出解決軟約束這個問題的，違背這些約束就與實際情況相悖 。 所以，可知 在三類約束條件之中，前兩者是衡量排課方案是否切實可行的基本 標準，軟約束是衡量排課方案 是否人性化 的標準，通常判別一個排課方案的優(yōu)劣標準有多個。 可以把排課過程常見的 約束條件分類羅列如下表 22 所示，這些約束條件 也比較符合排課過程的實際情況。 表 22 約束表 Table 22 constraint table 基本硬約束 B1 同一時間，同一班級不能上兩門不同的課程 B2 同一時間，同一個教師不能上兩門不同的課程 B3 同一個時間，同一個教室不能上兩門不同的課程 硬約束 H1 課程的學時 在每周要均勻化 H2 滿足每門課的特定教學資源 H3 教室足夠大，能夠容納學生 H4 某些課程要 特定 安排 ，如 某些教師的課程要固定 H5 教師學生上課不能用于在路途 上的奔波 H6 體育課盡量安排在下午 軟約束 S1 課程的分布要做到離散化 S2 一周有些時段處于最佳利于學習時間 S3 盡量不讓老師連著上課 S4 班級相鄰上課地點盡量近些 9 模型 問題陳述 設課程集合： L={l1， l2， ..... lA}；班級集合： C = {c1， c2， .......， cB}；教室集合： R = {r1， r2， .....， rQ}；教師集合： S={s1， s2， ......， sK}；時間集合：T={t1， t2， ......tD}[2]、 [4]。 首先初始化 種群，即編碼，編碼時形成班級集合、課程集合與教師集合形成課程教師對L_S={（ c1， l1， s2），（ c2， l3， s8） ......（ cB， la， sK） }，然后再在時間集合上排序形成時間上無沖突的一個班級 課程 時間 教師對集合 A={（ cb， lr， ti， sp）， ......，（ cB， lR