畢業(yè)設(shè)計（論文）智能排課系統(tǒng)設(shè)計與實現(xiàn)

1、北方民族大學(xué) 學(xué)士學(xué)位論文 論文題目 智能排課系統(tǒng)設(shè)計與實現(xiàn) 系(部)名 稱: 計算機科學(xué)與工程學(xué)院 學(xué) 生 姓 名: 專 業(yè): 學(xué) 號: 指導(dǎo)教師姓名: 任 榮 論文提交時間: 2012-4-23 論文答辯時間: 2012-4-28 學(xué)位授予時間: 北方民族大學(xué)教務(wù)處制 智能排課系統(tǒng)設(shè)計與實現(xiàn)智能排課系統(tǒng)設(shè)計與實現(xiàn) 摘 要 排課，是給學(xué)校各專業(yè)的教學(xué)計劃中設(shè)置的課程安排合適的時間和地點，也就是 給每個班的課程安排時間和地點。排課工作在教學(xué)管理中很重要也很繁瑣，計算機智 能排課系統(tǒng)，可以降低排課人員的工作量，減少排課中的人為因素1-2。但排課問題屬 于 np 問題，即無法直接得到答案，只能通過

2、猜測獲取可能結(jié)果。通常 np 問題雖無答 案，卻有算法，算法不能直接告訴答案，但可以用來判斷可能的結(jié)果是否正確可行。 因此，要做好排課工作，提高排課效率，實現(xiàn)智能排課是必不可少的。 本文在查閱大量相關(guān)文獻的基礎(chǔ)上，對高校的排課問題進行了分析，設(shè)計和實現(xiàn) 了該功能，此系統(tǒng)主要被分為三個部分：界面的設(shè)計、排課算法的設(shè)計、以及報表的 自動生成。本系統(tǒng)是采用 microsoft visual studio 2005 作為前臺開發(fā)工具，sql server2005 作為后臺數(shù)據(jù)庫平臺的管理系統(tǒng)。 關(guān)鍵詞：關(guān)鍵詞：智能排課、貪心、分治、visual studio 2005、sql server 2005。

3、 the design and implementation of intelligence curriculum system abstract courses timetabling, is to arrange the appropriate time and the place to the curriculum in school each specialized plan of instruction or is for each classs curriculum arrangementeach semester, courses timetabling work is in t

4、he teaching supervisory work key point and the difficultyauto-course timetabling can help reduce working pressure and man-made interruptioncourses timetabling, belonging to the np question，is unable to give the direct answer, but a possible result through guessalthough the question does not have the

5、 answer，has the algorithm actually，the algorithm usually cannot tell the answer, but can tell whether the some possibility is true of falsetherefore，it is essential to implementation of intelligence curriculum systemit may help to enhance the timetabling efficiency，promote teaching management level

6、enhancement this article in the consult massive correlation 1iterature foundation has carried on the analysis to courses timetabling，design and implement the function, this system is mainly divided into three parts: interface design, curriculum design, and reports of the automatic generation. this s

7、ystem is used as a microsoft visual studio 2005 development tools, sql server2000 as the back-end database management system platform. keywords the design and implementation of intelligence curriculum system; greedy; partition; visua1 studio 2005; sql server 2005 目 錄 摘 要 .ii abstract .iii 1緒論 .1 1.1

8、 系統(tǒng)開發(fā)背景.1 1.2 系統(tǒng)開發(fā)環(huán)境及方法.1 1.2.1.開發(fā)環(huán)境.1 1.2.2 開發(fā)方法.3 2 可行性分析 .4 2.1 技術(shù)可行性.4 2.2 經(jīng)濟可行性.4 2.3 操作可行性.5 2.4 法律可行性.5 3 系統(tǒng)需求分析 .6 3.1 系統(tǒng)功能需求.6 3.2 系統(tǒng)非功能需求.6 3.2.1 排課中的基本原則.6 3.2.2 排課的基本要求.7 4 總體設(shè)計 .8 4.1 系統(tǒng)總體構(gòu)架.8 4.2 系統(tǒng)功能結(jié)構(gòu).8 4.3 排課算法.9 4.3.1 目前常用算法.9 4.3.2 排課問題描述.10 4.3.3 排課問題的數(shù)學(xué)表示.11 4.3.4 排課問題的優(yōu)先級問題.11

9、4.3.5 算法思想.12 4.3.6 算法分析.13 5 數(shù)據(jù)庫設(shè)計 .14 5.1 系統(tǒng)數(shù)據(jù)表.14 5.2 uml 建模圖.14 5.3 數(shù)據(jù)字典.15 5.4 數(shù)據(jù)庫關(guān)系圖.18 6 詳細設(shè)計 .19 6.1 數(shù)據(jù)庫訪問模塊.19 6.2 條件設(shè)置模塊.22 6.3 教學(xué)計劃模塊.25 6.4 排課模塊.26 6.5 課程表查詢模塊.44 結(jié)束語 .46 致謝 .47 參考文獻 .48 1 緒論 1.1 系統(tǒng)開發(fā)背景 在高校各項教學(xué)管理工作中，排課一直是最基本的、最重要的工作，其實質(zhì)就是 給教學(xué)計劃中設(shè)置的課程安排合適的時問和地點，保證整個教學(xué)工作能夠順利地進行； 同時，排課工作也是一

10、項很復(fù)雜的工作，排課是一個 np 問題，就是始終找不到一個最 優(yōu)的方法能夠解決的問題，因為這個問題涉及了多種因素進行組合規(guī)劃，有教師、學(xué) 生的因素，也有教室的因素。尤其在目前各高校規(guī)模不斷擴大，教學(xué)資源面臨緊張， 教師總數(shù)不足的前提下，排課工作問題更為凸出。 隨著計算機技術(shù)的飛速發(fā)展，特別是計算機的應(yīng)用已普及到經(jīng)濟和社會生活的各 個領(lǐng)域。使原本的舊的管理方法越來越不適應(yīng)現(xiàn)在社會的發(fā)展。許多人還停留在以前 的手工操作。這大大地阻礙了人類經(jīng)濟的發(fā)展。為了適應(yīng)現(xiàn)代社會人們高度強烈的時 間觀念，利用計算機實現(xiàn)高校排課系統(tǒng)勢在必行。對于各大高校來說，利用計算機支 持學(xué)校管理員排課，是適應(yīng)現(xiàn)代學(xué)校的制度要

11、求、推動學(xué)校管理走向科學(xué)化、系統(tǒng)化、 規(guī)范化的必要條件，從而達到提高校管理效率的目的。給同學(xué)和老師帶來方便。 1.2 系統(tǒng)開發(fā)環(huán)境及方法 .2.1.開發(fā)環(huán)境 在計算機硬件和軟件快速發(fā)展的今天，計算機硬件和軟件已經(jīng)遠遠滿足本管理系 統(tǒng)的要求。在數(shù)據(jù)庫編程工具方面，各種可視化編程方法的出現(xiàn)，一改過去程序設(shè)計 的概念和方法，用戶用鼠標就可以快速、簡捷地創(chuàng)建應(yīng)用程序，極大地提高了編程效 率。選用 microsoft visual studio 2005 中文版數(shù)據(jù)庫開發(fā)的應(yīng)用程序可以獨立運行 于 windows 平臺，而且 sql server2005 產(chǎn)生的數(shù)據(jù)庫適用范圍廣，因此本系統(tǒng)

12、采用 microsoft visual studio 2005 中文版來完成高校排課系統(tǒng)的設(shè)計。 visual studio 是微軟公司推出的開發(fā)環(huán)境。是目前最流行的 windows 平臺應(yīng)用 程序開發(fā)環(huán)境。2005 年，微軟發(fā)布了 visual studio 2005。.net 字眼從各種語言的 名字中被抹去，但是這個版本的 visual studio 仍然還是面向 .net 框架的（版本 2.0） 。它同時也能開發(fā)跨平臺的應(yīng)用程序，如開發(fā)使用微軟操作系統(tǒng)的手機的程序等。 總體來說是一個非常龐大的軟件，甚至包含代碼測試功能。 這個版本的 visual studio 包含有眾多版本，分別面向不

13、同的開發(fā)角色。同時還永久提供免費的 visual studio express 版本。 使用 visual studio 2005, 專業(yè)開發(fā)人員能夠： （1）使用改進后的可視化設(shè)計工具、編程語言和代碼編輯器，享受高效率的開發(fā) 環(huán)境 ； （2）在統(tǒng)一的開發(fā)環(huán)境中，開發(fā)并調(diào)試多層次的服務(wù)器應(yīng)用程序 ； （3）使用集成的可視化數(shù)據(jù)庫設(shè)計和報告工具，創(chuàng)建 sql server 2005 解決方案 ； （4）使用 visual studio sdk 創(chuàng)建可以擴展 visual studio ide 的工具6-8。 vb 2005 是 visual studio 2005 中最重要的組件之一，是新一代的

14、 vb，但它并不 是 vb.net2003 的簡單升級，從開發(fā)界面到控件，vb 2005 與 vb.net2003 之間還是有比 較大的區(qū)別6。 新一版 sql server 的設(shè)計目標正是幫助企業(yè)單位應(yīng)對上述挑戰(zhàn)。作為 microsoft 公司的下一代數(shù)據(jù)管理與分析軟件，sql server 2005 有助于簡化企業(yè)數(shù)據(jù)與分析應(yīng)用 的創(chuàng)建、部署和管理，并在解決方案伸縮性、可用性和安全性方面實現(xiàn)重大改進。 基于 sql server 2000 技術(shù)優(yōu)勢構(gòu)建的 sql server 2005 將提供集成化信息管理 解決方案，可幫助任何規(guī)模的組織機構(gòu)： （1）創(chuàng)建并部署更具伸縮性、可靠性和安全性的

15、企業(yè)級應(yīng)用。 （2）降低數(shù)據(jù)庫應(yīng)用創(chuàng)建、部署與管理的復(fù)雜程度，進而實現(xiàn) it 效率最大化。 （3）憑借可供創(chuàng)建更具安全保障之數(shù)據(jù)庫應(yīng)用的豐富、靈活、現(xiàn)代化開發(fā)環(huán)境增 強開發(fā)人員工作效能。 （4）跨越多種平臺、應(yīng)用和設(shè)備實現(xiàn)數(shù)據(jù)共享，進而簡化內(nèi)部系統(tǒng)與外部系統(tǒng)連 接。 （5）實現(xiàn)功能強勁的集成化商務(wù)智能解決方案，從而在整個企業(yè)范圍內(nèi)推進科 學(xué)決策，提高工作效率。 （6）在不必犧牲性能表現(xiàn)、可用性或伸縮性的前提下控制成本費用水平9-10。 1.2.2 開發(fā)方法 以各高校的排課需求為應(yīng)用背景，開發(fā)一個典型的高校智能排課系統(tǒng)?？紤]實際 情況，本系統(tǒng)將采用結(jié)構(gòu)化生命周期法進行系統(tǒng)分析和設(shè)計，并采用原型法

16、進行系統(tǒng) 實施。 圖 1-1 原型法生命周期圖 原型法的基本思想是在投入大量的人力，物力之前，在限定的時間內(nèi)，用最經(jīng)濟 的方法開發(fā)出一個可實際運行的系統(tǒng)模型，用戶在運行使用整個原型的基礎(chǔ)上，通過 對其評價，提出改進意見，對原型進行修改，統(tǒng)一使用，評價過程反復(fù)進行，使原型 逐步完善，直到完全滿足用戶的需求為止。這樣能有效避免盲目開 發(fā)問題， 同時能充分的發(fā)揮原型法的優(yōu)勢，能順利實現(xiàn)系統(tǒng)的實施4-5。 2 可行性分析 2.1 技術(shù)可行性 該系統(tǒng)對軟、硬件系統(tǒng)要求較低，所需硬件設(shè)備，市場上銷售且價格較低，甚至 可以使用原有的設(shè)備。軟件上，操作系統(tǒng)采用 windows 系列操作系統(tǒng)、microsoft

17、 visual studio 2005 作為前臺開發(fā)工具，它具有的“編輯后繼續(xù)運行(edit and continue)”的特性，超越了舊的編輯編譯測試模式。它還引入了面向?qū)ο蟮某绦?設(shè)計思想和“控件”概念，使得大量已經(jīng)編好的 visual basic 程序可以直接拿來使用。 同時， visual basic 又是最容易學(xué)習(xí)與應(yīng)用的程序語言之一。它的功能非常強大，已 成為一種專業(yè)化的開發(fā)語言和環(huán)境。采用 sql server 2005 作為后臺數(shù)據(jù)庫平臺的管 理系統(tǒng)，它在電子商務(wù)、數(shù)據(jù)倉庫和數(shù)據(jù)庫解決方案等應(yīng)用中起著核心作用，可為企 業(yè)的數(shù)據(jù)管理提供強大的支持，對數(shù)據(jù)庫中的數(shù)據(jù)提供有效的管理，

18、并采用有效的措 施實現(xiàn)數(shù)據(jù)的完整性、數(shù)據(jù)的安全性以及數(shù)據(jù)的可靠易用性等等。這些軟件在高校排 課系統(tǒng)開發(fā)中已被大量應(yīng)用，技術(shù)上都比較成熟。因此在技術(shù)上是可行的。 2.2 經(jīng)濟可行性 當今學(xué)校內(nèi)部沒有完善的高校排課系統(tǒng)，管理水平差，學(xué)校課程不能得到合理分 配。迫切需要提高現(xiàn)代化管理水平、管理質(zhì)量和管理高校課程。高校排課系統(tǒng)的初步 現(xiàn)代化的開發(fā)和使用，能夠大大提高學(xué)校管理者的工作效率，節(jié)省成本提高經(jīng)濟效益。 它把從事教務(wù)管理的人員從繁重的手工操作中解脫出來，用更多精力從事創(chuàng)造性的管 理活動和其它重要的活動中去，從而達到節(jié)省人力、物力，財力的目標；它能使決策、 計劃和其它管理活動更加科學(xué)、精確、靈活。

19、因此，開發(fā)一個專門針對高校排課系統(tǒng)， 在經(jīng)濟上也是可行的。 2.3 操作可行性 本系統(tǒng)靈活方便，快捷迅速，適應(yīng)處理多項數(shù)據(jù)。采用友好、直觀的視窗界面， 鼠標、鍵盤兩種操作方式任意選擇，方便快捷。界面統(tǒng)一規(guī)范，提示信息功能完整， 稍一接觸就可以上手進行所有操作。 2.4 法律可行性 本系統(tǒng)純?yōu)閭€人設(shè)計，在開發(fā)過程中沒有涉及合同、責任、版權(quán)等與國家相關(guān)法 律規(guī)定相抵觸的方面。因此，本系統(tǒng)在法律上是可行的。 3 系統(tǒng)需求分析 3.1 系統(tǒng)功能需求 智能排課系統(tǒng)需要實現(xiàn)對學(xué)校教師、教室、班級、及課程的信息管理，對高校排 課，都有智能的管理，主要實現(xiàn)如下的一些功能： 班級各種信息的輸入，包括班級號，班級

20、名稱，年級，班級人數(shù)，是否合班。 教師各種信息的輸入，包括教師號，教師姓名，職稱，聯(lián)系方式。 學(xué)校課程的增加，刪除，修改。 學(xué)校課程計劃的制定。 學(xué)校的自定義排課，根據(jù)需要，人工排課。 學(xué)校的智能排課，根據(jù)需要，隨機智能排課。 有一些相關(guān)的提示。 課表查課界面，根據(jù)不同條件，查看課程安排。 3.2 系統(tǒng)非功能需求 3.2.1 排課中的基本原則 在課程的編排中應(yīng)遵循一定的規(guī)則, 只有按照基本規(guī)則來進行課程的編排才能夠 減少沖突的發(fā)生, 這些基本規(guī)則主要有以下幾條: 1) 同一班級的學(xué)生在同一時間(某些特定的選修課時間除外) 不能安排兩門課程 2) 同一教師在同一時間不能安排兩門課程 3) 同一教

21、室在同一時間不能安排兩門課程 4) 同一時間安排的課程總數(shù)不能大于所能提供的教室總數(shù) 5) 某一課程參加學(xué)習(xí)的總?cè)藬?shù)不應(yīng)大于所安排教室的座位數(shù) 6) 所提供教室的屬性與課程所需教室的屬性一致 在時間、教師、班級、教室、課程這五維關(guān)系中, 時間、教師、班級三者之間存 在著緊密關(guān)系。相對而言, 教室與它們關(guān)系就不那么密切。 3.2.2 排課的基本要求 課程的安排不是任意的, 為了達到最好的教學(xué)效果應(yīng)遵循一定的要求。這些要求 主要有: 1) 要盡量為所排課程安排上該類課效果最好的時間 2) 課程在一周上多次時,要有一定的間隔性 3) 公共課等涉及面廣、學(xué)時多的課程應(yīng)優(yōu)先處理 4) 對同一教師,同一上

22、課對象應(yīng)盡量選擇相對固定的幾個教室 5) 對同一個班級的課程應(yīng)選擇相對固定的教室 6) 連著的課的教室選擇不應(yīng)相隔太遠 7）同一天有幾門課時盡量把課分散 8) 優(yōu)先滿足一些特殊要求（比如有些教室喜歡上上午的課，可以優(yōu)先滿足） 4 總體設(shè)計 4.1 系統(tǒng)總體構(gòu)架 本系統(tǒng)采用客戶/服務(wù)器（client/server）模式。又叫主從式架構(gòu)，簡稱 c/s 結(jié) 構(gòu)，是一種網(wǎng)絡(luò)架構(gòu)，它把客戶端 (client) （通常是一個采用圖形用戶界面的程序） 與服務(wù)器 (server) 區(qū)分開來。每一個客戶端軟件的實例都可以向一個服務(wù)器或應(yīng)用 程序服務(wù)器發(fā)出請求。 圖 4-1 系統(tǒng)體系結(jié)構(gòu)圖 c/s 的優(yōu)點是能充分

23、發(fā)揮客戶端 pc 的處理能力，很多工作可以在客戶端處理后再 提交給服務(wù)器?？梢猿浞掷脙啥擞布h(huán)境的優(yōu)勢，將任務(wù)合理分配到 client 端和 server 端來實現(xiàn)，降低了系統(tǒng)的通訊開銷對應(yīng)的優(yōu)點就是客戶端響應(yīng)速度快。 4.2 系統(tǒng)功能結(jié)構(gòu) 高校排課系統(tǒng)可以用于支持各高校完成高校排課的難題，有如下幾個個方面的目 標：支持各高校輸入班級信息； 支持各高校輸入教師信息，班級教師的增刪改等方面。 支持輸入教室，還有自定義排課和智能排課以及課表查詢。 系統(tǒng)分為四大模塊：條件設(shè)置、課程計劃、排課管理、課表查詢、系統(tǒng)管理。 . 智能排課系統(tǒng) 設(shè)置課程計劃排課管理課表查詢系統(tǒng)管理 課 程 管 理 教 室

24、課 表 教 師 課 表 班 級 課 表 智 能 排 課 手 工 排 課 計 劃 管 理 教 師 管 理 新 建 計 劃 教 室 管 理 班 級 管 理 圖 4-2 功能模塊圖 具體設(shè)計目標如下： (1)界面友好，操作簡單，幫您輕松上手。 (2)系統(tǒng)具有靈活、嚴格的權(quán)限設(shè)定功能，采用非常周密有效的權(quán)限設(shè)置，確保高 校各類資料的可靠性和保密性，防止錯誤和違規(guī)操作。系統(tǒng)管理：可修改管理員權(quán)限 及密碼。 (3)高校排課系統(tǒng)，資料詳細周到，同窗多頁的界面方式讓你輕松完成所有工作。 (4)友善的登錄界面，包括學(xué)生登錄，教師登錄，和管理員登陸，根據(jù)身份不同， 進入的界面也 4.3 排課算法 4.3.1 目前

25、常用算法 目前，解決排課問題常用的方法有：著色算法11，通過研究時間資源庫的形成策 略，分析基于時間資源的排課算法12?；诜謱臃种?、貪心算法的排課系統(tǒng)的設(shè)計與 實現(xiàn)13，基于圖論方法的自動優(yōu)化排課模型研究14，基于資源受限的非線性約束多目 標排課模型及算法15，整數(shù)規(guī)劃解決排課問題16，基于遺傳禁忌算法結(jié)合解決排課問 題17等。這些方法雖然提高了搜索效率，但由于高校普遍存在課程量大，教室、教師 資源緊張，排課約束條件多且條件經(jīng)常變化等問題，排課算法的應(yīng)用仍然受到很大限 制19。 4.3.2 排課問題描述 排課問題的約束條件 排課即要滿足一定的硬約束條件來協(xié)調(diào)處理教師、教室、學(xué)

26、生、時間之間的多維 沖突，同時還要盡可能滿足一些軟約束條件，從而使排出的課表更加合理， 滿足人性 化需求。硬約束條件要求系統(tǒng)必須滿足的條件，而軟約束條件是在滿足硬約束條件以 后要考慮的約束條件，軟約束條件不要求系統(tǒng)必須滿足，但滿足這些條件能得到較優(yōu) 解。常用的硬約束條件有： (1) 所有的課程都必須被安排； (2) 除合班課外，同一時間，一個教室只能被一個班級占用； (3) 除選修課外，同一時間，一個班級只能安排一門課程； (4) 同一時間，一個教師只能在一個教室上課； (5) 同一個教師所上的不同課程不能發(fā)生在同一時間； (6) 兩門課程不能在同一個時間安排在同一個教室； (7) 教室的類型

27、必須與課程要求一致； (8) 教室的最大容納人數(shù)必須大于等于在該教室上課的學(xué)生人數(shù)等； (9) 不同課程時間段不同，如體育課只能在白天且不安排在第一節(jié)，選修課不能安 排在早上等。 常用的軟約束條件有： (1) 同一門課程的上課時間盡量間隔均勻。例如某課程周學(xué)時為 4 學(xué)時，以 2 學(xué)時 為一個教學(xué)單位，需安排兩次。兩次的安排時間盡量間隔一天或者一天以上； (2) 每個學(xué)生的課程均勻的分布在工作日中； (3) 學(xué)生的上課時間要盡量選擇在較好的上課時間段； (4) 對班級、教室、教師的單雙周上課時間點盡量匹配，以節(jié)約教學(xué)資源； 4.3.3 排課問題的數(shù)學(xué)表示 如果用 c 表示課程、 s 表示班級、

28、n 表示時間、 r 表示教室，t 表示教師， 排課 問題的目標就是找出滿足約束條件的(c，s，n，r，t)組合。并且，這五種元素之間存 在一定的對應(yīng)關(guān)系： c 與 s 之間的對應(yīng)關(guān)系，即每個班級有其特定要上的課程； c 與 t 之間的對應(yīng)關(guān)系，即每門課程有一定的任課教師； (n，r)與(s，c，t)之間的對應(yīng)關(guān)系，即每個教室在某一時間段只能有一個班級 上一門課程。排課問題的實質(zhì)就是對于給定的一組(s，c，t)要分配其一個滿足上課條 件的時空片(n，r)。即找到(n，r)與(s，c，t)之間的一一對應(yīng)關(guān)系。 4.3.4 排課問題的優(yōu)先級問題 排課中有很多等待分配時空片的(s，c，t)，如何安排它

29、們的分配次序，不僅關(guān) 系到算法的性能、安排的合理性，更關(guān)系到最終能否求出可行解。因此，分配次序的 好壞也是每個算法中要仔細處理的問題。在本文的算法中，是對每一組 (s，c，t)設(shè) 定優(yōu)先級，然后按照優(yōu)先級的高低次序分配時空片。設(shè)定(s，c，t) 優(yōu)先級要考慮的 因素有： (s，c，t)中課程 c 的類別，對于不同類別的課程，給它們設(shè)定相應(yīng)的優(yōu)先值， 本算法中針對課程類別的優(yōu)先級設(shè)定如下：專業(yè)基礎(chǔ)課、公共基礎(chǔ)課、專業(yè)限選課、 專業(yè)選修課、公選課優(yōu)先級別依次降低， 其中專業(yè)基礎(chǔ)課級別最高，公選課級別最低； (s，c，t)中課程 c 在一周內(nèi)要上的次數(shù)。即一門課程周學(xué)時越多，優(yōu)先級越高； (s，c，

30、t)中班級 s 所需要上的課程總數(shù)的大小。即學(xué)生每周要上的課程總數(shù)越 多，優(yōu)先級越高； (s，c，t)中學(xué)生 s 中的人數(shù)的大小。 最后根據(jù)各個因素的重要性不同，給每個因素設(shè)置一定的權(quán)重系數(shù) p0、p1、 p2、p3，最后求四種因素的帶權(quán)累加和，即得到一個(s，c，t)的優(yōu)先級，每次按 照(s，c，t)的優(yōu)先級的降序次序來分配時空片。 4.3.5 算法思想 該算法在選擇每一組教學(xué)任務(wù)(s，c，t)時是按貪心策略來選擇， 即按(s， c， t)優(yōu)先級的降序次序選擇優(yōu)先級最高的教學(xué)任務(wù)。 接下來在進行時空片分配過程 中 采用分治的策略，在分配過程中分為三個層次： 1）即先分配要上課的星期數(shù)（星期數(shù)

31、是指星期一到星期五的任意一天） ， 2）再分配其該天的上課時間段（在本文中某天的上課時間段分為 5 個時間段，上 午 1、2 節(jié)為第 1 個時間段， 上午 3、4 節(jié)為第 2 個時間段，下午 1、2 節(jié)為第 3 個時 間段，下午 3、4 節(jié)為第 4 個時間段，晚上 1、2 節(jié)或者 1、2、3 節(jié)為第 5 個時間段） ， 3）最后分配上課的教室。同時在每一階段的分配過程中，都要對資源總數(shù)和使用 狀況作統(tǒng)計和記錄，從而防止不計后果的資源濫用。算法主要步驟如下： step1：初始化。 step1.1：初始化，將所有教室按類型劃分，并在每一類型中按教室容量統(tǒng)計可用 教室資源的數(shù)目。例如，可將教室劃分為

32、：普通教室、多媒體教室、語音室、物理實 驗室、機房等。 然后按教室可容納人數(shù)分為 0-60 人、60-120 人、120-140 人這 4 個 不同等級。然后統(tǒng)計記錄每一類型不同容量范圍的可用教室資源數(shù)目。 step1.2：預(yù)排序，將待排的所有課程先按周學(xué)時降序排列，然后再將待排的所有 課程先按所需教室類型升序排列，再按所需教室容量降序分配，即先為上課人數(shù)多的 課程分配教室，防止較小的班級占用大教室，最后再將所有需要使用同一類型和容量 教室的課程按優(yōu)先級降序排序。 step2：分配上課的星期數(shù)。按照排序后的次序，再參照剩余的可用資源記錄來分 配每組(s，c，t)在一周內(nèi)要上課的星期數(shù)。同時參考

33、總課表，使得班級和教師的上課 時間在一周內(nèi)盡可能均勻分布。 step3:分配某天內(nèi)上課的時間段。 step3.1 對每種類型和大小的教室資源按其在一周內(nèi)的某一天的 5 個時段的分配 情況作統(tǒng)計。 step3.2 在分配時間段的時候， 從第一個時段到第 5 個時段依次查看是否還有剩 余資源，若有，則為其分配相應(yīng)的是時間段，否則看能否將某個已被占用的時間段調(diào) 整后再為其分配。分配的過程中要參照總課表，防止時間沖突。 step3.3 若有不能分配的， 查找與其相關(guān)的已經(jīng)分配了時間段的課程，并看看能 否重新為它分配時間段，從而將原來的時間段讓給不能成功找到時間段的那個課程使 用。 step4:分配上課

34、的教室：根據(jù)每一課程要求的上課時間和教室類型及大小為其分 配教室。對于每個已經(jīng)分配了星期數(shù)和時間段的課程，一般來說，都是找得到可用教 室的，因為在前兩個分配階段中，是嚴格按照資源剩余狀況來進行分配的。同時在分 配上課所用的教室時，也考慮到單雙周情況，以便充分利用教室資源。 4.3.6 算法分析 基于分治貪心相結(jié)合的排課算法主要分為 3 個階段：即分配上課星期數(shù)、分 配上 課時間段、分配上課的教室。這里對算法的時間復(fù)雜度進行分析。 第一階段：分配上課星期數(shù)，為每一門課程分配上課星期數(shù)的運算次數(shù)主要與課 程數(shù)目有關(guān)； 第二階段：分配上課的時段，為一次課分配上課時段所進行判斷的次數(shù)最壞 為 5 次，

35、分配上課時段的運算次數(shù)主要和每周上的總課程次數(shù)有關(guān)。 第三階段： 根據(jù)上課星期數(shù)和上課時段分配教室； 因此該算法主要和問題的規(guī)模有關(guān)， 即與要排課的課目數(shù)、課程的周學(xué)時數(shù)及教 室數(shù)目有關(guān)。和基于貪心策略、基于隨機分配時間片的排課算法進行比較，該算法的 運行時間介于二者之間，效率略低于基于貪心策略的排課算法， 比基于隨機分配時間 片的排課算法效率要高。但該算法在成功排課的數(shù)量上，性能比基于貪心策略的算法 會略好。 因為分治與貪心相結(jié)合的算法中是當有滿足條件的資源時，便一定會為其分 配。而貪心策略中，可能雖然存在可用資源時仍會遺漏可行解。 5 數(shù)據(jù)庫設(shè)計 5 5.1 系統(tǒng)數(shù)據(jù)表 根據(jù)系統(tǒng)需求分析，

36、以及考慮到數(shù)據(jù)表之間的關(guān)聯(lián)性，系統(tǒng)需要建立 7 個表，2 個 視圖，其用途說明如下表 4.1 所示。 表 5-1 系統(tǒng)數(shù)據(jù)表 數(shù)據(jù)表名稱數(shù)據(jù)表描述 class保存班級基本信息 hb保存組成各合班的班級號 teacher記錄教師信息 classroom記錄教室信息 course保存課程信息 lesson_plans保存教學(xué)計劃 r_l存儲總課表 表 5-2 系統(tǒng)視圖 數(shù)據(jù)表名稱數(shù)據(jù)表描述 lp_view保存需要排課的信息，利于排課 rl_view保存教室安排信息，利于查詢班級時間及教室時間 5.2 uml 建模圖 下圖主要是對應(yīng)實體關(guān)系圖，經(jīng)過分析了各實體及其屬性，用 microsoft off

37、ice visio 2007 畫出下圖。 教師 pk教教師師id 教師姓名 職稱 年齡 已上過課程 所屬部門教室 pk教教室室id 容量 類別 班級 pk班班級級id 專業(yè) 年級 人數(shù) 課程 pk課課程程id 課程名 課程計劃 pk課課程程計計劃劃id 課課程程id 班級id 教教師師id 周節(jié)次 總課時 課程性質(zhì) 課程計劃列1 排課 權(quán)重 r_t pkkc_id 星星期期 節(jié)節(jié)次次 教教室室id 是否可用 課程計劃id 單雙周 合班 p pk k合合班班號號 p pk k分分班班號號 圖 5-1 uml 建模圖 5.3 數(shù)據(jù)字典 下列表 5.2 到表 5.8 給出 7 個數(shù)據(jù)表：班級信息表、

38、合班表、教室信息表、教師 信息表、課程信息表、教學(xué)計劃表、總課表的具體描述，包括數(shù)據(jù)描述、數(shù)據(jù)名稱、 數(shù)據(jù)類型等。 表 5-3 course-班級信息表 字段名稱字段名稱說明說明數(shù)據(jù)類型數(shù)據(jù)類型長度長度主主/外鍵外鍵約束約束備注備注 class_id班級編號char10主鍵 class_name班級名char20非空 department專業(yè)char20 grade年級char10 number人數(shù)int非空 hb是否合班int非空默認 0（否） 表 5-4 hb-合班表 字段名稱字段名稱說明說明數(shù)據(jù)類型數(shù)據(jù)類型長度長度主主/外鍵外鍵約束約束備注備注 hb_id合班號char10主鍵 clas

39、s_id小班號char10外鍵非空 表 5-5 classroom-教室信息表 字段名稱字段名稱說明說明數(shù)據(jù)類型數(shù)據(jù)類型長度長度主主/外鍵外鍵約束約束備注備注 cr_id教室編號char10主鍵 capacity教室容量int category教室類別char10非空 表 5-6 teacher-教師信息表 字段名稱字段名稱說明說明數(shù)據(jù)類型數(shù)據(jù)類型長度長度主主/外鍵外鍵約束約束備注備注 t_id教師編號char10主鍵 t_name教室姓名char10非空 profession職稱char10 age年齡int department所屬學(xué)院char10 表 5-7 course-課程信息表 字段名稱字段名稱說明說明數(shù)據(jù)類型數(shù)據(jù)類型長度長度主主/外鍵外鍵約束約束備注備注 c_id課程號char10主鍵 c_name課程名char20非空 表 5-8 lesson_plans-教學(xué)計劃表 字段名稱字段名稱說明說明數(shù)據(jù)類型數(shù)據(jù)類型長度長度主主/外鍵外鍵約束約束備注備注 lesson_id課程計劃號char10主鍵 c_id課程號char10外鍵非空參照 course 表中的 c_id class_id班級號char10外鍵非空參照 class 表中 class_id t_id教師編號char10外鍵非空參照 teacher 表中