1  引言

        .1  開發(fā)背景

        近幾年來，隨著各高校辦公自動(dòng)化工作的推進(jìn)，教務(wù)管理自動(dòng)化也被擺上了日程。在教務(wù)工作中占有很大比重的一項(xiàng)就是每學(xué)期的課程表排定工作。由于教工、教室和設(shè)備的相對(duì)緊張，如何進(jìn)行合理地安排和分配，從而充分利用教學(xué)資源是我們不得不面對(duì)的問題。而人工進(jìn)行排課不僅任務(wù)重，效率低，而且易出錯(cuò)，難于維護(hù)，想要排出一張各方面都滿意的課表非常困難。并且隨著高校規(guī)模的擴(kuò)大手工排課的難度和工作量呈幾何級(jí)數(shù)增長(zhǎng)。

        隨著信息技術(shù)的飛速發(fā)展，各個(gè)行業(yè)的信息化勢(shì)在必行?？萍嫉倪M(jìn)步大大地提高了生產(chǎn)率。作為高校，如何才能提高辦學(xué)效率，更好地完成教學(xué)任務(wù)，跟上社會(huì)發(fā)展步伐，這是一個(gè)擺在教學(xué)工作者面前的一個(gè)迫切的問題。應(yīng)用信息化來改造傳統(tǒng)的教學(xué)管理模式是一個(gè)重要途徑  。

        在實(shí)際的應(yīng)用中，很多研究者都提出了各種解決排課問題的方法，由于排課問題的復(fù)雜性，還沒有找到有效的算法能獲得NP完全問題的最優(yōu)解。因此，如何運(yùn)用近似算法和新的軟件技術(shù)來降低排課問題的計(jì)算復(fù)雜度，仍然是頗具挑戰(zhàn)性的研究方向  。

        傳統(tǒng)的人工排課使用手工操作存在許多弊端，如重復(fù)勞動(dòng)嚴(yán)重、效率低下、且不能達(dá)到資源的最優(yōu)化配置等，將產(chǎn)生大量的文件和數(shù)據(jù)，這對(duì)于查找、更新和維護(hù)都帶來了不少的困難。最令人擔(dān)心的問題就是——出現(xiàn)教室資源沖突或教師資源沖突的情況，而且工作繁瑣，工作量巨大,尤其是在給大學(xué)校園進(jìn)行排課時(shí)出現(xiàn)的問題更多。當(dāng)前高校教務(wù)管理所涉及到的信息資料數(shù)量大、類型多，還可能帶有大量的統(tǒng)計(jì)輸出，同時(shí)學(xué)校規(guī)模的不斷擴(kuò)大和招生人數(shù)的逐年攀升導(dǎo)致傳統(tǒng)的排棵手段已無法滿足現(xiàn)代化管理的要求  。

        排課管理系統(tǒng)是利用數(shù)據(jù)庫管理系統(tǒng)開發(fā)的一種應(yīng)用系統(tǒng),其開發(fā)主要包括數(shù)據(jù)庫的建立，充分滿足正常的題庫管理的前提下，提供了多角度的題庫信息查詢和題庫信息分析報(bào)表，使學(xué)校管理人員可以隨時(shí)掌握學(xué)校的排課情況，進(jìn)一步指導(dǎo)學(xué)校的教學(xué)。真正實(shí)現(xiàn)了業(yè)務(wù)一體化，為學(xué)校全方位的信息化管理奠定了基礎(chǔ)。

        在教學(xué)計(jì)劃的不斷完善和各高校校園網(wǎng)建立的大背景下，設(shè)計(jì)滿足高校教務(wù)要

        求的排課系統(tǒng)顯得十分必要。而據(jù)了解，排課管理是高校教務(wù)處重復(fù)性比較強(qiáng)且急需得到解決的工作， 且排課系統(tǒng)有安全性要求高、交互性強(qiáng)、處理數(shù)據(jù)量大等人工難以實(shí)現(xiàn)的特點(diǎn)。

        因此設(shè)計(jì)一個(gè)基于校園網(wǎng)絡(luò)的人工智能化且操作簡(jiǎn)便的排課系統(tǒng)是高校教務(wù)管理信息系統(tǒng)實(shí)現(xiàn)的首要條件，同時(shí)也是一大難點(diǎn)，因?yàn)榕耪n管理要求綜合考慮教師、課程、班級(jí)、教室、時(shí)間等諸方面的因素，統(tǒng)籌兼顧，使課表既符合教學(xué)規(guī)律，又能夠充分利用現(xiàn)有資源使其最大限度地發(fā)揮作用  。

        .2  國(guó)內(nèi)外研究現(xiàn)狀

        在國(guó)內(nèi)，在20世紀(jì)80年代初期，國(guó)內(nèi)學(xué)者開始用從模擬手工排課，也有人工智能構(gòu)建的專家系統(tǒng)等等，具有代表性的有：南京工學(xué)院的UTSS(A University Timetable Seheduling System)系統(tǒng)，大連理工大學(xué)的智能教學(xué)組織管理與課程調(diào)度系統(tǒng)等。這些系統(tǒng)大都是模擬手工排課過程，以“班”為單位，運(yùn)用啟發(fā)式函數(shù)來進(jìn)行編排的。但是這些課表編排系統(tǒng)往往依賴于各個(gè)學(xué)校的教學(xué)體制，不宜于進(jìn)行大量推廣  。

        早在20世紀(jì)50年代末，國(guó)外就有人開始研究課表編排問題。1963年，Gotlieb曾提出一個(gè)課表問題的數(shù)學(xué)模型，但由于排課問題易受實(shí)際問題的影響，求解結(jié)果也不理想。20世紀(jì)70年代，美國(guó)人S.Even等就證明了排課問題是一個(gè)NP完全問題，其算法的時(shí)間復(fù)雜度呈指數(shù)增長(zhǎng)。S.Even的論證正式確立了排課問題的學(xué)術(shù)地位，把人們對(duì)排課問題的認(rèn)識(shí)提高到了理論高度  。此外，有些文獻(xiàn)試圖從圖論的角度來求解課表問題，但是圖的染色體問題也是NP完全問題，只有在極為簡(jiǎn)單的情況下才可以將課表編排轉(zhuǎn)化為二部圖匹配問題。

        .1  JSP簡(jiǎn)介

        應(yīng)用程序不同于其他語言開發(fā)的單一性程序。使用Jsp編程時(shí)，必須首先確定應(yīng)用程序如何與用戶交互，如鼠標(biāo)單擊，用戶必須編寫代碼控制這些事件的響應(yīng)方法。

        使用JSP開發(fā)數(shù)據(jù)庫應(yīng)用程序的一般步驟如下所示：

        （1） 建立數(shù)據(jù)庫

        （2） 建立用戶界面

        （3） 編寫代碼

        （4） 調(diào)試運(yùn)行

        （5） 編譯應(yīng)用程序

        （6） 發(fā)布應(yīng)用程序

        應(yīng)用程序的結(jié)構(gòu)：

        由于JSP應(yīng)用程序是基于對(duì)象的，所以應(yīng)用程序的代碼結(jié)構(gòu)就是該程序在屏幕上物理表示的模型。根據(jù)定義，對(duì)象包含數(shù)據(jù)和代碼。在屏幕上看到的窗體代表屬性，這些屬性定義了窗體的外觀和內(nèi)在特性。

        界面設(shè)計(jì)

        （1） 控件的位置

        （2） 界面元素的一致性

        （3） 保持界面的簡(jiǎn)明

        （4） 使用顏色和圖像：增加視覺的感染力

        （5） 圖像和圖標(biāo)：增加應(yīng)用程序的視覺上的趣味

        （6） 選取字體

        .2  SQL Server 2000簡(jiǎn)介

        本系統(tǒng)所用SQL Server 2000 的特性包括： 1.Internet 集成；2.企業(yè)級(jí)數(shù)據(jù)庫功能；3.易于安裝、部署和使用。同時(shí)本系統(tǒng)使用SQL Server 2000 個(gè)人版; 其特性為：

        (1)支持對(duì)稱多處理器結(jié)構(gòu)、存儲(chǔ)過程、ODBC，并具有自主的SQL語言。SQL Server以其內(nèi)置的數(shù)據(jù)復(fù)制功能、強(qiáng)大的管理工具、與Internet的緊密集成和開放的系統(tǒng)結(jié)構(gòu)為廣大的用戶、開發(fā)人員和系統(tǒng)集成商提供了一個(gè)出眾的數(shù)據(jù)庫平臺(tái)。

        (2)高性能設(shè)計(jì)，可充分利用Windows NT的優(yōu)勢(shì)。

        (3)強(qiáng)壯的事務(wù)處理功能，采用各種方法保證數(shù)據(jù)的完整性。

        (4)系統(tǒng)管理先進(jìn)，支持Windows圖形化管理工具，支持本地和遠(yuǎn)程的系統(tǒng)管理和配置。

        .3  Tomcat簡(jiǎn)介

        很受廣大程序員的喜歡，因?yàn)樗\(yùn)行時(shí)占用的系統(tǒng)資源小，擴(kuò)展性好，支持負(fù)載平衡與郵件服務(wù)等開發(fā)應(yīng)用系統(tǒng)常用的功能；而且它還在不斷的

        是一個(gè)小型的輕量級(jí)應(yīng)用服務(wù)器，在本系統(tǒng)中當(dāng)在一臺(tái)機(jī)器上配置好Apache 服務(wù)器，可利用它響應(yīng)對(duì)HTML 頁面的訪問請(qǐng)求。實(shí)際上Tomcat 部分是Apache 服務(wù)器的擴(kuò)展，但它是獨(dú)立運(yùn)行的，所以當(dāng)你運(yùn)行tomcat 時(shí)，它實(shí)際上作為一個(gè)與Apache 獨(dú)立的進(jìn)程單獨(dú)運(yùn)行的。

        當(dāng)配置正確時(shí)，Apache 為HTML頁面服務(wù)，而Tomcat 實(shí)際上運(yùn)行JSP 頁面和Servlet。另外，Tomcat具有處理HTML頁面的功能，同時(shí)它還是一個(gè)Servlet和JSP容器，獨(dú)立的Servlet容器是Tomcat的默認(rèn)模式。

        需求分析

        1 幫助系統(tǒng)維護(hù)可以實(shí)現(xiàn)：操作日志、重新登錄、打印設(shè)置（包括統(tǒng)計(jì)各種報(bào)表及打印等）、退出等操作。

        2 系統(tǒng)的主要功能

        3掌握學(xué)校所有的課程和教師的信息。包括每門課程的時(shí)間、班級(jí)以及任課老師的姓名等。

        4可以對(duì)一個(gè)或多個(gè)班級(jí)進(jìn)入課程管理與排課表管理，可以不限次的生成該班級(jí)課程表。

        5針對(duì)不同的人員授予不同的權(quán)限。提供靈活的瀏覽、查詢功能?？梢圆榭茨硞€(gè)系、某個(gè)班級(jí)所有課程的信息。

        可以對(duì)課程進(jìn)行變動(dòng)管理。既可以手工排課，又可以實(shí)現(xiàn)自動(dòng)排序功能。 

        提供一種或多種課程表輸出功能，并使用活動(dòng)的模板輸出功能，輸出樣式可以由用戶自定義。

        實(shí)現(xiàn)功能全面化，由于每個(gè)學(xué)?；虬嗉?jí)的每天課程數(shù)目或時(shí)間都不太一樣，實(shí)現(xiàn)智能計(jì)算總課程數(shù)目和管理對(duì)應(yīng)的時(shí)間段，并且根據(jù)每門課程的獨(dú)立分布式來進(jìn)行排列（例如：大學(xué)語文自動(dòng)排列的分布方式可以是周一至周六，那么系統(tǒng)就會(huì)自動(dòng)將其平均分布在周一至周六這些天里）。

        1用戶管理：設(shè)置兩個(gè)級(jí)別用戶：管理員和普通用戶，管理員有權(quán)限操作系統(tǒng)中的所有數(shù)據(jù)，普通用戶只能以執(zhí)行查詢，輸出之類的功能，無法對(duì)系統(tǒng)進(jìn)行實(shí)質(zhì)性的操作，用戶使用本系統(tǒng)之前必須先通過身份認(rèn)證（用戶級(jí)別、用戶名和密碼，密碼輸入有次數(shù)限制，連續(xù)三次輸入錯(cuò)誤密碼則鎖定該用戶）。

        .2 系統(tǒng)所需硬件環(huán)境

        （1）處理器：建議使用酷睿 2

        （2）內(nèi)存：1G以上

        .3  排課的約束條件

        在我的排課系統(tǒng)，主要對(duì)不同類型課程進(jìn)行等級(jí)劃分，排列出課程的排課優(yōu)先級(jí)別，通過優(yōu)先次序?qū)Σ煌愋偷恼n程使用不同的算法進(jìn)行排課，能夠非常方便地處理各種排課約束條件的限制。

        例如教師和教室沖突、班級(jí)沖突、教師上課時(shí)間和地點(diǎn)選擇、分層次教學(xué)、單雙周排課、一課多教師教學(xué)和課程連上等各種各樣的約束。同時(shí)該系統(tǒng)還能夠非常迅速地得到排課結(jié)果，例如排一千門課只需幾分鐘時(shí)間等一系列問題。

        .4  系統(tǒng)所需軟件平臺(tái)

        （1）操作系統(tǒng)：Windows XP

        （2）數(shù)據(jù)庫：Access 2003

        （3）Web 服務(wù)器 ：IIS 6.0

        （4）瀏覽器：IE 7.0，推薦使用360安全瀏覽器

        系統(tǒng)總體設(shè)計(jì)

        4.1  設(shè)計(jì)思想

        本系統(tǒng)采用各班級(jí)獨(dú)立劃分管理，所有教師均可為任何班級(jí)服務(wù)，各班級(jí)根據(jù)每天課程數(shù)目來進(jìn)行自動(dòng)排序，同時(shí)各教師允許教學(xué)多門課程，因此為了每名教師配置了時(shí)間占用表，只要與班級(jí)對(duì)應(yīng)的時(shí)間空間表未被占用，都可以參與排課，并根據(jù)用戶定義的要求排出課程。

        數(shù)據(jù)管理類：由于班級(jí)，時(shí)間，教師，課程等信息都需要一個(gè)活動(dòng)的管理過程，因?yàn)樵诠?jié)省資源的情況下，將各數(shù)據(jù)所需要的代碼合并在一起進(jìn)行編寫和使用。

        4.2  系統(tǒng)功能模塊劃分

        教務(wù)排課系統(tǒng)在功能上分四個(gè)模塊，如圖4.2：

        4.3  數(shù)據(jù)庫結(jié)構(gòu)的設(shè)計(jì)

        利用SQL Server2000來管理排課資源、排課約束條件等信息，利用數(shù)據(jù)庫技術(shù)來實(shí)現(xiàn)設(shè)置排課優(yōu)先級(jí)、課時(shí)和時(shí)間段的匹配以及處理排課資源的沖突，從而實(shí)現(xiàn)自動(dòng)排課的目的。

        主要包含的數(shù)據(jù)實(shí)體有：專業(yè)、課程、教師、教室、課程表等。實(shí)體的具體屬性如下：

        （1）專業(yè)信息包括：專業(yè)代碼、專業(yè)名稱；

        （2）課程信息包括：課程代碼、課程名稱、課程類型、總學(xué)時(shí)、每周課時(shí)、任課教師、開課院系、授課班級(jí)（專業(yè)）、上課人數(shù)、約束條件等信息；

        （3）教師信息包括：教師代碼、教師名稱、所屬院系、約束條件等；

        （4）教室信息包括：教室代碼、教室名稱、教室類型、教室地址、容納人數(shù)等；

        （5）課程表信息包括：課程代碼、專業(yè)代碼、教師代碼、教室代碼、上課時(shí)間等。

        系統(tǒng)詳細(xì)設(shè)計(jì)

        .2  主界面及課表生成設(shè)計(jì)

        .2.1  班級(jí)管理設(shè)計(jì)

        模塊設(shè)計(jì)說明：班級(jí)的操作部分是排課程序正常執(zhí)行的重要部分，班級(jí)的添加不允許有同名的班級(jí)出現(xiàn)，而修改也不能做到修改班級(jí)名，班級(jí)名稱將作為不可修改的數(shù)據(jù)部分，而刪除部分，在刪除之前必須保證該班級(jí)的課表是否已經(jīng)生成，如果是，則需要注銷課程表，這樣做是讓該班級(jí)生成的課表占用教師空間的部分全部返回，這樣不會(huì)使教師的空間被反復(fù)占用，而最終導(dǎo)致錯(cuò)誤發(fā)生。

        .1  登錄系統(tǒng)設(shè)計(jì)

        設(shè)計(jì)說明:進(jìn)入主界面后,等待操作用戶輸入用戶名和密碼,在輸入之后按確定進(jìn)入,驗(yàn)證用戶名和密碼,實(shí)現(xiàn)流程:

        (1) 檢測(cè)數(shù)據(jù)庫中有無管理員賬號(hào)，如果有,則等待用戶輸入用戶名和密碼,否則按程序本身自動(dòng)執(zhí)行插入命令,新建一個(gè)管理員用戶,并等待用戶輸入.

        (2) 驗(yàn)證用戶名和密碼是否正確,錯(cuò)誤次數(shù)不能超過三次,超過三次則退出系統(tǒng)登陸界面

        (3) 當(dāng)驗(yàn)證通過后,檢測(cè)該登陸用戶的管理權(quán)限,并設(shè)置變量傳值給主窗體

        .2.3  課表生成部分設(shè)計(jì)

        圖5.4 排課循環(huán)流程圖 模塊設(shè)計(jì)說明：此處將執(zhí)行的數(shù)據(jù)分成很多小部分來執(zhí)行，這樣做可以在測(cè)試中便如發(fā)現(xiàn)問題，因?yàn)榕耪n系統(tǒng)的要求非常高，所以在程序?qū)崿F(xiàn)方面是以由簡(jiǎn)到繁的過程。

        (1)排課中要求的每周課程數(shù)相加不能超出定義的課表范圍，否則也將會(huì)出現(xiàn)死循環(huán)。

        (2)列出對(duì)應(yīng)課程教師的未被占用的排課列表和班級(jí)的課程占用表。

        (3)窮舉法列出以上兩者之間的共通點(diǎn)，可用點(diǎn)。

        (4)最后通過循環(huán)隨機(jī)選擇來實(shí)現(xiàn)課程的定位與排列。

        (5)課程定位中不允許每天有相同的課程重復(fù)，并按規(guī)定來執(zhí)行按什么樣的格式來排列，例如兩節(jié)連排，也就是說可以把該課程在同一天排在一起，可以實(shí)現(xiàn)兩節(jié)課連上，這是大學(xué)課表里最常用的一個(gè)功能。

        5.2.2  班級(jí)課程處理設(shè)計(jì)

        模塊設(shè)計(jì)說明：課程數(shù)據(jù)的添加，修改或刪除都會(huì)影響到已生成課程表的返回，因?yàn)樵诓僮髦氨匾ＷC課程表屬于未生成狀態(tài)，如果當(dāng)前為生成狀態(tài)，則需要注銷課程表，這樣才可以繼續(xù)操作。

        注：已生成課程表的返回：由于課程表排列好后，對(duì)應(yīng)的課程后教師的排課占用表都會(huì)有標(biāo)記標(biāo)明，如果這時(shí)修改了某此數(shù)據(jù)后，這教師的占用表并沒有恢復(fù)到未生成狀態(tài)，這樣就會(huì)導(dǎo)致不可預(yù)知的錯(cuò)誤發(fā)生。

        5.2.4  報(bào)表輸出功能設(shè)計(jì)

        模塊設(shè)計(jì)說明：此處采用了兩種輸出方式，第一種是普通的報(bào)表方式輸出，可以實(shí)現(xiàn)一般的打印預(yù)覽等功能，第二種則是采用模板功能，用戶可以自由修改模板，前提是不可以更改數(shù)據(jù)位，其它的部分無論如何修改都沒有關(guān)系。

        .3  數(shù)據(jù)表設(shè)計(jì)

        在使用SQL server創(chuàng)建“排課管理系統(tǒng)”數(shù)據(jù)庫系統(tǒng)中需要建立的數(shù)據(jù)表如下所示:

        課程信息

        表5.1 課程信息表

        2 用戶登錄

        3 課程名

        5 課程占用表

        系統(tǒng)日志

        7 系統(tǒng)設(shè)定

        5.4  其它模塊設(shè)計(jì)

        此處幾個(gè)模塊是經(jīng)過資源優(yōu)化將其與班級(jí)管理整合在一起的，此處工作流程基本上與班級(jí)管理的流程相同。

        6  系統(tǒng)的實(shí)現(xiàn)

        .1  調(diào)課功能的實(shí)現(xiàn)及設(shè)計(jì)說明

        由系統(tǒng)自動(dòng)排課生成的并不一定能完全達(dá)到用戶所想需要的效果,雖然在程序中解決了系統(tǒng)沖突的出現(xiàn),但是因?yàn)槟承┰蚨霈F(xiàn)臨時(shí)的原因都需要進(jìn)行調(diào)課,因此排課系統(tǒng)中除了自動(dòng)生成課表還必須有很靈活的調(diào)課功能才能讓系統(tǒng)更完整,也方便使用。

        此處調(diào)課是事先獲取系統(tǒng)有用資源空間,并在圖表中進(jìn)行背景色變色顯示,提示用戶該門課程可以調(diào)動(dòng)至變色顯示的地方,主要是通過班級(jí)的課程占用與該教師的排課占用情況進(jìn)行對(duì)比,尋找有利和適用的位置,并等待用戶進(jìn)行調(diào)課操作。

        執(zhí)行調(diào)課:在進(jìn)行以上操作后,計(jì)算機(jī)自動(dòng)等待用戶選擇系統(tǒng)列出的調(diào)課點(diǎn),在選擇某調(diào)課點(diǎn)后,系統(tǒng)自動(dòng)清除數(shù)據(jù)庫的中該課程的教師與當(dāng)前班級(jí)該處資源占用情況,并同時(shí)清除圖表中的資料,將其重新放置到新位置,并修改新地點(diǎn)的資源占用情況,最后將圖表的可調(diào)位置背景色還原回正常狀態(tài)。