【正文】 未進(jìn)行的占用。 考試申請(qǐng)與取消 用戶可以對(duì)自己所教授的課程申請(qǐng)考試教室安排。在用戶選擇考試科目以及考試時(shí)間后，系統(tǒng)會(huì)首先讀取該門課程，查找選修該門課程的全部班級(jí)，然后根據(jù)班級(jí)的人數(shù)去查找在所選時(shí)間是否存在足夠多的教室來(lái)安排考試，查找過(guò)程要注意教室的容量應(yīng)該為學(xué)生數(shù)量的兩倍，若存在足夠的教室，則系統(tǒng)以列表的方式顯示一個(gè)安排方案，由用戶確定是否進(jìn)行考試安排，同樣在安排之前要檢查教室是否已被占用；若不存在足夠的教室提示教室數(shù)量不足，用戶可以調(diào)整考試時(shí)間再次安排直至成功。安排成功之后頁(yè)面跳轉(zhuǎn)至考試歷史查看頁(yè)面，該頁(yè)面顯示已安排的考試信息。用戶不可以已安排的課程，若想取消需要聯(lián)系管理員。 發(fā)布通知 該模塊功能比較簡(jiǎn)單，有系統(tǒng)提供可以輸入通知標(biāo)題和通知內(nèi)容的表單，用戶輸入相應(yīng)內(nèi)容之后確定發(fā)布通知，系統(tǒng)將通知存入數(shù)據(jù)庫(kù)，待其他用戶登錄系統(tǒng)之后可以在通知頁(yè)面發(fā)現(xiàn)。發(fā)布成功之后頁(yè)面跳轉(zhuǎn)至通知顯示頁(yè)面，用戶可以查看通知是否發(fā)布成功。修改密碼模塊與學(xué)生密碼修改基本一致，不在贅述。 管理員功能模塊該模塊主要實(shí)現(xiàn)系統(tǒng)的管理功能以及排課功能，各個(gè)模塊之間存在一定的數(shù)據(jù)耦合，全部耦合數(shù)據(jù)都保存在系統(tǒng)變量數(shù)組中，下面介紹各個(gè)子模塊的功能。 教室管理模塊 該模塊包含三個(gè)內(nèi)容，教學(xué)樓管理、教室管理以及統(tǒng)計(jì)教室報(bào)表。教學(xué)樓管理包括教學(xué)樓的添加刪除和查看所屬教學(xué)樓的全部教室。查看結(jié)果以列表形式逐條顯示。教室管理包括教室的刪除、添加、修改以及教室課表查看。教室課表查看與教師課表查看形式基本一致，并且可以進(jìn)行打印。統(tǒng)計(jì)教室報(bào)表為系統(tǒng)訪問(wèn)數(shù)據(jù)庫(kù)按所在校區(qū)教室類型教室座位數(shù)對(duì)教室進(jìn)行分類然后統(tǒng)計(jì)各類教室的數(shù)量，以一定格式顯示，并且可以打印輸出。 考試管理模塊 管理員可以通過(guò)該模塊查看本學(xué)期已安排的全部的考試信息，也可以根據(jù)課程名查找某一門課程是否已經(jīng)安排考試。對(duì)已經(jīng)安排但尚未進(jìn)行的考試，管理員可以取消考試的安排信息。 占用管理模塊 該模塊也分為兩部分教室占用管理模塊和教室占用模塊，管理員教室占用模塊與教師申請(qǐng)教室占用基本相同。管理員使用教室占用管理功能可以查看本學(xué)期全部的教室占用信息，查找結(jié)果按時(shí)間由近至遠(yuǎn)排列，內(nèi)容分頁(yè)顯示，管理員可以取消尚未發(fā)生的占用。 課程安排 該模塊屬于系統(tǒng)最主要的功能模塊，用于實(shí)現(xiàn)學(xué)期初課程的安排，在課程安排之前應(yīng)該需要將與課程安排相關(guān)的數(shù)據(jù)導(dǎo)入數(shù)據(jù)庫(kù)，這部分由學(xué)期初始化模塊完成，因此與其有一定的數(shù)據(jù)相關(guān)性。該模塊分為三個(gè)部分，其中自動(dòng)排課功能最先調(diào)用，根絕課程要求為課程安排合適的教室，安排結(jié)束后頁(yè)面跳轉(zhuǎn)至顯示尚未安排課程的模塊。對(duì)于自動(dòng)排課未安排成功的課程再調(diào)用手動(dòng)課程安排模塊。 數(shù)據(jù)維護(hù)模塊 該模塊主要用于系統(tǒng)數(shù)據(jù)維護(hù)功能，其下又分為兩個(gè)子模塊數(shù)據(jù)備份模塊和數(shù)據(jù)恢復(fù)模塊。數(shù)據(jù)備份需要手動(dòng)操作，其備份頻率可由管理員自己根據(jù)實(shí)際情況自己決定，數(shù)據(jù)備份文件以備份時(shí)間作為文件名，儲(chǔ)存路徑為系統(tǒng)根目錄下的backup文件夾。當(dāng)系統(tǒng)數(shù)據(jù)出現(xiàn)異常時(shí)管理員可以調(diào)用數(shù)據(jù)恢復(fù)模塊將數(shù)據(jù)庫(kù)恢復(fù)至某個(gè)狀態(tài)。 本章小結(jié)本章主要介紹系統(tǒng)模塊的劃分以及各個(gè)模塊內(nèi)部的設(shè)計(jì)。模塊劃分主要考慮模塊之間低耦合模塊內(nèi)部高內(nèi)聚，先將系統(tǒng)劃分為四個(gè)大模塊，然后繼續(xù)劃分為若干個(gè)小模塊，并以系統(tǒng)層次結(jié)構(gòu)圖的方式介紹本系統(tǒng)所有的功能模塊以及功能模塊之間的關(guān)系。之后對(duì)所有小模塊各自需要實(shí)現(xiàn)的功能進(jìn)行了具體的介紹。第6章 系統(tǒng)詳細(xì)設(shè)計(jì) 第6章 系統(tǒng)詳細(xì)設(shè)計(jì)經(jīng)過(guò)上一章對(duì)系統(tǒng)總體設(shè)計(jì)的介紹，已經(jīng)對(duì)系統(tǒng)進(jìn)行了功能劃分和設(shè)計(jì)，但是由于其中涉及到的模塊較多且大部分比較簡(jiǎn)單，內(nèi)容基本都為頁(yè)面前臺(tái)設(shè)計(jì)以及讀數(shù)據(jù)庫(kù)的查找、刪除等基本操作，因此就不對(duì)這些模塊的詳細(xì)設(shè)計(jì)進(jìn)行一一介紹，這些部分的詳細(xì)設(shè)計(jì)可見(jiàn)程序源代碼。在本章將主要論述一些公共模塊的詳細(xì)設(shè)計(jì)和排課算法的詳細(xì)設(shè)計(jì)，并將排課算法的源代碼已附加文件的方式給出。 公共模塊設(shè)計(jì)其他公共模塊是指在程序中并未以獨(dú)立模塊存在但在程序中卻多次出現(xiàn)的部分，在這里做統(tǒng)一的介紹。（1）輸入模塊設(shè)計(jì) 程序中多出涉及輸入功能，輸入時(shí)用戶可能因?yàn)榉N種原因造成輸入錯(cuò)誤，表單提交之后會(huì)彈出錯(cuò)誤提示，在提交表單同時(shí)將表單內(nèi)容保存至系統(tǒng)的Session數(shù)組中，這樣在表單提交頁(yè)面刷新之后可以保存用戶的輸入歷史，方便用戶的使用。（2）用戶驗(yàn)證模塊設(shè)計(jì) 在用戶登陸成功之后將用戶名、用戶密碼和用戶身份保存至系統(tǒng)Session數(shù)組中。在每個(gè)頁(yè)面調(diào)用之前先讀取系統(tǒng)的Session信息并將該信息與數(shù)據(jù)庫(kù)中的用戶信息以及頁(yè)面所屬的模塊進(jìn)行比對(duì)，若比對(duì)結(jié)果正確則加載該頁(yè)面，若比對(duì)結(jié)果出現(xiàn)錯(cuò)誤則彈出提示信息系統(tǒng)跳轉(zhuǎn)至登陸頁(yè)面。（3）分頁(yè)顯示模塊設(shè)計(jì) 對(duì)于需要分頁(yè)顯示的數(shù)據(jù)，首先讀取數(shù)據(jù)庫(kù)確定所有數(shù)據(jù)條數(shù)nums，然后確定該頁(yè)面可顯示的條數(shù)this_nums，將兩者相除得出分頁(yè)總頁(yè)數(shù)pages。然后對(duì)數(shù)據(jù)再次查找并將結(jié)果按一定方式排序，讀取前this_nums條作為首頁(yè)顯示內(nèi)容，當(dāng)訪問(wèn)第n頁(yè)時(shí)，從查詢結(jié)果的第（n1）*this_nums開始讀取this_nums條數(shù)據(jù)記錄顯示。（4）表單提交后響應(yīng)方式的設(shè)計(jì) 程序中大部分頁(yè)面都存在表單提交，基本所有表單提交都通過(guò)本頁(yè)面中的處理程序處理，處理代碼存于一個(gè)是否存在$_POST的邏輯判斷中。本頁(yè)面處理的好處是將條件與查詢結(jié)果在同一頁(yè)面進(jìn)行顯示，表達(dá)更直觀并且便于用戶修改查詢條件。 排課算法的詳細(xì)設(shè)計(jì)排課問(wèn)題可以認(rèn)為是一個(gè)NP問(wèn)題[9]，即一個(gè)可以在多項(xiàng)式時(shí)間內(nèi)求解的問(wèn)題，而啟發(fā)式方法是解決這一類問(wèn)題的之中方法，與隨機(jī)搜索方法不同，該方法應(yīng)用領(lǐng)域內(nèi)經(jīng)驗(yàn)或規(guī)則來(lái)重新排列問(wèn)題表中節(jié)點(diǎn)的順序，搜索沿著某個(gè)被認(rèn)為是最優(yōu)希望的前沿區(qū)段擴(kuò)展。因此在開發(fā)過(guò)程中借用啟發(fā)式解決NP完全問(wèn)題的思想，利用在排課領(lǐng)域內(nèi)的經(jīng)驗(yàn)，改進(jìn)啟發(fā)式算法，將啟發(fā)式算法與回溯算法、禁忌搜索等算法相結(jié)合，設(shè)計(jì)一個(gè)適用于大學(xué)自動(dòng)排課的混合式算法[10]。從排課流程上來(lái)說(shuō)現(xiàn)在已有的排課算法有兩種[11]，一種是先對(duì)課程進(jìn)行時(shí)間安排，完全不考慮教室因素，時(shí)間安排完成之后再進(jìn)行教室分配，這樣做的好處是可以將時(shí)間分配問(wèn)題和空間分配問(wèn)題分別獨(dú)立進(jìn)行考慮，簡(jiǎn)化問(wèn)題復(fù)雜度，但也有一個(gè)缺點(diǎn)就是時(shí)間分配時(shí)有一個(gè)前提是教室資源足夠多，就現(xiàn)在大學(xué)教室使用緊張的情況而言基本不可能。因此在這里采用第二種方案，課程的時(shí)間安排與空間安排同時(shí)進(jìn)行。首先考慮排課中的時(shí)間沖突問(wèn)題。排課中的時(shí)間沖突問(wèn)題主要前面提到的硬性要求中的第三條和第四條教師和學(xué)生的沖突。由實(shí)際問(wèn)題可知并不是所有課程之間安排時(shí)都可能會(huì)發(fā)生時(shí)間沖突問(wèn)題，只有當(dāng)兩門課程的出席班級(jí)存在交集或者任課教師相同時(shí)，兩門課程在安排時(shí)才需考慮時(shí)間沖突問(wèn)題，因此只要確定所有課程之間的相關(guān)關(guān)系，就可以在排課時(shí)對(duì)時(shí)間沖突進(jìn)行考慮。在程序設(shè)計(jì)中使用無(wú)向圖的方式來(lái)表示課程之間的沖突關(guān)系[12]，圖中的頂點(diǎn)作為課程實(shí)體，若課程之間存在沖突，則將兩個(gè)沖突的實(shí)體連起來(lái)。在排課算法開始時(shí)遍歷所有課程創(chuàng)建沖突圖，如何使用沖突圖在下面講述。接下來(lái)考慮空間沖突問(wèn)題，空間沖突問(wèn)題主要是指任意兩門課程在同一時(shí)間不能安排在同間教室。空間沖突問(wèn)題在所有的課程安排時(shí)都需要考慮，在這里使用資源數(shù)組的方式解決空間問(wèn)題[13]。為每一門待排課程創(chuàng)建教室，時(shí)間二維時(shí)間片資源數(shù)組，如圖51所示：數(shù)組橫向共有20個(gè)元素，其含義為每學(xué)周周一至周五每天的四個(gè)課節(jié)，圖 61 時(shí)間片資源數(shù)組縱向?yàn)閙行，m值為教室總數(shù)。排課開始之前每門課程的資源數(shù)組中的所有元素的值均為0。設(shè)待檢測(cè)的課程安排方案為K(r,t)，r為安排的教室對(duì)應(yīng)的m值，t為安排的課節(jié)取值范圍為(1,20)。每安排成功一門課程就將所有課程的資源數(shù)組中相應(yīng)的時(shí)間片元素的值置1，這樣每安排一門課程之前只要檢查該門課程的時(shí)間片資源數(shù)組中元素αr,t值是否為0，就能確定該安排方案是否會(huì)與其他課程發(fā)生空間沖突。現(xiàn)在再返回上一步考慮時(shí)間沖突問(wèn)題。由于解決空間沖突問(wèn)題中也涉及到時(shí)間，因此時(shí)間片資源數(shù)組從縱向上可以看做是只有20個(gè)元素的時(shí)間向量數(shù)組（A1，…，A20），這樣我們也可以借助時(shí)間片資源數(shù)組來(lái)解決時(shí)間沖突問(wèn)題。解決方案如下：每當(dāng)成功安排一門課程s，設(shè)安排時(shí)間為t，開始遍歷無(wú)向沖突圖，找到所有與課程s沖突的課程集合S，對(duì)于S中的每門課程Si，將Si的時(shí)間片資源數(shù)組中與t對(duì)應(yīng)的時(shí)間向量At（α1,t,…，αm,t）內(nèi)的全部元素置1。這樣在課程安排之前只要讀取資源數(shù)組中與安排方案K(r,t)相對(duì)應(yīng)的元素αr,t的值，就可以判斷該安排方案是否會(huì)發(fā)生時(shí)間或空間沖突。在初步解決了課表安排過(guò)程中的時(shí)間與空間沖突問(wèn)題后，接下來(lái)考慮排課過(guò)程中的其他問(wèn)題。（1）如何確定課程的安排方案 本系統(tǒng)使用啟發(fā)式方式為課程查找安排方案，將隨機(jī)搜索和局部搜索相結(jié)合，首先選擇局部最優(yōu)教室，判斷是否為最優(yōu)的標(biāo)準(zhǔn)為[14]：該教室滿足課程對(duì)教室的類型和所在校區(qū)的要求；該教室座位數(shù)不小于課程出席人數(shù)；在滿足前兩條的基礎(chǔ)上教室座位數(shù)最接近課程出席人數(shù)；在滿足前三條的基礎(chǔ)上教室被安排課程的次數(shù)最少。找到最優(yōu)教室后，從20個(gè)課節(jié)時(shí)間片中隨機(jī)選出一個(gè)組成預(yù)選安排方案K(r,t)，根據(jù)時(shí)間片資源數(shù)組判斷該方案是否可行，若可行繼續(xù)進(jìn)行安排，如不可行重新選擇時(shí)間片進(jìn)行再次判斷。（2）如何對(duì)同一門課程的不同課節(jié)進(jìn)行安排 由于課程要求同一門課程的不同課節(jié)盡量安排在同一教室，而且上一步也涉及到時(shí)間片重選，因此可將20個(gè)時(shí)間片隨機(jī)排序，順序遍歷所有時(shí)間片，設(shè)置一個(gè)禁止數(shù)組，每當(dāng)課程成功安排一節(jié)之后，將與該時(shí)間片在同一天中的其他時(shí)間片加入到禁止數(shù)組，繼續(xù)遍歷時(shí)間片，安排下一課節(jié)，對(duì)課節(jié)安排時(shí)不僅要考慮時(shí)間片資源數(shù)組還要確保該時(shí)間片不在禁止數(shù)組中。若遍歷之后不能將課程的全部課節(jié)安排成功，則重新選擇教室，重復(fù)上述過(guò)程。（3）若課程安排失敗如何處理 若課程安排失敗，應(yīng)該對(duì)安排過(guò)程進(jìn)行回溯，但課程安排問(wèn)題如果僅僅是回溯到上一個(gè)剛剛安排好的課程是不行的，因?yàn)檫B續(xù)安排的兩門課程之間也許沒(méi)有任何約束關(guān)系，這樣做很可能回溯很多步之后仍不能找到可用的時(shí)間片資源[15]。因此在這里可將回溯搜索與禁忌搜索相結(jié)合，回溯過(guò)程不是回溯到上一門安排的課程，而是對(duì)沖突圖中與該門課有聯(lián)系的課程（若該門課程已經(jīng)安排）進(jìn)行回溯，并且回溯過(guò)程不再是反向遍歷安排過(guò)程，而改為遍歷沖突圖與其相關(guān)的所有課程，為保證回溯過(guò)程不會(huì)耗費(fèi)過(guò)多時(shí)間，為回溯過(guò)程設(shè)置回溯半徑。若回溯遍歷該半徑內(nèi)全部課程仍未能將該門課程安排成功，則取消該門課已安排課節(jié)的安排信息。在回溯過(guò)程中對(duì)課程進(jìn)行重新安排時(shí)也要取消該門課程的安排信息，并對(duì)其他課程的時(shí)間片資源數(shù)組做適當(dāng)?shù)男薷?。在全部課程安排結(jié)束之后，對(duì)于所有未安排成功的課程進(jìn)行再次安排，若仍未安排成功，則確定安排失敗，最后保存并返回所有安排失敗的課程信息。在取消某門課程的安排信息時(shí)，修改其他課程時(shí)間片資源數(shù)組因該是課程安排成功之后重置其他課程資源數(shù)組過(guò)程的逆過(guò)程，由于該過(guò)程涉及安排成功的安排方案，因此對(duì)每門課程設(shè)置一個(gè)儲(chǔ)存成功安排方案的數(shù)組，以便取消課程安排時(shí)使用。在修改其他課程S的資源數(shù)組時(shí)涉及一個(gè)問(wèn)題，假設(shè)課程S尚未安排并且課程S被修改的資源數(shù)組的元素αr,t不僅僅與該門課程發(fā)生沖突，還與一門或多門課程S1發(fā)生沖突，那么僅僅將αr,t置0會(huì)對(duì)安排課程S時(shí)造成影響，使安排信息出錯(cuò)。解決辦法是課程安排成功時(shí)對(duì)其他課程資源數(shù)組的修改不再是置1，而改為加1，在取消時(shí)將其減1，這樣可以確保不會(huì)丟失沖突信息。（4）如何對(duì)課時(shí)不同的課程進(jìn)行安排 為了盡量高效率的利用教室資源，將課程分為兩部分[16]：長(zhǎng)課和短課。其中課時(shí)數(shù)大于48的為長(zhǎng)課，安排時(shí)間貫穿本學(xué)期，其中課時(shí)大于64的每周安排三次，其他每周安排兩次；課時(shí)不大于48的設(shè)為短課，將其安排在上半學(xué)期或下半學(xué)期，其中課時(shí)大于32的每周安排三次，其他每周安排兩次。課程的起始學(xué)周由教務(wù)工作者手工分配，在并隨課程導(dǎo)入數(shù)據(jù)庫(kù)。程序在安排全部課程之前先讀取全部課程，讀取時(shí)將課程分別存在三個(gè)數(shù)組中，三個(gè)數(shù)組分別為保存長(zhǎng)課數(shù)組long_subjects、儲(chǔ)存需要上半學(xué)期安排的課程的數(shù)組short_subjects1和需要在下半學(xué)期安排的課程數(shù)組short_subject2。由于short_subjects1中的課程與short_subject2中的課程不會(huì)發(fā)生沖突，因此在初始化沖突無(wú)向圖時(shí)對(duì)于分別存于兩數(shù)組中的課程不做判斷。（5）如何實(shí)現(xiàn)沖突圖 由于程序中不存在圖的結(jié)構(gòu)，因此采用鏈表的方式實(shí)現(xiàn)。程序中使用的類和對(duì)象的概念，將沖突圖中與某一門課程沖突的課程全部存于一個(gè)沖突數(shù)組中，該數(shù)組作為課程對(duì)象的一個(gè)屬性存在，數(shù)組中保存的是指向沖突課程對(duì)象的指針，這樣方便對(duì)沖突課程的訪問(wèn)。下面對(duì)排課算法做簡(jiǎn)要的描述[17]（具體算法見(jiàn)代碼部分）：（1）創(chuàng)建課程類和教師類，讀取全部教室和課程的信息并創(chuàng)建相應(yīng)的對(duì)象，教室按類型、校區(qū)和座位數(shù)分別存于不同的教室數(shù)組中，將課程分別存于上面提到的三個(gè)數(shù)組中。（2）遍歷全部課程，初始化所有課程的沖突數(shù)組和時(shí)間片資源數(shù)組。（3）分別遍歷三個(gè)儲(chǔ)存課程的數(shù)組long_subjects、short_subjects1和short_subjects2，若全部課程都已安排結(jié)束則調(diào)至步驟（7），否則對(duì)每門課程Si做如下操作：（4）調(diào)用查找教室的函數(shù)，開始遍歷教室類型數(shù)組。根據(jù)啟發(fā)式前三個(gè)條件找到最合適的教室類型數(shù)組。從該數(shù)組中隨機(jī)選擇三個(gè)教室（若不足三個(gè)則全部選取），選擇三個(gè)教室對(duì)象中占用次數(shù)最少的教室，若該教室剩余時(shí)間片足夠安排該門課程返回該教室對(duì)象，否則遍歷該數(shù)組中全部課程對(duì)象，找到占用次數(shù)最少的教室，若該教室剩余時(shí)間片足夠安排該門課程返回該教室對(duì)象，否則繼續(xù)進(jìn)行遍歷。（5）對(duì)所有20個(gè)時(shí)間片隨機(jī)排序，順序遍歷時(shí)間片，通過(guò)訪問(wèn)時(shí)間片資源數(shù)組和禁止數(shù)組判斷方案K(r,t)是否可行，若可行保存該安排并重置其他課程的時(shí)間片資源數(shù)組[18]，將被占用的教室的占用次數(shù)加1。將沖突時(shí)間片加入禁止數(shù)組。判斷該門課程全部課時(shí)是否都已安排，若安排結(jié)束則調(diào)至步驟3對(duì)課程Si+1進(jìn)行安排。若該門課程尚未安排結(jié)束，則繼續(xù)執(zhí)行該步驟，若該步驟執(zhí)行完畢仍未安排結(jié)束則調(diào)至步驟4重選教室再次進(jìn)行安排，若反復(fù)執(zhí)行10次之后仍未全部安排結(jié)束則執(zhí)行步驟6進(jìn)行回溯。（6）回溯之前