上海師范大學(xué)碩士學(xué)位論文 摘要 時(shí)間表問題( t t p ) 是一個(gè)應(yīng)用廣泛的、典型的組合優(yōu)化和不確定性調(diào)度問題，并且 已經(jīng)被證明是n p 完全問題，課程表的編排問題是t t p 的一種典型實(shí)例。排課是教學(xué)管 理中最基本、最重要、同時(shí)也是最復(fù)雜的管理工作之，其實(shí)質(zhì)就是為學(xué)校所設(shè)置的課 程安排一組適當(dāng)?shù)慕虒W(xué)時(shí)間與空間，從而使整個(gè)教學(xué)能夠有計(jì)劃有秩序地進(jìn)行。動(dòng)態(tài)規(guī) 劃是解決多階段決策過程最優(yōu)化問題的一種方法，它把比較復(fù)雜的問題劃分為若干個(gè)階 段，通過逐段求解，最終求得全局最優(yōu)解。 本文立足農(nóng)林職業(yè)技術(shù)學(xué)院的實(shí)際情況，運(yùn)用多階段決策技術(shù)和動(dòng)態(tài)規(guī)劃技術(shù)對排 課問題進(jìn)行了分解，在分析現(xiàn)有軟件系統(tǒng)算法的基礎(chǔ)上，提出了一種新的多階段自動(dòng)排 課算法m a c a ( m u l t i s t a g ea u t o a r r a n g i n gc o u r s ea l g o r i t h m ) ，并在此基礎(chǔ)上建立了 一個(gè)通用的排課系統(tǒng)，能有效的滿足各種排i 氍需求。 2 0 0 5 年1 月，該系統(tǒng)在農(nóng)林職業(yè)技術(shù)學(xué)院投入運(yùn)行，至今為止，運(yùn)行效果良好。2 0 0 5 年7 月，系統(tǒng)通過軟件著作權(quán)申請。2 0 0 6 年初，在該系統(tǒng)基礎(chǔ)上申請通過了上海市教委 項(xiàng)目“通用多學(xué)制型排課考試費(fèi)用計(jì)算鏈應(yīng)用系統(tǒng)研究”。 本論文主要完成了以下工作： ( 1 ) 詳紐分析了課表編排問題，分析了課表編排過程中涉及的因素及各種約束條件； ( 2 ) 根據(jù)數(shù)據(jù)庫系統(tǒng)設(shè)計(jì)理論，討論了排課系統(tǒng)設(shè)計(jì)過程，包括數(shù)據(jù)庫的概念模型設(shè) 計(jì)、邏輯設(shè)計(jì)、物理設(shè)計(jì)及其實(shí)施； ( 3 ) 詳細(xì)分析了排課中各種沖突，并對每種沖突采取不同的沖突稽核方法； ( 4 ) 設(shè)計(jì)了教師分配算法：教師等概率分配算法e p d a 和首次適應(yīng)分配算法v m d a ，并 分析比較了這兩種方法的優(yōu)缺點(diǎn)，最后提出了將這兩種分配算法結(jié)合起來的優(yōu)化 算法等概率首次適應(yīng)分配算法e p f m d a ； ( 5 ) 設(shè)計(jì)了場地最佳適應(yīng)分配算法o a d a ，把場地按類型和大小進(jìn)行分配，實(shí)現(xiàn)了資源 的既充分又合理的利用； ( 6 ) 引入三維時(shí)間片劃分方法，在此基礎(chǔ)上分析了排課問題的可行解和近似最優(yōu)解， 并設(shè)計(jì)了時(shí)間片分配算法t s d a ，采用- r i j 權(quán)分組匹配思想。 ( 7 ) 立足農(nóng)林職業(yè)技術(shù)學(xué)院的實(shí)際情況，實(shí)現(xiàn)了功能強(qiáng)大的排課系統(tǒng)，不僅可以實(shí)現(xiàn) 手動(dòng)排課和自動(dòng)排課兩大基本功能，還可以打印各種報(bào)表。 關(guān)鍵字：t t p ，r i i a c a ，等概率分配，首次適應(yīng)分配，最佳適應(yīng)分配，排課系統(tǒng) m 在高校排課中的研究與應(yīng)用 a b s t r a c t t i m e t a b l ep r o b l e ma 曰) i sat y p i c a lc o m b i n a t i o no p t i m i z a t i o np r o b l e ma n du n c e r t a i n m a n a g e m e n tp r o b l e m w h i c h i sa p p l i e dw i d e l y t t ph a sb e e np r o v e dan p - c o m p l e t i o n p r o b l e m a n dt h ec o u r s ea r r a n g e m e n ti sat y p i c a li n s t a n c eo fm c o u r s ea r r a n g e m e n ti so n e o ft h eb a s e s t ，t h em o s ti m p o r t a n ta n dt h em o s tc o m p l i c a t e dt a s k so fc o l l e g e ，o fw h i c ht h e e s s e n t i a li st od i s t r i b u t et i m ea n ds p a c et oc o u r s e st om a k et h ew o r ki no r d e ra c c o r d i n gt ot h e t e a c h i n gp l a n d y n a m i cp r o g r a m m i n gi so n eo fm e t h o d st ot h em u l t i s t a g ed e c i s i o n m a k i n g p r o b l e m i tp a r t i t i o n st h ec o m p l e xp r o b l e mi n t os e v e r a lp h a s e s ，a n dg e t st h ew h o l es o l u t i o nb y r e s o l v i n ge a c hp h a s eo ft h ep r o b l e m i nt h i sp a p e r , w ea p p l i e dt h et e c h n o l o g yo fm u l t i s t a g ed e c i s i o n - m a k i n ga n dd y n a m i c p r o g r a m m i n g ，e c a l y z e dm a n ya l g o r i t h m s o fr e c e n ts o f t w a r es y s t e m s ，p r o p o s e dan e w a l g o r i t h m ，m a c a ( m u l t i s t a g ea u t o a r r a n g i n gc o u r s ea 1 9 0 r i t h m ) ，a n db u i l tag e n e r a lc o u r s e a r r a n g e m e n ts y s t e m ，w h i c hc a nr e a l i z ea l lk i n d so fr e q u i r e m e n t s ， f r o mj a n u a r yo f2 0 0 5 ，t h es y s t e m h a sb e e np u ti n t ou s ei ns h a n g h a iv o c a t i o n a la n d t e c h n i c a lc o l l e g eo fa g r i c u l t u r ea n df o r e s t r y ，a n dt h ep e r f o r m a n c ei sg o o d ，s 0f a r i nj u l yo f 2 0 0 5 ，t h es y s t e mp a s s e dt h ea p p l i c a t i o no ft h es o f t w a r ec o p y r i g h t a tt h eb e g i n n i n go f2 0 0 6 ， an e wp r o j e c tb a s e do nt h i ss y s t e m ，s t u d yo fag e n e r a ls y s t e mb a s e do nc o u r s ea r r a n g e m e n t & e x a m i n a t i o na r r a n g e m e n t e x p e n s e sc a l c u l a t i o n ，w a sa p p l i e da n da p p r o v e db yt h e s h a h g h a im u n i c i p a le d u c a t i o nc o m m i s s i o n t h em a i nw o r ko ft h i sp a p e r ： ( 1 ) a n a l y z e dt h em a i nf a c t o r sa n da 1 1k i n d so fc o n s t r a i n t so fc o u r s ea r r a n g e m e n ti nd e t a i l ( 2 ) d i s c u s s e dt h ed e s i g np r o c e s so fc o u r s ea r r a n g e m e n ts y s t e mu s i n gt h ed e s i g nt h e o r y o fd a t a b a s es y s t e m ，i n c l u d i n gt h ec o n c e p td e s i g n ，t h el o g i c a ld e s i g n ，t h ep h y s i c a l d e s i g na n dt h ei m p l e m e n t a t i o n ( 3 ) a n a l y z e da l lc o l l i s i o n si nt h ec o u r s ea r r a n g e m e n tp r o c e s s ，a n dp r o p o s e dd i f f e r e n t s o l u t i o n s ( 4 ) d e s i g n e da l g o r i t h m so f t e a c h e rd i s t r i b u t i o n ：d i s t r i b u t e a l g o r i t h mo f e q u a lp r o b a b i l i t y ( e p d a ) a n dd i s t r i b u t ea l g o r i t h mo ff i r s tm a t c h i n g ( f m d a ) c o m p a r e dt h e a d v a n t a g ea n dd i s a d v a n t a g eo ft h et w oa l g o r i t h m s ，p r o p o s e da l lo p t i m i z a t i o no f i j 上海師范大學(xué)碩士學(xué)位論文 t e a c h e rd i s t r i b u t ea l g o r i t h m ，d i s t r i b u t ea l g o r i t h mo ff i r s tm a t c h i n gb a s e do ne q u a l p r o b a b i l i t y ( e p f m d a ) ( 5 ) d e s i g n e dt h eo p t i m a la d a p t a t i o nd i s t r i b u t i o na l g o r i t h mo fp l a c e ( o a d a ) d i s t r i b u t e dp l a c e sb a s e do nt h e i rt y p ea n dc a p a c i t y , w h i c hc a nu t i l i z ep l a c e sf u l l ya n d r e a s o n a b l y ( 6 ) i n t r o d u c e dat h r e e - d i m e n s i o n a lt i m e s l i c em e t h o d a n da n a l y z e dt h ef e a s i b l es o l u t i o n ( f s ) a n dt h en e a re x c e l l e n ts o l u t i o n ( n e s ) d e s i g n e dt h ed i s t r i b u t e a t g o r i t h mo f t i m e s l i c e ( t s d a ) u s i n gt h ei d e ao fw e i g h e dg r o u pm a t c h i n g ( 7 ) b u i l tag e n e r a lc o u r s ea r r a n g e m e n ts y s t e mb a s e dt h ep r a c t i c eo fs h a n g h a iv o c a t i o n a l a n dt e c h n i c a lc o l l e g eo fa g r i c u l t u r ea n df o r e s t r y , w h i c hh a st w om a i nf u n c t i o n s ： a r r a n g i n gc o u p eb yh a n da n da u t o m a t i c a l l y , i ta l s oc a ne x p o ga uk i n d so fp a p e r s k e yw o r d s ：t i m e t a b l ep r o b l e m ，m u l t i s t a g ea u t o a r r a n g i n g c o u r s e a 1 9 0 r i t h m ，t h e d i s t r i b u t i o no fe q u a lp r o b a b i l i t y , t h ed i s t r i b u t eo ff i r s tm a t c h i n g ，t h ed i s t r i b u t i o no fo p t i m a l a d a p t a t i o n ，c o u r s ea r r a n g e m e n ts y s t c m i i j 一 圭塑墮要莖蘭嬰主蘭垡絲蘭 圖2 1 圖3 1 圖4 1 圖4 2 圖4 3 圖4 4 圖4 5 圖4 6 圖4 7 圖4 8 圖5 1 圖5 2 圖5 3 圖54 圖5 5 圖5 6 圖5 7 圖5 8 圖5 9 圖6 ，1 圖6 2 圖6 3 圖6 4 圖6 5 圖6 6 圖6 7 圖6 8 圖 圖 圖 圖 圖表索引 空課程表8 數(shù)據(jù)庫邏輯結(jié)構(gòu)設(shè)計(jì)過程1 6 d f d 的符號表示2 1 排課系統(tǒng)頂層d f d 圖2 2 制訂專業(yè)教學(xué)計(jì)劃的細(xì)化d f d 圖 手動(dòng)排課的細(xì)化d f d 圖 e r 模型的符號表示 學(xué)校行政層次e r 模型 學(xué)校行政層次e r 模型實(shí)例 排課系統(tǒng)e r 模型， 手動(dòng)排課可視化界面 鼠標(biāo)拖放沖突稽核過程 刪除排課稽核過程 與空白時(shí)間片換課沖突稽核過程 與非空白時(shí)間片換課沖突稽核過程 更換教師沖突稽核過程 更換場地沖突稽核過程 調(diào)課示例 調(diào)課流程 多階段排課過程 教學(xué)班級形成過程 教師和課程之間的關(guān)系 教師等概率分配算法 教師首次適應(yīng)分配算法 2 3 2 5 ，2 5 2 6 2 6 3 0 3 2 3 3 3 4 ，3 5 3 6 ，3 7 3 8 3 9 ，4 0 。4 2 ，4 2 ，4 3 ，4 4 等概率首次適應(yīng)分配算法 場地最佳適應(yīng)分配算法， 三維向最圖 時(shí)間片分配算法 0 基于課程的分配思想 1 基于班級的分配思想 系統(tǒng)功能模塊圖， 4 5 4 7 ，4 8 5 3 5 4 5 5 。6 0 上海師范大學(xué)碩士學(xué)位論文 第一章緒論 時(shí)間表問題t t p ( t i m e t a b l ep r o b l e m s ) 是一個(gè)應(yīng)用廣泛的、典型的組合優(yōu)化和不 確定性調(diào)度問題，并且已經(jīng)被證明是n p 完全問題，不存在多項(xiàng)式復(fù)雜性的解法。c o o p e r 等人在中以五種不同的方式證明了時(shí)間表問題是n p 一完全類問題。 課程表編排問題是一個(gè)非常難的組合優(yōu)化問題，是t t p 的一種典型實(shí)例，在研究領(lǐng) 域中，它常常是t t p 的代名詞，代表了這樣的一類問題。所謂課程表問題，是指用一定 的方法，排出滿足一定條件的課程表，而這些條件因具體學(xué)校各自要求的不同而不同， 特別是大學(xué)的課程表要求與中小學(xué)的要求大不相同。 1 1 課程表編排問題及其研究現(xiàn)狀 課程表的編排問題在教務(wù)工作中占有重要地位。在每個(gè)新學(xué)期開始之前，學(xué)校根據(jù) 教學(xué)計(jì)劃，以及教師、學(xué)生、教室、設(shè)備等情況，編排一個(gè)教學(xué)活動(dòng)時(shí)間安排表( 俗稱 課程表) ，以便有秩序地來組織全校的教學(xué)活動(dòng)。 課程表的編排問題是t t p 的一種典型實(shí)例，其難度在于：它是一個(gè)好壞標(biāo)準(zhǔn)很難統(tǒng) 一的問題，對于同一個(gè)排課結(jié)果，有人說好，有人說不好，其質(zhì)量標(biāo)準(zhǔn)很難規(guī)定和量化。 因此從這種意義上說，求解課表編排問題的最優(yōu)解是不可能的。在設(shè)計(jì)中我們把滿足用 戶期望值的程度作為評價(jià)課程表優(yōu)劣的標(biāo)準(zhǔn)。 1 1 1 國外研究狀況 從上世紀(jì)5 0 年代末開始，國外就有人著手研究用計(jì)算機(jī)來解決課表問題。在1 9 7 5 年以前的一段時(shí)間里，人們主要從構(gòu)造算法模型入手，研究其解決方法，目的是能找到 一個(gè)解決問題的有效算法。1 9 6 2 年，g o t l i e b 提出了一個(gè)構(gòu)造課程表的數(shù)學(xué)模型”3 ，接 著人們對這個(gè)模型算法解的存在性等問題作了許多探索。1 9 7 6 年，e v e n 等人證明了課 表問題是一個(gè)n p 完全類問題。3 。對于大多數(shù)這類問題，迄今為止還沒有找到在多項(xiàng)式步 驟內(nèi)解決的有效算法。因此，人們尋求有效算法的探索告一段落，而將更多精力轉(zhuǎn)到如 何借助計(jì)算機(jī)這一現(xiàn)代化工具來解決實(shí)際課程表的編排問題。 進(jìn)入9 0 年代以后，國外對課表問題的研究仍然十分活躍。如比較有代表性的印度 v a s t a p u r 大學(xué)管理學(xué)院的a r a b i n d at r i p a t h y p “3 、加拿大m o n t r e a l 大學(xué)的j e a na u b i n $ 口 j a c q u e sf e r l a n d “1 等。 t t p 在高校排課中的研究與應(yīng)用 1 1 2 國內(nèi)研究狀況 國內(nèi)對課表問題的研究開始于8 0 年代初期，所用方法從模擬手工排課到運(yùn)用人工智 能構(gòu)建專家系統(tǒng)或決策支持系統(tǒng)都有。在國內(nèi)，自1 9 8 4 年清華大學(xué)發(fā)表了實(shí)驗(yàn)性研究成 果起，相繼多個(gè)院校都開展了此項(xiàng)研究工作。具有代表性的有大連理工大學(xué)的教學(xué)調(diào) 度軟件、清華大學(xué)的 u t p s 自動(dòng)排課系統(tǒng)，南京工學(xué)院的u t s s 排課系統(tǒng)、西北 工業(yè)大學(xué)的西工大科教排課系統(tǒng)、北京科利華排課系統(tǒng)等。 1 1 3 主要算法概述 目前，解決課表問題的方法有以下幾類： ( 1 ) 啟發(fā)式算法 啟發(fā)式算法，如禁忌搜索( t a b us e a r c h ) 算法”7 “、模擬類似自然界金屬退火過 程的模擬退火算法“”1 、類似于自然界種群遺傳的遺傳算法“”1 ”等等。 t a b us e a r c h ( 也稱列表尋優(yōu)法) ，可以看作是對局部搜索算法的改進(jìn)，具有較強(qiáng)的 局部搜索能力。在這種技術(shù)中，首先按照隨機(jī)方法產(chǎn)生一個(gè)初始可行解作為當(dāng)前解，然 后搜索當(dāng)前解鄰域中的所有可行解，取其最好的可行解作為新的當(dāng)前解。為了避免陷入 局部解，這種優(yōu)化方法允許一定的上山操作( 會(huì)使解的質(zhì)量變差) 。另外，為了避免搜 索路徑的往返重復(fù)，t a b us e a r c h 使用列表的形式記錄搜索路徑的歷史信息，這在一定 程度上可使搜索過程避開局部極值點(diǎn)，開辟新的搜索區(qū)域。這優(yōu)化方法的主要問題是 列表的大小不易確定”1 。 戴春達(dá)。3 等人在t a b us e a r c h 算法的基礎(chǔ)上，改進(jìn)得到了模擬記憶搜索算法。 模擬退火法( s i m u l a t e da n n e a l i n g ) 是k i r k p a t r i c k 等人于1 9 8 3 年首先提出的”， 它是人們從自然界固體退火過程中得到啟發(fā)并從中抽象出來的一種隨機(jī)優(yōu)化算法。模擬 退火法用于求解優(yōu)化問題的出發(fā)點(diǎn)是基于物理中固體物質(zhì)的退火過程與一般優(yōu)化問題 間的相似性。在對固體物質(zhì)進(jìn)行退火處理時(shí)，常先將它加溫使其粒子可自由運(yùn)動(dòng)，以后 隨著溫度的逐漸下降，粒子逐漸形成低能態(tài)晶格。若在凝結(jié)點(diǎn)附近的溫度下降速率足夠 慢，則固體物質(zhì)定會(huì)形成最低能量的基態(tài)，優(yōu)化問題也存在類似過程。模擬退火法被用 來解決許多實(shí)際應(yīng)用中的優(yōu)化問題，取得了不錯(cuò)的效果，但用其解決排課問題，現(xiàn)在還 處在模型試驗(yàn)階段。還有許多問題要解決。 李增智m ，等人提出了一種基于概率型啟發(fā)式算法( h a ) 的混合型模擬退火算法，通過 2 上海師范大學(xué)碩士學(xué)位論文 概率型啟發(fā)式算法得到了模擬退火的初始解，然后用模擬退火方法對初始解進(jìn)一步優(yōu) 化。 遺傳算法。“”。2 ”是一種借鑒生物界自然選擇和進(jìn)化機(jī)制發(fā)展起來的高度并行、隨 機(jī)、自適應(yīng)的隨機(jī)搜索算法，是一種非常有效的解決n p 完全的組合優(yōu)化問題的方法。 遺傳算法使用群體搜索技術(shù)，尤其適用于處理傳統(tǒng)搜索方法難以解決的復(fù)雜的和非線性 的問題。經(jīng)過近4 0 年的發(fā)展，遺傳算法在理論研究與實(shí)際應(yīng)用中取得了巨大的成功， 但相對其鮮明的生物基礎(chǔ)，其數(shù)學(xué)基礎(chǔ)還是相對不完善的。 陳本慶“”等人針對基本遺傳算法不以概率1 收斂于最優(yōu)解的問題，提出了一些改進(jìn) 方法并對其收斂性進(jìn)行了證明。 楊宇“7 1 等人對遺傳算法做了多個(gè)方面的改進(jìn)優(yōu)化，得到了一種排課算法，該算法能 很好的避免遺傳算法出現(xiàn)未成熟收斂等一系列問題。另外，還針對“甩課”問題，設(shè)置 了三個(gè)子算法，分別通過計(jì)算機(jī)資源優(yōu)化度和回溯調(diào)整方法來避免和解決。 張春梅”等人把排課目標(biāo)分為優(yōu)化時(shí)間和空間兩類，把課程也分為兩類，采用遺傳 算法思想，對兩類課程分別給出染色體編碼和適應(yīng)度函數(shù)，并采用了自適應(yīng)的雜交和變 異概率。 業(yè)寧?！暗热死眠z傳算法建立數(shù)據(jù)模型，定義一個(gè)四維的染色體編碼方式和包含多 種因素的適應(yīng)度函數(shù)。通過切片算子，生成指定要求的基因型個(gè)體，用交叉算子和變異 算子對基因型個(gè)體進(jìn)行運(yùn)算，再利用選擇算子選擇適應(yīng)度函數(shù)值較高的染色體編碼方 案，最后對優(yōu)化的染色體按指定方向切片，生成教師課表、學(xué)生課表和教室課表。 ( 2 ) 優(yōu)先級算法” 基于優(yōu)先級的自動(dòng)排課算法利用了運(yùn)籌學(xué)中分層規(guī)劃的思想，把求解問題在數(shù)學(xué)上 看作為一個(gè)約束條件的組合規(guī)劃問題，采用了化整為零的思想及提出了優(yōu)先級的概念， 有效地抽象了實(shí)際排課情況，縮小了求解問題的空間。楊怡等人根據(jù)北京工商大學(xué)人 工排課的要求，提出了基于優(yōu)先級的自動(dòng)排課算法。 ( 3 ) 應(yīng)用專家系統(tǒng) 專家系統(tǒng)作為人工智能領(lǐng)域最活躍的分支，受到普遍的重視?；趯＜蚁到y(tǒng)的求解 算法m 刪，將專家系統(tǒng)知識引入排課問題的求解中，有效組織排課過程中的知識，使各 種排課邏輯從程序中解放出來，能夠便于各種排課經(jīng)驗(yàn)的累積，使排課結(jié)果更加符合實(shí) 際情況。王曉昕瞄3 、胡小兵?！暗热诉M(jìn)一步擴(kuò)展了專家系統(tǒng)的適用范圍，采用模糊專家系 統(tǒng)技術(shù)，在探討模糊知識主要表達(dá)技術(shù)及各自特點(diǎn)基礎(chǔ)上，選用產(chǎn)生式規(guī)則表達(dá)方法對 t 丁p 在高校排課中的研究與應(yīng)用 排課知識的具體表達(dá)進(jìn)行了設(shè)計(jì)，著重闡述了排課系統(tǒng)推理機(jī)制，提出了規(guī)則驅(qū)動(dòng)與驗(yàn) 證調(diào)整相結(jié)合的推理方法。 ( 4 ) 應(yīng)用人工智能原理 智能規(guī)劃?！笔侨斯ぶ悄苎芯款I(lǐng)域近年來發(fā)展起來的一個(gè)熱門分支。 丁德路。8 1 等人運(yùn)用智能規(guī)劃技術(shù)，提出了基于智能規(guī)劃方法的時(shí)間表問題解決方案 p l a n t t p ( p l a n b a s e dt t p ) 。增強(qiáng)學(xué)習(xí)算法是一種機(jī)器學(xué)習(xí)的框架，其智能體通過一系 列的活動(dòng)影響其環(huán)境，并收到活動(dòng)的回報(bào)，智能體通過狀態(tài)映射到動(dòng)作來選擇能獲得最 大回報(bào)的動(dòng)作。 郭方銘?！钡热私Y(jié)合智能學(xué)習(xí)算法的q 學(xué)習(xí)算法，設(shè)計(jì)出了課表編排問題的較為實(shí)用 的模型。并通過對該模型的分析，詳細(xì)討論了增強(qiáng)學(xué)習(xí)算法用于課表編排從理論、實(shí)現(xiàn) 到實(shí)踐的每一個(gè)環(huán)節(jié)。 ( 5 ) 分組優(yōu)化決策算法 分組優(yōu)化決策算法”2 ?！笔悄M“人工”排課表的一種方法，優(yōu)化決策的原則是先難 后易。李爽?！钡热烁鶕?jù)高校排課中所涉及的諸多因素，提出了一種基于分組優(yōu)化決策的 算法。 ( 6 ) 作為約束滿足問題處理 約束滿足方法“是把排課問題當(dāng)作約束滿足問題。對這類約束滿足問題己有多種解 決方法，如圖著色。在圖著色的示例中計(jì)算時(shí)間相當(dāng)長，一旦指定的值失敗就需做大最 的反跟蹤，因?yàn)闆]有辦法避開不可行解。 ( 7 ) 基于搜索的算法”7 “ 局部搜索算法是一種比較通用的優(yōu)化算法，可以對特定問題在可行的時(shí)聞內(nèi)求得合 理的優(yōu)化解。但是傳統(tǒng)的局部搜索算法在優(yōu)化過程中容易陷入局部最優(yōu)。顏鶴?！钡热嗽?傳統(tǒng)局部搜索算法里引入了多領(lǐng)域搜索的思想，避免了局部攝優(yōu)，也極大地提高了解空 間里的搜索能力。 回溯是一種優(yōu)選搜索法。它按選優(yōu)條件向前搜索，以達(dá)到目標(biāo)，但當(dāng)搜索到某一步 時(shí)，發(fā)現(xiàn)原先的選擇并不優(yōu)或達(dá)不到目標(biāo)，就退回一步重新選擇。吳志斌1 、昌玉劍“” 等人在排課算法中運(yùn)用了回溯的思想，大大降低了排課過程中死鎖的發(fā)生。 分支定界法，是將問題采用原始的枚舉法進(jìn)行求解，然后對一個(gè)龐大的樹進(jìn)行搜索。 在枚舉的過程中，將產(chǎn)生大量的不可行的分支，對這些不可行的分支采用分支定界法來 剪支。定界是采用一種判別原則，定義一種抽象的界，當(dāng)超過界時(shí)，就把它剪掉。吳金 4 上海師范大學(xué)碩士學(xué)位論文 榮“。蜘等人把n p 一難的課程表問題采用分支定界的方法進(jìn)行求解，提出了一種帶約束有 教案的中學(xué)排課程表問題的分支定界算法。 ( 8 ) 數(shù)據(jù)挖掘相關(guān)算法 魏靜波“”等人針對數(shù)據(jù)挖掘中的關(guān)聯(lián)規(guī)則挖掘算法a p r i o r i 算法，提出了一種 關(guān)聯(lián)規(guī)則算法a p r i o r i2 算法。魏峻“等人運(yùn)用數(shù)據(jù)挖掘中數(shù)據(jù)集市理論，通過引入粗 糙集理論和貪心算法，完成了排課系統(tǒng)的分析、設(shè)計(jì)與實(shí)現(xiàn)。重點(diǎn)討論了建立排課模型、 組建面向排課問題的數(shù)據(jù)集市、設(shè)計(jì)算法策略以及應(yīng)用軟件的開發(fā)。 1 2 研究課程表編排問題的意義 研究課表編排問題的解決方案具有重要的實(shí)踐應(yīng)用價(jià)值和理論研究意義。 方面它在教務(wù)工作中占有重要地位，各類學(xué)校根據(jù)教學(xué)計(jì)劃的要求，在每個(gè)新學(xué) 期開始之前，必須根據(jù)本校課程設(shè)置以及教師、學(xué)生、教室、設(shè)備等具體情況，編排一 個(gè)教學(xué)活動(dòng)時(shí)間安排表( 俗稱課程表) ，以便有秩序地來組織全校的教學(xué)活動(dòng)。 另一方面，由于它是和其它的時(shí)間表問題同屬于一類問題，并且1 9 7 6 年e v e n 。1 等 人證明了課表問題屬于n p 完全類，因此課表編排問題的解決可以有力地推動(dòng)其它具有 實(shí)踐意義的時(shí)間表問題解決，具有廣泛的應(yīng)用前景：它可以應(yīng)用于小學(xué)、中學(xué)以及大學(xué) 等各類學(xué)校的課程表和各類考試的時(shí)間安排，各類大型的會(huì)議、比賽、晚會(huì)，鐵路翳牽 時(shí)刻表等，也可以應(yīng)用于與時(shí)間相關(guān)的裝配序列規(guī)劃a s p ( a s s e m b l ys e q u e n c ep l a n n e r ) 中等。 1 3 本課題研究背景 農(nóng)林職業(yè)技術(shù)學(xué)院的辦學(xué)模式是在科教興市的指導(dǎo)下產(chǎn)生的新一輪辦學(xué)模式( 有中 專、高中、高職、高職春季班、2 + 2 ( 2 年中專，2 年高職) ) 。特別是最近幾年，學(xué)校 規(guī)模發(fā)展很快，班級越來越多，而硬件設(shè)施增長相對較少。如何運(yùn)用現(xiàn)有資源為教學(xué)服 務(wù)，使教學(xué)管理隨著學(xué)校規(guī)模的擴(kuò)大更具規(guī)范化，現(xiàn)代化，是高層管理人員最最關(guān)心的 問題。 農(nóng)校在過去的幾年中，曾先后買過兩套現(xiàn)成的包含排課的軟件，但由于以下原囪而 沒有成功。 ( 1 ) 購買的系統(tǒng)大而全，排課數(shù)據(jù)缺乏獨(dú)立操作性，許多數(shù)據(jù)要由其他部門配合輸入； ( 2 ) 網(wǎng)絡(luò)經(jīng)常發(fā)生故障，調(diào)試不順利。 t t p 在高校排課中的研究與應(yīng)用 這就要求建立一個(gè)既切合農(nóng)校實(shí)際的辦學(xué)模式，又具有一定的通用性、可以進(jìn)行擴(kuò) 展的排課系統(tǒng)軟件。 1 4 計(jì)算機(jī)排課的目的和意義 在我國現(xiàn)行的教育體制下，學(xué)校大體上分為三類：普通中小學(xué)、普通高校、中等專 業(yè)學(xué)校和職業(yè)學(xué)校等。不同體制的學(xué)校對課程編排有著不同的要求，課程表問題具有很 大的靈活性。但傳統(tǒng)的課程表編排是由人工來完成的。教務(wù)工作人員在長期的工作實(shí)踐 中摸索出了一些既行之有效，又切合實(shí)際的手工編排方法。 隨著教學(xué)規(guī)模的擴(kuò)大，排課涉及的因素越來越多，問題越來越復(fù)雜，使得這項(xiàng)工作 耗費(fèi)了大量的人力，總的來說人工排課存在如下困難： ( 1 ) 工作量大，耗費(fèi)較多的時(shí)間和人力； ( 2 ) 課程、教師、學(xué)生及課時(shí)等數(shù)據(jù)關(guān)系繁雜，人工管理效率低； ( 3 ) 涉及因素多，要做到考慮全面、沒任何沖突很困難： ( 4 ) 細(xì)小數(shù)據(jù)的調(diào)整，往往牽涉很廣，增加很多工作量； ( 5 ) 課表填寫、數(shù)據(jù)匯總等簡單重復(fù)性工作量很大。 因此，課程表編排問題一直被人們認(rèn)為是最困難的作業(yè)調(diào)度問題之一。隨著計(jì)算機(jī) 的應(yīng)用從科學(xué)計(jì)算、實(shí)時(shí)控制逐漸擴(kuò)展到非數(shù)值處理的各個(gè)領(lǐng)域，計(jì)算機(jī)系統(tǒng)在辦公自 動(dòng)化的應(yīng)用日益受到各行各業(yè)的極大關(guān)注。計(jì)算機(jī)的應(yīng)用為人們提供了現(xiàn)代化的工具和 手段，應(yīng)用計(jì)算機(jī)技術(shù)進(jìn)行自動(dòng)排課，可以大大提高排課效率，合理分配有限的教室和 教師資源，盡可能減少排課過程中的人為因素的干擾，從而使得課程安排更加合理。 1 5 章節(jié)安排 本文章節(jié)安排如下： 第一章緒論，概述論文的研究意義、背景、國內(nèi)外發(fā)展現(xiàn)狀及章節(jié)安排。 第二章排課問題概述，具體描述了排課問題中涉及到的因素以及各種約束條件， 并把約束條件根據(jù)約束滿足要求分為硬約束和軟約束。 第三章主要技術(shù)背景，簡要介紹一下本論文中用到的一些技術(shù)，包括多階段決 策技術(shù)、動(dòng)態(tài)規(guī)劃技術(shù)、以及數(shù)據(jù)庫技術(shù)和一些設(shè)計(jì)工具。 第四章排課系統(tǒng)的分析與設(shè)計(jì)，根據(jù)數(shù)據(jù)庫系統(tǒng)設(shè)計(jì)理論，簡要介紹排課系統(tǒng) 的設(shè)計(jì)過程。 6 圭堡! ! 墮查蘭堡主蘭垡堡苧 第五章排課稽核條件，重點(diǎn)討論排課過程中可能出現(xiàn)的沖突以及沖突的稽核方 法。 第六章多階段分組自動(dòng)排課算法，重點(diǎn)討論自動(dòng)排課中涉及到的算法，包括教 師等概率分配算法、首次適應(yīng)算法及兩種方法的結(jié)合；場地最佳適應(yīng)算法和時(shí)間片的 加權(quán)匹配算法，并重點(diǎn)討論了三維時(shí)間片的劃分方法，結(jié)合動(dòng)態(tài)規(guī)劃技術(shù)分析了排課 問題的可行解和近似最優(yōu)解。 第七章排課系統(tǒng)的實(shí)施與測試，簡要介紹排課系統(tǒng)的功能，以及測試。 第八章總結(jié)與展望，簡要概括了本論文所做的工作，以及將來需要進(jìn)一步考慮 的后續(xù)問題。 最后是參考文獻(xiàn)，讀碩期間研究成果和致謝等。 訂p 在高技排課中的研究與應(yīng)用 第二章排課問題概述 就其實(shí)質(zhì)而言，排課問題是一個(gè)有約束的、非線性的、模糊多目標(biāo)優(yōu)化的、難解的、 時(shí)空組合的數(shù)學(xué)問題。即在滿足各種己知的約束條件的情況下，找到一組較優(yōu)的時(shí)空組 合，同時(shí)在具體實(shí)踐上它受到教學(xué)組織形式、客觀物質(zhì)條件和求解目標(biāo)等多種因素的相 互影響，使這問題在實(shí)際解決時(shí)呈現(xiàn)出受具體條件制約的特點(diǎn)。 當(dāng)前大多數(shù)院校的排課是采用手工編排方法，它主要通過人的判斷和協(xié)調(diào)來完成。 手工編排工作往往開始于一個(gè)學(xué)期數(shù)月前，各部門的協(xié)調(diào)交互頻繁，而且在實(shí)際安排過 程中，涉及的校區(qū)可能有多個(gè)，教師數(shù)量成千，學(xué)生數(shù)目上萬，教師跨院上課和班級交 叉上課眾多，而且在計(jì)劃安排完畢之后，往往由于頻繁的變動(dòng)不得不及時(shí)調(diào)艇。所有諸 如此類因素，使得排課工作不堪重負(fù)，工作結(jié)果也不盡人意。 計(jì)算機(jī)排課，是把排課問題化為計(jì)算領(lǐng)域的、有約束的時(shí)空組合優(yōu)化問題來進(jìn)行求 解。它對課表上的時(shí)間進(jìn)行了分片處理，使分成的每個(gè)時(shí)間片和每個(gè)教室空間組合，構(gòu) 建了一個(gè)個(gè)大小不等的時(shí)空組合塊，并根據(jù)求解規(guī)則，對每個(gè)開課計(jì)劃進(jìn)行時(shí)空組合塊 分配，而且分配的組合，必須在目標(biāo)空間中表現(xiàn)出良好的人為滿意度。這些人為滿意度 往往有多個(gè)，而且是模糊的。 2 1 課表編排中的基本問題 2 1 1 課程表結(jié)構(gòu) 在我們的排課系統(tǒng)中，把“周”劃分成若干個(gè)以“一課時(shí)”為單位的時(shí)間片的集合 設(shè)每天上課的節(jié)數(shù)為m ，每周的天數(shù)為n ，這樣就形成了一個(gè)m 州的周時(shí)間表矩陣。取m = 1 2 n = 7 ，時(shí)間表如圖2 1 所示： 圖2 1 空課程表 上海師范大學(xué)碩士學(xué)位論文 這樣的課表劃分可以滿足不同體制學(xué)校的不同上課要求，可以單節(jié)課安排，也可以 連接幾節(jié)課一起安排，使課表在編排上具有很大的靈活性。 每個(gè)行政班級都有對應(yīng)的課程表，每張課表的眉頭顯示的是行政班級的名稱以及學(xué) 年度學(xué)期信息。圖2 1 表示周七天，從星期- n 星期臼；每天十二節(jié)課，其e e 上午四 節(jié)，下午至晚上八節(jié)，中間由分隔線分開，也可以根據(jù)具體情況作適當(dāng)調(diào)整?！皒 ”表 示該單元格還未被占用。 2 1 2 基本排課術(shù)語 排課過程是一個(gè)非常復(fù)雜的過程，在課表編排過程中將會(huì)遇到教務(wù)管理中各種常用 的名詞術(shù)語，不同體制的學(xué)?？赡懿幌嗤?，現(xiàn)統(tǒng)一加以說明。 定義2 1 課程：待排課程的集合，也就是教學(xué)計(jì)劃中所有課程的集合。 定義2 2 班級：待排課的班級集合，一般特指行政班級，有時(shí)也稱行政班級。 定義2 3 教師：所有參加排課的教師的集合。 定義2 4 場地：所有參加排課的教室、實(shí)驗(yàn)室、體育場地等等可供教學(xué)使用的場 所集合。 定義2 5 學(xué)時(shí)：教學(xué)活動(dòng)所延續(xù)的課時(shí)數(shù)。 定義2 6 時(shí)間片：把課程表根據(jù)單課時(shí)的時(shí)間長度，劃分為長度相等的若干個(gè)時(shí) 問段，每個(gè)時(shí)間段稱為一個(gè)時(shí)間片。 定義2 7 行政班級：簡稱班級，即最初注冊入學(xué)的班級單元。 定義2 8 教學(xué)班級：實(shí)際參與排課的單元，即獨(dú)立授課的一個(gè)單元。它可能是幾 個(gè)行政班級的合并，或者某個(gè)行政班級的部分，也可能是幾個(gè)行政班級的交叉組合。 每個(gè)教學(xué)班級都有一個(gè)唯一的序列號，稱為教學(xué)班級號，通過教學(xué)班級號可以確定 和該教學(xué)班級相關(guān)的教師信息、課程信息、場地信息等等。 定義2 9 教學(xué)班級號：一個(gè)自增長序列，表示本學(xué)年度、本學(xué)期以課程和教師組 織教學(xué)的一個(gè)序列，它是排課中作為稽核條件的唯一標(biāo)志。 定義2 1 0 合班上課：出于資源分配的需要，多個(gè)開設(shè)同一門課程的行政班級可能 合在一起進(jìn)行授課。合班上課的行政班級對應(yīng)一個(gè)教學(xué)班級號。 定義2 1 l 拆班上課：個(gè)行政班級根據(jù)一定的拆分規(guī)則，拆成幾個(gè)教學(xué)班級進(jìn)行 授課。拆班的行政班級對應(yīng)于同一門課程有多個(gè)教學(xué)班級號。 定義2 1 2 拆班后再合班上課：多個(gè)行政班級中的某個(gè)或某些行政班級按某種規(guī)則 t t p 在高校排課中的研究與應(yīng)用 抽出部分同學(xué)，然后再交叉組合進(jìn)行授課，組合后的每個(gè)教學(xué)班級對應(yīng)一個(gè)教學(xué)班級號。 2 。1 3 課表編排 課表編排的基本目標(biāo)就是在圖2 】中的“x ”中填入教學(xué)計(jì)劃中的課程，為每個(gè)行政 班級生成學(xué)期課程表，并且使得不產(chǎn)生教師、場地、班級等的沖突。 課表編排的任務(wù)是以“教師在某時(shí)某地?fù)?dān)任某班級某課程”的基本形式下達(dá)的。課 程的設(shè)置是由教學(xué)計(jì)劃規(guī)定的，教學(xué)活動(dòng)的組織是根據(jù)學(xué)校的實(shí)際情況，把課程、班級、 教師、場地以及時(shí)間作為教學(xué)活動(dòng)組織的對象，通過優(yōu)化組合，然后以課程表的形式直 觀的顯示出來。 課表編排完成后，教學(xué)計(jì)劃中規(guī)定的每個(gè)班級開設(shè)的每門課程都應(yīng)和一個(gè)任課教 師、一個(gè)上課場地以及一些時(shí)間片相聯(lián)系，同時(shí)，不會(huì)出現(xiàn)任課老師、上課場地和上課 時(shí)間的沖突，并且可以滿足學(xué)校、教師和場地等的一些特殊要求。 2 1 4 課表調(diào)整 課表編排完畢后，應(yīng)能根據(jù)實(shí)際需要進(jìn)行局部的微調(diào)。比如某個(gè)教師對自己的課程 安排又提出了新的要求；某門課程的上課場地另有他用，需要更換等等。 2 2 基本排課要素 排課問題是一個(gè)多約束問題。在排課系統(tǒng)中主要涉及五類要素：課程要素、班級要 素、教師要素、場地要素和時(shí)間要素。 2 2 1 課程要素 課程即教學(xué)計(jì)劃中規(guī)定開設(shè)的課。課程除一些基本屬性，如課程編號、課程名稱外， 還應(yīng)該有一個(gè)課程類型屬性，用以標(biāo)明該課程是公共課程、必修課程或者選修課程等等。 般情況下，公共課程的優(yōu)先級最高，即，排課時(shí)應(yīng)先考慮公共課程的編排，再考慮其 他課程的編排。 2 2 2 班級要素 班級又分為行政班級和教學(xué)班級( 定義見2 1 2 ) 。行政班級指招生時(shí)注冊的班級， 每個(gè)行政班級有一個(gè)編號和相應(yīng)的行政班級名稱。但在實(shí)際排課時(shí)，因?yàn)橐紤]某些課 1 0 上海師范大學(xué)碩士學(xué)位論文 程需要合班上課，比如公共政治課可以幾個(gè)行政班級合在一起授課；而有些課程需要拆 班上課，比如體育課要求男女生分開上課；這樣就使得真正上課的班級有可能并不是單 獨(dú)的行政班級，而是幾個(gè)行政班級的組合或者一個(gè)行政班級的一部分。因此，這里引入 了教學(xué)班級的概念，即，教學(xué)班級或者是幾個(gè)行政班級的合并，或者是一個(gè)行政班級拆 開的一部分，也有可能是幾個(gè)行政班級拆分后的再組合。而教學(xué)班級才是真正參與排課 的班級元素，每個(gè)教學(xué)班級都有一個(gè)唯一的編號和相應(yīng)的教學(xué)班級名稱。 2 2 3 教師要素 教師即有可能參與排課的所有教師的集合。排課時(shí)除了需要考慮教師所在的分校、 部門、專業(yè)或教研室等信息外，還需要考慮教師的特殊需求，即教師本人對排課時(shí)間、 地點(diǎn)等的特殊要求。例如： ( 1 ) 某某老師要求他的課不要安排在星期一。 ( 2 ) 某某老師要求將她計(jì)算機(jī)一班的高等數(shù)學(xué)課安排在西部校區(qū)，并且在星期三 上午l ，2 節(jié)。 2 2 4 場地要素 場地即可以用于排課的所有的教室、實(shí)驗(yàn)室或體育場地的集合。場地除了容量等屬 性外，還應(yīng)該有一個(gè)標(biāo)識場地類型的屬性，可能包括普通教室、多媒體教室等等。例如， 1 0 1 教室是個(gè)非多媒體教室，那么某門需要多媒體教學(xué)的課程就不能排在該教室上課。 任何場地還可能有其自身的特殊要求，例如，1 0 2 教室要求星期五第二大節(jié)不能安排課。 2 2 5 時(shí)間要素 時(shí)間要素用于說明各個(gè)時(shí)間片是否安排上課。在安排時(shí)間片的過程中，要考慮三個(gè) 方面的沖突：( 1 ) 同一個(gè)教師不能在同一個(gè)時(shí)間段上兩門課： ( 2 ) 同一個(gè)班級不能在 同一個(gè)時(shí)間段上兩門課；( 3 ) 同一個(gè)場地不能在同一個(gè)時(shí)間段安排兩門課。 另外，時(shí)間片本身還需要滿足一定的要求，可以分為一般性要求和特殊性要求。一 般性要求對大部分學(xué)校普遍適用，主要有以下兩條： ( 1 ) 星期六、星期曰一般不上課。 ( 2 ) 晚上一般不上課。 特殊性要求主要是各學(xué)校針對自身情況做出的規(guī)定，差異性較大。例如：某校規(guī)定 ! ! 壟壹堇簍堡! 絲翌塞皇窒星 星期三下午不安排課，用作政治學(xué)習(xí)。 2 3 排課約束條件及分類 根據(jù)約束條件被滿足的不同情況，可以把約束分為兩類m 3 ；硬約束和軟約束。硬約 束，是指在排課過程中，必須要滿足的約束，不存在任何取舍問題。相反，軟約束是指 可以被違反，應(yīng)盡可能滿足的約束。結(jié)合農(nóng)校的實(shí)際情況，主要存在以下約束條件。 2 3 1 硬約束 ( 1 ) 在同一時(shí)間同一學(xué)生不能上兩門不同的課程； ( 2 ) 在同一時(shí)間同一教師不能給兩門不同課程上課； ( 3 ) 在同一時(shí)間同一教室不能安排兩門不同課程： ( 4 ) 教室必須足夠大，能夠容納上課的學(xué)生； ( 5 ) 上課場地必須滿足上課類型要求； 2 3 2 軟約束 ( 1 ) 一個(gè)班級上課時(shí)間安排在周內(nèi)要盡量分布均勻； ( 2 ) 對于跨校區(qū)設(shè)置的課表在各個(gè)時(shí)間存在一定的偏好； ( 3 盡量滿足教師上課時(shí)聞的期望； ( 4 ) 教師對時(shí)間安排在課表上的密度有一定的喜好； ( 5 ) 教師和班級接連兩次上課地點(diǎn)盡量較近等等。 利用計(jì)算機(jī)來模擬手工排課工作，可以抽象問題中的各個(gè)要素，數(shù)學(xué)表達(dá)各種約束 條件，并根據(jù)課表的組織形式和普遍存在的規(guī)律，縮減問題空間的搜索范圍，以及有效 的組織排課知識，使其在一定程度上呈現(xiàn)智能化。但由于其問題本身的求解規(guī)模過于龐 大，各要素之間的關(guān)聯(lián)層出不窮，以及人們對課表優(yōu)劣評定的準(zhǔn)則存在差異，使計(jì)算機(jī) 在求解排課問題的過程中，面對難以窮盡的組合和多個(gè)模糊目標(biāo)的優(yōu)化，也表現(xiàn)得無能 為力。 1 2 上海師范大學(xué)碩士學(xué)位論文 第三章主要技術(shù)背景 3 1 多階段決策最優(yōu)化問題與動(dòng)態(tài)規(guī)劃 3 1 1 多階段決策最優(yōu)化問題 在現(xiàn)實(shí)生活中，有一類活動(dòng)過程，由于它們的特殊性，可將過程分成若干個(gè)互相聯(lián) 系的階段，每階段都需要作出決策，從而使整個(gè)過程達(dá)到最好的活動(dòng)效果。各個(gè)階段 的決策不能任意確定，它依賴于當(dāng)前面臨的狀態(tài)，又影響以后的發(fā)展。當(dāng)各個(gè)階段決策 確定后，就組成一個(gè)決策序列，從而也就確定了整個(gè)過程的條活動(dòng)路線。這種把