基于遺傳算法的排課管理平臺的設(shè)計(jì)與實(shí)現(xiàn)

黃新葉　蔣高峰

摘要：本文意在編寫一套適用于江蘇信息學(xué)院的自動排課系統(tǒng)，通過校園網(wǎng)構(gòu)建一個(gè)交流平臺來連接教師、學(xué)生和教學(xué)管理部門。利用并結(jié)合J2EE技術(shù)、Struts技術(shù)、MVC結(jié)構(gòu)設(shè)計(jì)、SOA技術(shù)實(shí)現(xiàn)B/S結(jié)構(gòu)的數(shù)據(jù)信息管理目標(biāo)；通過對排課算法進(jìn)行算法分析與算法設(shè)計(jì)，建立基于遺傳算法的排課數(shù)學(xué)模型。同時(shí)利用算法中的各項(xiàng)約束條件和混合編碼方法簡化排課過程中存在的問題。

關(guān)鍵詞：排課；排課管理；遺傳算法

中圖分類號：G647 文獻(xiàn)標(biāo)志碼：A 文章編號：1674-9324（2016）15-0011-02

一、國內(nèi)外研究動態(tài)

（一）背景與意義

排課管理作為教育教學(xué)中的重要環(huán)節(jié)，其目的是為教師、學(xué)生安排合適的教學(xué)地點(diǎn)與時(shí)間。排課管理是教學(xué)管理中一項(xiàng)復(fù)雜的工作，只有合理安排好了課程時(shí)間與地點(diǎn)，才能保障教學(xué)工作的有序進(jìn)行[1]。關(guān)于教學(xué)排課管理研究已經(jīng)有近四十多年之久，在理論以及實(shí)際應(yīng)用中都取得了豐碩的成果。然而，現(xiàn)有教學(xué)排課管理在面對復(fù)雜教學(xué)排課環(huán)境及大規(guī)模教學(xué)排課管理時(shí)存在的問題至今尚未完全解決，特別是隨著各大高校學(xué)生的大力擴(kuò)招，給教學(xué)排課管理帶來了巨大的壓力。在國內(nèi)，目前教學(xué)排課管理采用系統(tǒng)自動排課與人工排課的方式[2]，系統(tǒng)首先進(jìn)行自動排課，然后找出存在沖突的課程進(jìn)行人工調(diào)整，并根據(jù)經(jīng)驗(yàn)判斷將課程安排到合理的位置。由于人工調(diào)整缺乏理論指導(dǎo)與數(shù)據(jù)模型，使教學(xué)排課管理具有一定的盲目性，因此需要利用計(jì)算機(jī)技術(shù)與合適的排課算法解決人工干預(yù)的問題，這對于推動教學(xué)的發(fā)展也起到了非常重要的作用[3]。排課管理通過將各個(gè)年級開設(shè)的課程匯總，然后根據(jù)學(xué)校全年教學(xué)計(jì)劃任務(wù)和教學(xué)資源定制各個(gè)年級課程表，從而達(dá)到優(yōu)化教學(xué)資源的目的，通過設(shè)計(jì)一個(gè)有效的智能排課系統(tǒng)，減輕教學(xué)管理工作者的勞動強(qiáng)度，提高教學(xué)工作效率，為規(guī)范教學(xué)管理工作流程提供技術(shù)支持，從而保障學(xué)校的正常教學(xué)秩序。排課管理是非常復(fù)雜而煩瑣的管理過程，在學(xué)校規(guī)模大、約束（條件）復(fù)雜以及規(guī)律不斷變化的環(huán)境下，目前許多排課軟件與排課算法無法滿足實(shí)際需求，為滿足學(xué)校排課需求及師生對教學(xué)資源利用的要求，規(guī)避資源限制等約束條件，本研究對江蘇信息學(xué)院排課管理進(jìn)行了研究分析以滿足學(xué)院實(shí)際排課需求。

（二）國內(nèi)外研究現(xiàn)狀和發(fā)展態(tài)勢

排課問題是教育界非常關(guān)心的問題，對于排課問題研究主要集中在理論、啟發(fā)式搜索技術(shù)應(yīng)用求解、系統(tǒng)求解設(shè)計(jì)、遺傳算法應(yīng)用求解上。在國外，排課算法起源于20世紀(jì)50年代，1963年Gotlieb提出“排課算法數(shù)學(xué)模型”這一概念，標(biāo)志著排課算法研究進(jìn)入了科學(xué)的殿堂。自此以后，許多學(xué)者也參與到了排課算法研究中，早期的大多數(shù)求解都存在諸多問題，無法完全應(yīng)用于實(shí)際生活中，如Ferland、吳金榮等人將排課問題化成整數(shù)規(guī)劃來求解，但這種方法計(jì)算量巨大，只能應(yīng)用到小數(shù)據(jù)量環(huán)境中，無法適用于實(shí)際應(yīng)用中。而何永太和胡順仁等人則采用圖論中的染色問題進(jìn)行排課研究，由于圖論的染色問題本身也是NP完全問題，其計(jì)算比較復(fù)雜，也只能應(yīng)用于特殊條件中，因此至今沒有一個(gè)切實(shí)可行的算法。到了20世紀(jì)90年代，國外對于排課算法研究非常活躍，提出了一種新的課表編排方法，它以“人”為單位，利用格朗日松弛法及分支定界技術(shù)進(jìn)行排課算法研究。而在我國，對于排課算法的研究卻要始于20世紀(jì)80年代，從模擬手工排課到運(yùn)用人工智能，逐步發(fā)展，取得了一定的成績。隨著人工智能的發(fā)展，開始在排課算法中引入了生物界進(jìn)化思想和遺傳算法，依靠其超強(qiáng)的并行搜索能力和在解決優(yōu)化問題中表現(xiàn)出來的優(yōu)勢，已經(jīng)被廣泛使用。特別是生物進(jìn)化思想和遺傳思想的出現(xiàn)，出現(xiàn)了基于遺傳算法來求解排課問題。本課題就是利用了基于遺傳算法進(jìn)行排課算法設(shè)計(jì)，并結(jié)合J2EE技術(shù)、Struts技術(shù)、MVC結(jié)構(gòu)設(shè)計(jì)、SOA技術(shù)實(shí)現(xiàn)系統(tǒng)開發(fā)設(shè)計(jì)。

二、理論意義及實(shí)用價(jià)值

隨著社會經(jīng)濟(jì)的發(fā)展，高校規(guī)模的擴(kuò)大增加了教學(xué)管理的難度及造成了教學(xué)資源的相對緊張，但顯然這些學(xué)校的師資、教學(xué)設(shè)備和其他教學(xué)資源都不能及時(shí)有效地進(jìn)行補(bǔ)充，所以無法適應(yīng)教學(xué)發(fā)展的需求，這其中排課問題就尤為突出。不僅在普通高校出現(xiàn)了以上問題，在高職院校也出現(xiàn)同樣的問題。江蘇信息職業(yè)技術(shù)學(xué)院經(jīng)過六十多年的艱苦創(chuàng)業(yè)，現(xiàn)有全日制在籍學(xué)生共一萬多人，學(xué)校形成了中高職銜接、職成教一體的辦學(xué)體系。目前采用的是2004年引進(jìn)學(xué)院的教務(wù)排課系統(tǒng)，經(jīng)過十年的運(yùn)營，技術(shù)已經(jīng)落后，不能很好地滿足日常教學(xué)工作的需要。本文也是基于這個(gè)原因，意在編寫一套適用于江蘇信息學(xué)院的自動排課系統(tǒng)。

三、目標(biāo)、研究內(nèi)容和研究方法

（一）工作目標(biāo)與任務(wù)

結(jié)合江蘇信息學(xué)院的現(xiàn)實(shí)，再造教務(wù)教學(xué)管理的管理流程，使它更加科學(xué)化、規(guī)范化。據(jù)此建立一套教學(xué)制管理制度，不但要適合江蘇信息學(xué)院的現(xiàn)實(shí)，還要完成選課排課的信息化與自動化。最后設(shè)計(jì)一個(gè)排課系統(tǒng)，與現(xiàn)有運(yùn)行的排課系統(tǒng)相比，該系統(tǒng)支持全學(xué)分制，這是它最明顯的優(yōu)點(diǎn)。它不僅能夠減少各級教學(xué)管理人員的工作量，方便檢索查詢與管理，還能夠形成先進(jìn)的教學(xué)理念和管理制度。

（二）研究內(nèi)容和研究方法

本文主要包括以下工作：重點(diǎn)分析、設(shè)計(jì)及研究排課管理系統(tǒng)。（1）對目前許多高校的教務(wù)管理流程進(jìn)行重點(diǎn)分析，找出手工排課的主要問題和編制課表的基本原則，分析排課需求。組織學(xué)生評價(jià)教師及他們所授的課程，最優(yōu)組合教師和課程，充分做好排課的相關(guān)準(zhǔn)備工作；（2）從多方面分析系統(tǒng)需求，主要包括系統(tǒng)開發(fā)背景、可行性論證、主要業(yè)務(wù)流程分析、系統(tǒng)功能需求分析、數(shù)據(jù)模型分析等，確定江蘇信息學(xué)院排課管理系統(tǒng)實(shí)現(xiàn)的必要性及可行性；（3）全面設(shè)計(jì)系統(tǒng)實(shí)現(xiàn)的各個(gè)功能模塊，確定本排課系統(tǒng)的主要內(nèi)容：其中包含系統(tǒng)管理、原始數(shù)據(jù)、教室管理、教學(xué)任務(wù)管理、排課管理、和課表管理等六大模塊。同時(shí)，詳細(xì)設(shè)計(jì)各個(gè)功能模塊；（4）利用J2EE技術(shù)、Struts技術(shù)、MVC結(jié)構(gòu)設(shè)計(jì)、SOA等技術(shù)進(jìn)行具體的程序開發(fā)。同時(shí)，在后臺數(shù)據(jù)庫方面，選擇SQL Server 2008作為管理系統(tǒng)；（5）關(guān)于算法研究方面，本排課系統(tǒng)完整討論了排課問題的主要影響要素、約束條件、以及排課系統(tǒng)中遺傳算法的設(shè)計(jì)及核心算法等問題。

四、關(guān)鍵技術(shù)問題

（一）創(chuàng)新之處

首先，對于排課問題的影響要素、主要約束條件、求解目標(biāo)和難點(diǎn)，本系統(tǒng)進(jìn)行了完整的討論，提出了排課問題求解方法的總體框架和技術(shù)路線；其次，根據(jù)江蘇信息學(xué)院的實(shí)際情況，從排課系統(tǒng)的需求分析開始，建立排課系統(tǒng)的數(shù)據(jù)模型及其體系結(jié)構(gòu)。給出排課系統(tǒng)中遺傳算法的設(shè)計(jì)，核心算法的實(shí)現(xiàn)方法和步驟；最后，說明本排課系統(tǒng)的總體設(shè)計(jì)方案、各模塊的功能結(jié)構(gòu)及相應(yīng)的實(shí)現(xiàn)方法。

（二）擬解決的關(guān)鍵問題

影響排課的因素很多，總結(jié)起來分為以下兩大類：一是參與教學(xué)活動的主體。主要是指教師、班級、課程，教學(xué)等主體對象因素，這些因素在每個(gè)學(xué)期都是可能變動的，是動態(tài)的。它們是需要給予分配資源的對象。而在排課過程中，這些主體對象必須在空間和時(shí)間上都保證獨(dú)立，而不是沖突的。在排課過程中，最主要的問題就是解決這些主體對象因素在空間和時(shí)間上的沖突；二是教學(xué)資源對象因素。主要指被分配的資源，如教室、教學(xué)時(shí)間等因素，這些資源往往都是有限的。并且教學(xué)資源都是分種類的，如教室有大教室、小教室之分，類型有多媒體教室、普通教室、語音室、實(shí)驗(yàn)室之分。其他因素還包括教學(xué)計(jì)劃的不同、教師個(gè)人的選擇喜好等。

五、可行性論證

（一）目標(biāo)可行性論證

通過校園網(wǎng)構(gòu)建一個(gè)交流平臺來連接教師、學(xué)生和教學(xué)管理部門，利用并結(jié)合J2EE技術(shù)、Struts技術(shù)、MVC結(jié)構(gòu)設(shè)計(jì)、SOA技術(shù)實(shí)現(xiàn)B/S結(jié)構(gòu)的數(shù)據(jù)信息管理目標(biāo)。

（二）技術(shù)可行性論證

軟件方面，本系統(tǒng)結(jié)合了物聯(lián)網(wǎng)技術(shù)，采用目前最常用的J2EE技術(shù)與SQL相結(jié)合的模式進(jìn)行開發(fā)，數(shù)據(jù)庫服務(wù)器選用Microsoft的SQL Server 2008作為數(shù)據(jù)庫，此數(shù)據(jù)庫能夠處理大量的數(shù)據(jù)，不僅能夠保持?jǐn)?shù)據(jù)的完整性，而且還能夠提供多項(xiàng)高級管理功能。由此可見，系統(tǒng)的軟件開發(fā)平臺條件已經(jīng)滿足。在硬件方面，江蘇信息學(xué)院計(jì)算機(jī)容量越來越大，可靠性越來越高，硬件平臺完全能夠滿足系統(tǒng)開發(fā)和系統(tǒng)運(yùn)行的需要。

（三）成本可行性論證

本系統(tǒng)只需花費(fèi)少量的經(jīng)費(fèi)，廣大教務(wù)管理人員就能從繁重的手工排課工作中解脫出來，他們可以把更多的精力投入到其他教學(xué)管理工作中，提高工作效率；同時(shí)也可以使廣大師生通過校園網(wǎng)查詢到相關(guān)的個(gè)人教學(xué)信息，此方式成本低，既方便又經(jīng)濟(jì)。

（四）社會可行性論證

目前，江蘇信息學(xué)院校園網(wǎng)絡(luò)已經(jīng)覆蓋了整個(gè)教學(xué)區(qū)和學(xué)生區(qū)，學(xué)院各個(gè)教學(xué)部門、行政部門和廣大學(xué)生的上網(wǎng)需求都可以滿足。尤其是本學(xué)院已經(jīng)通過光纖接入的方式與Internet連接，能夠很好地實(shí)現(xiàn)校內(nèi)用戶之間以及校內(nèi)用戶與校外用戶之間的聯(lián)系。

綜上所述，面對江蘇信息學(xué)院教務(wù)信息處理需求的日益增長，開發(fā)一個(gè)教務(wù)排課管理系統(tǒng)來應(yīng)對這種需求，為學(xué)生和教學(xué)管理人員提供快捷方便的雙向選擇服務(wù)，提高排課管理工作的效率，是非常有必要的。

參考文獻(xiàn)：

[1]劉真.基于URP的地方高校數(shù)字校園建設(shè)應(yīng)用研究[D].山東大學(xué)碩士學(xué)位論文，2008.

[2]王慧.基于URP的校園信息公建設(shè)的研究[D].河海大學(xué)碩士學(xué)位論文，2006.

[3]錢晨.高校數(shù)字化校園統(tǒng)一身份認(rèn)證平臺設(shè)計(jì)[D].復(fù)旦大學(xué)碩士學(xué)位論文，2010.