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