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

黃新葉　蔣高峰

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

關鍵詞：排課；排課管理；遺傳算法

中圖分類號：G647 文獻標志碼：A 文章編號：1674-9324（2016）15-0011-02

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

（一）背景與意義

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

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

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

二、理論意義及實用價值

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

三、目標、研究內容和研究方法

（一）工作目標與任務

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

（二）研究內容和研究方法

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

四、關鍵技術問題

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

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

（二）擬解決的關鍵問題

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

五、可行性論證

（一）目標可行性論證

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

（二）技術可行性論證

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

（三）成本可行性論證

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

（四）社會可行性論證

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

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

參考文獻：

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

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

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