基于遺傳算法的排課管理平臺的設計與實現

黃新葉　蔣高峰

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

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

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

一、國內外研究動態

（一）背景與意義

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

（二）國內外研究現狀和發展態勢

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

二、理論意義及實用價值

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

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

（一）工作目標與任務

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

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

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

四、關鍵技術問題

（一）創新之處

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

（二）擬解決的關鍵問題

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

五、可行性論證

（一）目標可行性論證

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

（二）技術可行性論證

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

（三）成本可行性論證

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

（四）社會可行性論證

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

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

參考文獻：

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

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

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