【文章內(nèi)容簡介】 ............................... 51 附錄 3 中期報告 ............................................................................................... 54 附錄 4 外文原文 ............................................................................................... 57 附錄 5 外文譯文 ............................................................................................... 68 第 1章 緒論 1 第 1 章 緒論 課題背景 隨著信息化的高度發(fā)展，大學中遠程在線課堂授課的教學方式已經(jīng)出現(xiàn)，但這種非面對面交互的教育方式存在著很多的弊病 [1]，因此目前在我國絕大部分大學還是以教室中面對面的授課方式為主。綜合考慮大學授課中多方面的特殊性，大學授課對教室的安排與義務(wù)教育階段大不相同，對某個班級的課程安排不再局限于某一個教室，并且可能會出現(xiàn)多個班級在一個教室中上課的情況。從使用角度上看，這樣的教室安排制度增大了教室使用的自由度，尤其是在如今大學中教室少班級多課程多的現(xiàn) 狀下，這樣的教室使用方案更能充分利用教室資源，使教室得到合理的分配。 但從教室的管理角度來說，教室使用越自由，教室的管理的難度就越大。管理的難度主要體現(xiàn)在對教室排課問題上。眾所周知，大學中每個專業(yè)需要修的課程都有很多，大部分課程都能在一個學期內(nèi)學習完畢，這樣就導致每個學期初都要進行一次教室分配。分配過程不僅要考慮教室本身是否會發(fā)生使用上的空間沖突（同一教室同一時間安排了兩門或兩門以上課程），而且還要考慮參與授課過程的教師學生是否會發(fā)生時間沖突（同一學生或教師同一時間不能出席兩門或兩門以上的課程）。 而且就目 前而言 ,我國高等教育己進入大眾化發(fā)展階段 ,各高校的招生數(shù)量急劇增加 ,給高等教育帶來了深刻的變革。面對跨越式的發(fā)展速度和招生數(shù)量的大幅度增加 ,不少高校教室資源短缺的問題逐漸凸現(xiàn)出來?？茖W、高效、合理地管理和使用高校教室資源 ,保證學生正常的學習環(huán)境 ,成為目前高校教學資源管理研究的一項重要課題。 以燕山大學為例，燕山大學東校區(qū)共四座教學樓，共近 200 間大小不等類型不一的教室 ， 要分配九個學院 41個專業(yè)的課程，這些專業(yè)四個年級共有大約 450 余個班 ，有近 11000 余名學生。所有的班級總共要在 東區(qū)安排近1200 門課程，每 門課程每周上課節(jié)數(shù)不等。如果手工安排所有課程的話大概需要花費一個月左右的時間，而且手工排課不能從全局考慮教室分配的平均性。 燕山大學本科生畢業(yè)設(shè)計（論文） 2 綜合以上論述來看，一個學校需要一個優(yōu)秀的教室管理軟件勢在必行。一個教室管理系統(tǒng)不僅能方便工作人員對教室資源的管理和安排，大大減輕他們的工作量，還更能為學生和老師查詢自身與教室的相關(guān)信息提供方便，并且還可以提供給教師部分教室占用權(quán)限，分擔管理人員的一部分工作。 國內(nèi)外研究現(xiàn)狀 上個世紀中葉 ，西方學術(shù)界就有人開始研究大學排課問題。二十世紀六十年代， Gotlieb 曾為排課問題創(chuàng)建了一 個數(shù)學模型 [2]，最終使用部圖匹配解決了排課問題。在此之后，人們開始在 Goflieb 的數(shù)學模型基礎(chǔ)之上對課表問題的算法、解的存在性等問題做了很多深入研究。 人們嘗試用各種方法求解排課問題 ,有些人 嘗試 把排課問題歸結(jié)為求一組 O1變量的解，但工作量十分龐大，而且這種技術(shù)只能適用于課程較少的情況；二十世紀八十年代 Mihoe 提出排課問題可以看作是一個優(yōu)化問題；接下來 Tripathy 發(fā)表論文使用整數(shù)線性編程方法求解排課問題并提出了相應的數(shù)學模型；之后 又有人提出可以使用圖論中的方法解決排課問題，比如二部圖匹配方法。 直 到遺傳算法的提出，人們又開始研究使用遺傳算法將排課問題看作是優(yōu)化問題來解決。直到如今仍然有許多人在研究遺傳算法，比較有代表性的有印度的 Vastapur 大學管理學院的 Arabinda Tripathy、加拿大 Montreal大學的 Jean Aubin 和 Jacques Fe rland 等。 在課表安排中使用過的算法有： （ 1） 關(guān)聯(lián)規(guī)則 FP． growth 算法。 （ 2） 基于時間位 圖迭加匹配的算法。 （ 3）基于資源匹配的算法。 （ 4）分組優(yōu)化決策算法。 （ 5）分支定界法。 （ 6）有限回溯法。 （ 7）拉格朗日松弛法。 （ 8） 二次分配型法等多種方法。 第 1章 緒論 3 由于排課問題面臨時間空間各個方面的資源約束，完全用數(shù)學方法進行問題描述而忽略計算機硬件條件總結(jié)出來的解決排課問題的方法雖然理論上可以解決排課問題，但是當使用具體編程語言實現(xiàn)時又會面臨各種障礙。外國的研究表明，解決大規(guī)模課表編排問題單純靠數(shù)學方法是行不通的，而利用運籌學中分層規(guī)劃的思想將問題分解，將是一個有望成功的辦法。 在我國對排課問題的研究始于八十年代時期，從今天來看具有代表性的有：南京工學院的 UTSS(A University Timetable Scheduling System)系統(tǒng) [3]、清華大學的 TISER 系統(tǒng)、大連理工大學的智能教學組織管理與課程調(diào)度系統(tǒng)、西南交通大學提出的以課元相關(guān)運算和課元的候選時空片計算為核心的計算機排課算法，延邊大學根據(jù)人手工排課的方法設(shè)計了計算機自動排課的數(shù)據(jù)結(jié)構(gòu)與算法；沈陽電力高等?？茖W校研制了基于 Client／ Server的開放式智能排課系統(tǒng)等。 課題目的 及意義 研究該課題的主要目的是設(shè)計出一個具有良好交互性的可供學生、教師以及教室管理人員使用的具有增 、 刪 、 改 、 查功能的管理類網(wǎng)站，同時設(shè)計出一個具有實際意義且可以用 PHP 語言實 現(xiàn)的排課算法。該算法對現(xiàn)有規(guī)模的排課問題應在可以 接受的時間內(nèi)執(zhí)行完畢，算法能實現(xiàn)全部的硬性條件約束和部分軟約束 并且可以完成對絕大部分課程的安排。 研究該課題的意義在于 可以使教室管理信息化，便于與教務(wù)管理其他模塊進行數(shù)據(jù)交換并且可以作為教務(wù)管理的一部分并入 教務(wù)管理系統(tǒng)。就教室管理本身而言，設(shè)計這樣的一個系統(tǒng) 可以大大減輕教務(wù)人員 對教師信息管理工作量， 尤其是可以大大減少手工排課所花費的時間，并且從整體而言能獲得比手工排課更加合理的教室分配方案。而就其他用戶而言，該系統(tǒng)可以簡化教師申請使用教室的流程，同時方便了學生 對教室信息的查看。而且作為一個 B/S 模式的管理系統(tǒng)，可以為教師和教務(wù)人員發(fā)布與教室相關(guān)的信息提供方便。 課題研究主要內(nèi)容 該課題主要研究主要內(nèi)容有： 燕山大學本科生畢業(yè)設(shè)計（論文） 4 （ 1）確定系統(tǒng)開發(fā)語言和平臺，選取適當?shù)拈_發(fā)工具。 （ 2）對該課題進行需求分析 根據(jù)用戶使用需求和現(xiàn)有業(yè)務(wù)流程對系統(tǒng)進行分析并對系統(tǒng) 各個功能的實現(xiàn) 方式進行構(gòu)思和設(shè)計。 接下來 通過 分析現(xiàn)有的手工排課流程 設(shè)計 系統(tǒng) 數(shù)據(jù)流程圖，對系統(tǒng)和人的應完成工作進行分工，明確系統(tǒng)功能。將 將系統(tǒng)數(shù)據(jù)流程圖中出現(xiàn)的 實體抽象化規(guī)范化 ，然后對這些實體 設(shè)計數(shù)據(jù)字典，明確每一對象的屬性 。 （ 3）對數(shù)據(jù)庫進行設(shè)計 考慮系統(tǒng)中所有會出現(xiàn)并且需要保存的數(shù)據(jù)，充分考慮數(shù)據(jù)之間 的關(guān)系，本著盡量減少冗余的規(guī)則設(shè)計數(shù)據(jù)庫表，并確定表之間的關(guān)聯(lián)關(guān)系。 （ 4）對系統(tǒng)進行整體設(shè)計 根據(jù)需求分析中對問題的定義將系統(tǒng)分為具體功能的模塊 ， 使 模塊之間 高內(nèi)聚低耦合。 然后根據(jù)現(xiàn)有技術(shù)和開發(fā)語言的特性 對 每一個模塊進行設(shè)計 。 （ 5）對系統(tǒng)進行詳細設(shè)計 在整體設(shè)計結(jié)束的基礎(chǔ)上對系統(tǒng)中反復出現(xiàn)的功能模塊進行詳細設(shè)計，然后分析排課過程中出現(xiàn)的各種問題并提出解決方案，敘述排課算法的流程 。 （ 6）系統(tǒng)實現(xiàn) 該部分主要以運行界面截圖的 方式講述各個功能模塊的實現(xiàn)方式以及系統(tǒng)如何操作。 第 2章 相關(guān)技術(shù) 與理論 5 第 2 章 相關(guān)技術(shù)與理論 開發(fā)環(huán)境與工具 根據(jù)當前主流技術(shù)的發(fā)展應用趨勢，本系統(tǒng)的開發(fā)選取了 Apache + PHP + MySQL 經(jīng)典組合作為開發(fā)平臺。其中 Apache 是系統(tǒng)運行的服務(wù)器，可以滿足中小型網(wǎng)站的使用需求； PHP 作為系統(tǒng)后臺腳本開發(fā)語言，完成系統(tǒng)中控制和處理部分的功能；開發(fā)本系統(tǒng)采用 MySQL 數(shù)據(jù)庫儲存數(shù)據(jù)主要是考慮MySQL 數(shù)據(jù)庫與 PHP 語言的完美兼容性。系統(tǒng)的前臺開發(fā)使用了 HTML 文本標記語言， 頁面設(shè)計使用了 CSS 層 疊樣式表， 前臺處理使用了 JavaScript腳本語言。 系統(tǒng)開發(fā)使用的主要工具為 Macromedia 公司的 Dreamweaver 可視化網(wǎng)頁編輯器，下面分別對其進行簡要介紹。 APM 平臺 Apache 是世界使用排名第一的 Web 服務(wù)器軟件。它可以運行在幾乎所有廣泛使用的計算機平臺上。 Apache HTTP Server（簡稱 Apache）是 Apache軟件基金會的一個開放源碼的網(wǎng)頁服務(wù)器，可以在大多數(shù)計算機操作系統(tǒng)中運行，由于其多平臺和安全性被廣泛使用，是最流行的 Web 服務(wù)器端軟件之一。 PHP 是一 個嵌套的縮寫名稱，它是英文超文本預處理語言（ Hypertext Preprocessor）的縮寫 ，只要用途是處理動態(tài)頁面。 PHP 是一種 HTML 內(nèi)嵌式的語言，語言風格類似于 C語言 ， 語法混合了 C、 Java、 Perl 以及部分自創(chuàng)語法，可以比 CGI 或者 Perl 更快速的執(zhí)行動態(tài)網(wǎng)頁。 PHP 屬于解釋執(zhí)行語言，嵌入在 HTML 文檔中執(zhí)行，具有較高的效率。 其 與 ASP 和 JSP 最大的不同點就是源代碼是開源的， 而且具有良好的跨平臺性。 MySQL 是一個小型關(guān)系型數(shù)據(jù)庫管理系統(tǒng)，由于其體積小速度快的因素被廣泛用于 Inter 的中 小型網(wǎng)站中。 MySQL 具有運行速度快、支持多種平臺和支持多種開發(fā)語言的特點。與其他數(shù)據(jù)庫相比， MySQL 是一個開源的軟件，因此用戶可以免費使用 MySQL 數(shù)據(jù)庫。 選取 Apache + PHP + MySQL 的組合有兩個原因： 燕山大學本科生畢業(yè)設(shè)計（論文） 6 （ 1） Apache 和 MySQL 對 PHP 有很好的兼容性， 能很好的支持 PHP 的一些擴展功能。 （ 2） 三個軟件全部是開源軟件，使用它們能在不侵犯版權(quán)的情況下降低開發(fā)成本。 HTML CSS 和 JavaScript HTML（ Hyper Text Markup Language）即 超文本標記語言或超文本鏈接標示語言，是目前網(wǎng)絡(luò)上應用最為廣泛的語言，也是構(gòu)成網(wǎng)頁文檔的主要語言。 HTML 文本是由 HTML 命令組成的描述性文本， HTML 命令可以說明文字、圖形、動畫、聲音、表格、鏈接等。 HTML 的結(jié)構(gòu)包括頭部（ Head）、主體（ Body）兩大部分，其中頭部描述瀏覽器所需的信息，而主體則包含所要說明的具體內(nèi)容。 CSS（ Cascading Style Sheet，可譯為“層疊樣式表”或“級聯(lián)樣式表”） 是一組格式設(shè)置規(guī)則，用于控制 Web 頁面的外觀。通過使用 CSS 樣式設(shè)置頁面的格式，可將頁面的內(nèi)容 與表現(xiàn)形式分離。 頁面內(nèi)容存放在 HTML 文檔中，而用于定義表現(xiàn)形式的 CSS 規(guī)則存放在另一個文件中或 HTML 文檔的某一部分，通常為文件頭部分。 將內(nèi)容與表現(xiàn)形式分離，不僅可使維護站點的外觀更加容易，而且還可以使 HTML 文檔代碼更加簡練，縮短瀏覽器的加載時間。 JavaScript 是一種基于對象和事件驅(qū)動并具有相對安全性的客戶端腳本語言。同時也是一種廣泛用于客戶端 Web 開發(fā)的腳本語言，常用來給 HTML網(wǎng)頁添加動態(tài)功能，比如響應用戶的各種操作。它最初由網(wǎng)景公司設(shè)計，是一種動態(tài)、弱類型、基于原型的語言，內(nèi)置支持類。 使用 JavaScript 可以在客戶端進行一些動態(tài)處理并且可以提供一些對瀏覽器的操作，減少客戶端與服務(wù)器端的交互，使系統(tǒng)得到優(yōu)化。 Dreamweaver編輯器 Dreamweaver 是在網(wǎng)頁設(shè)計與制作領(lǐng)域中用戶最多、應用最廣、功能最強大的軟件。它集網(wǎng)頁設(shè)計、網(wǎng)站開發(fā)和站點管理功能于一身，具有可視化、支持多平臺和跨瀏覽器的特性，是目前網(wǎng)站設(shè)計、開發(fā)、制作的首選工具。Dreamweaver 具有靈活編寫網(wǎng)頁的特點，不 但將“設(shè)計”和“代碼”編輯器第 2章 相關(guān)技術(shù) 與理論 7 合二為一，而且在設(shè)計窗口中還精化了源代碼，能幫助用戶按工作需要 定制自己的用戶界面 [4]