一、 問題的重述

        排課問題是高校制定教學計劃、安排教學過程中的一項較為復雜的工作，在高校教務管理工作中處于重要地位。高校在每學期末都要根據培養(yǎng)計劃和教學資源作出下學期的教學安排, 這主要體現(xiàn)在對課表的編排上。其中涉及的關鍵要素很多, 包括教師、班級、教室和授課時段等。根據排課總體目標、約束條件、及優(yōu)先級, 充分利用緊缺資源, 設計并實現(xiàn)高校課表安排系統(tǒng)。我校所面臨的問題主要有：

        第一，為節(jié)省學校在校車往返方面的開支，安排課表時應盡量減少校車運行車次。

        第二，渭水校區(qū)有包括從大一至大三三個年級的學生，20個學院近700個班級，教學任務繁重，課表安排難度較大；

        第三，基于學生的學習規(guī)律與習慣，應根據課程的難度與重要性進行課程時段的安排，若安排不當，會導致學生的學習效果不佳；

        第四，校區(qū)地處偏僻,距市區(qū)較遠，老師上課需乘車來回奔波，如果課表安排不當，就會導致部分老師前往渭水乘車次數(shù)過多或在渭水逗留時間過長；

        為此應根據教學計劃和排課要求,綜合考慮教師、課程、班級和授課時段等因素，協(xié)調合理的編排課表,制作一個系統(tǒng)模型，根據這個模型使老師、同學和學校盡可能滿意，并且具有足夠的可行性和可變動性。讓老師滿意，即讓每位老師一周內前往渭水的乘車次數(shù)盡可能少，同時還要使每位老師在渭水逗留的時間盡可能少；讓學生滿意，即同一班級同一門課程在時間段上盡量間隔開來，另外相對重要的課程應盡量安排在較好的教學時段上；讓學校滿意，即節(jié)約學校開支，使每周派往渭水的車次盡可能少。

        二、問題的分析

        課表安排的主要任務是把各學院的課程匯總, 然后根據教學計劃或教學環(huán)節(jié)制訂全校各班級的課表。根據學校的實際情況和學校所面臨的問題，可以將這類題歸為以老師、學生和學校的滿意情況為多目標的多約束的規(guī)劃問題。為了使課表的編排準確、合理、快速、高效, 充分利用學校資源，根據已知條件提出以下可行性要求：

        1、課程時段的規(guī)定：將每天分為5個時段(上午兩個,下午兩個,晚上一個)，并規(guī)定為：1-2節(jié)課為第一時段，3-4節(jié)課為第二時段  依此類推。根據學生的學習效果及課程難度與重要性，將課程時段按有利程度分為五個等級，即第一時段>第二時段>第三時段>第四時段>第五時段。

        2、課程的優(yōu)先級：將大學所有課程分為三類，

        1）其他如專業(yè)選修課或公共選修課等：少數(shù)班級開設的課程，課程相對簡單，可以任意安排時段授課。

        2）專業(yè)必修課：少數(shù)學院或一個學院開設的課程，課程重要且開設的班級數(shù)較多，這類課盡量安排在較好時段；

        3）公共必修課：多個學院開設的課程，課程重要且開設的班級數(shù)最多，這類課盡量安排在最好時段；

        3、時間段的有效性：

        1）一個老師一天內的兩節(jié)課應連排, 即盡量安排在同一天上午或同一天下午, 為教師上課提供方便，同時也減少了派往渭水的車次

        2）同一班級同一門課的兩次授課時間必須隔天，但相隔天數(shù)不宜超過兩天；

        4、時間段的分配優(yōu)先級：周一至周五的白天共20個時段用來安排公共必修課和專業(yè)必修課及部分選修課,每天晚上及周六、 周日安排其他課程；先安排公共必修課表,在剩余的時間段內安排各系專業(yè)課程，最后再安排選修課程；將相對重要的課程安排在較好時段。

        5、應避免各種沖突: 

        1）教師不沖突, 同一教師不能同一時間在不同地點上課。 

        2）學生不沖突, 同一班級學生不能在同一時間上兩門或兩門以上課程；

        3）教室不沖突, 同一教室同一時間不能安排兩門課程，人數(shù)不能超過教室的最大容量；

        4）課程不沖突, 同一班級同一課程不能同一時間在不同地點上課； 

        根據上述可行性要求，解決以下問題： 

        問題一：

        從學生的學習效率和老師的教學效果等方面，對學校的軟件設施、教學設施及運輸設施等提出一些可行性建議。

        問題二：

        利用加權綜合評判法，對老師滿意度、學生滿意度和學校滿意度進行加權綜合評價。其中老師滿意度從老師的滯留時間和老師的乘車次數(shù)方面考慮，學生滿意度以重要課程的安排的時間段好壞考慮，學校的滿意度以校車的車次考慮。

        問題三：

        要求建立排課表的數(shù)學模型，先確定公共基礎課的課程數(shù)，并將這些課程數(shù)聯(lián)系到教師和學生的滿意程度，在優(yōu)化滿意程度的條件下，排出各個公共基礎課的授課區(qū)域，指定老師在班級授課時間段的區(qū)域，并讓老師在這個區(qū)域內對不同的班級的授課時間段進行排布。然后將專業(yè)課安插到未被占用的時間段上，最后是選修課。同時課程的安排原則是盡可能選擇在較好時段。 

        問題四：

        要求對渭水校區(qū)的課表進行重排，利用統(tǒng)計學知識，對學校所有班級進行抽樣，隨機抽取三個班級，并對這三個班級的課表重排，得到的課程與現(xiàn)有的課程進行比較。

        三、符號說明

        ：課程集合

        ：課程類別的編號；

        ：按優(yōu)先級程度規(guī)定的課程編號；   CR：時段集合；

        ：空閑時段集合；

        ：滿足課程要求的空閑時段； 0：否；  1：是；

        ：間隔周期，單位：天；

        ：每周上課天數(shù)，單位：天； counts：周課時數(shù)；

        ：一次上課的節(jié)數(shù)； 

        Tc：班級的受限一維數(shù)組； 

        Tt：教師的受限一維數(shù)組； 

        P：加權后的總滿意度； 

        Pt：老師的滿意度； 

        Ps：學生的滿意度；

        Pu：學校的滿意度。

        四、模型的假設

        1.對于上課班級較多且任課老師較少的課程，每位老師可為幾組班級授課，每組班級由若干個班級組成。

        2.假設學校教室資源足夠，不考慮教室資源對課程安排的約束； 

        3.不考慮節(jié)日等因素對課程安排的影響；

        五、模型的建立與求解

        （一）問題一：建立排課表的模型，并研制出排課表的軟件包。

        利用對課程添加優(yōu)先級屬性，再根據優(yōu)先級程度每個課程進行排課，即解決死鎖問題。同時也對時間段添加優(yōu)先級屬性，在每個課程排課的同時進行時間段的選擇。根據實際情況和所的資料綜合分析實行對課程和時間段優(yōu)先級的確定，并利用C  或FORTRAN軟件對最優(yōu)課程最優(yōu)時間段的選擇。其步驟如下： 

                1、系統(tǒng)模型的設計

                系統(tǒng)模型數(shù)據庫是排課系統(tǒng)中的一個很重要的組成部分。數(shù)據庫中幾個主要的表如下, 其中“* ”號指出了各個表的主鍵:

                班級表(* 班級號、專業(yè)號、入學時間、學制)；

                課程表(課程號、*課程名稱、課程性質、授課要求、學時、選課人數(shù)、上課教室)；

                教師表(教師號、*教師名、所帶課程、*所帶班級數(shù))； 排課結果表(*課程名稱、*上課時段、上課周次)。 

                2、模型的建立

                        (1)從時段集合CRi中按序列獲取一個時段Rk, 根據課程Cj的上課要求判斷該時段是否可用并在可用時間段內選取最好時間段。

                        (2)判斷課程集合CS中所有課程集合是否都安排完成, 若再沒有待排課程則安排完畢, 否則根據順序從CS 中選擇一類課程,記作CSi。

                        (3)教務處匯總開課計劃時, 進行課程優(yōu)先級分類。分類的依據為課程的難度和重要性（公共必修課、專業(yè)必修課、專業(yè)選修課和公共選修課）分別為CS1, CS2,CS3，在對于這些類別根據該課程老師是否教授其他班課程和該課程課時的多少，將課程按優(yōu)先級順序分為C1,C2  Cj。

                        (4)如果CSi中所有課程的教室安排完成, 返回(2)；否則返回(3) , 進行CSi  1 類課程的安排, 依次類推。 

                        (5)在CSi 中選擇一門未排課程Cj,在時段集合CR中查找有空閑的時段CRi。 

                        (6)時段Rk 可用時, 課程Cj的班級和老師在時段Rk 的對應記錄上未分配, 則可安排給課程Cj,更新相應數(shù)據庫,轉入(7)。

                        (7)發(fā)生上課時段沖突, 時段Rk 不可用時, 若時段Rk 是時段集合Cr i中最后一個, 則沒有找到合適時段, 提示課程Cj安排失敗, 轉入(7) , 以便最后調整; 否則返回(4)。

                3、約束條件

                （1）、排課時不能使班級、教師、教室的時間相沖突，因前面已假設教室資源足夠，可不考慮教室的影響，故此類約束條件用一個受限時間數(shù)組來表示, 為Tc、 Tt。分別為其建立一維數(shù)組, 數(shù)組元素個數(shù)為周上課天數(shù)days, 每個元素用 “123456”的形式表示, 位數(shù)為每天上課的時段數(shù), 取2節(jié)課為一個時段。如某班級的受限一維數(shù)組Tc= (123456, 120000, 123456,003456, 123456, 103456)則表示該班級周二的下午和晚上、 周四的上午、 周六的上午3、4 節(jié)課時段空閑, 其余時段已排課或另有安排。對于教師做同樣的設置, 以便于檢測空閑時段進行排課。對某課程進行排課, 首先要檢測教師、 班級的受限時間數(shù)組，然后選擇合適的時段進行排課, 如果交集為空, 則產生沖突, 做標記后返回重排。

                （2）為了使一門課的兩次授課間隔合理, 規(guī)定了排課間隔周期。每周上課天數(shù)days, 周課時數(shù)counts, 一次上課的節(jié)數(shù)chapt 等。那么間隔周期T =[days/ (counts/ chap t)]-1。如果一門課周課時數(shù)counts= 4, 為了使老師一次授課可以連排, 兩節(jié)課代表一個上課時段, 上課節(jié)數(shù)chapt= 2, 一般每周上課6天, 則間隔周期T = 2, 即間隔2 天排下一次課(此類情況必要時也可間隔一天，如安排在周二和周四)。必修課的間隔周期可按此法計算，選修課由于其學時和選課人數(shù)的不同可另作調整。

                （3）為了降低排課的復雜性, 設計合理的排課順序,設定教學任務的優(yōu)先級。教學任務i的優(yōu)先級= 是否為公共課程或專業(yè)課程(0/1) 是否規(guī)定時段(0/1)  是否為必修課或基礎課(0/1)。這三個因素后括號的取值若為“是” , 取值為 “1” , 否則為 “0” ; 表達式中的 “  ” 是這三個因素的值連接。如果排課優(yōu)先級=“111” , 則表示: 公共課或專業(yè)課、規(guī)定了時段、必修課。計算出所有教學任務的優(yōu)先級后以降序排列, 然后按此順序進行課程編排。若兩門課程的優(yōu)先級相同，則對總學時較多的課程優(yōu)先安排。

        另外, 對于某些高校完全實行學分制的情況, 排課時只需考慮教師、教室的沖突, 不需考慮教學班的沖突, 由學生根據自己的時間來選擇合適的上課安排。

        （二）問題二：利用所建模型及軟件對本學期渭水校區(qū)的課表重排，并與現(xiàn)有課表進行比較。

        由于對渭水校區(qū)所有班級課表重排數(shù)據太多，工作量太大，根據隨機統(tǒng)計學抽樣調查，隨機抽選兩個班級，對這兩個班級的課程進行重排，根據這兩個班的實驗效果可以反映模型的可行性和實用性，將學校所有課程按1、2、3  編號，然后根據統(tǒng)計隨機程序挑選，挑選班級為28010707和26050801（關于這兩個班級的基礎數(shù)據見附表1），并對其09-10第二學期的課表進行安排，安排的步驟與結果如下：

        一】班級28010707課表安排結果如下：

            1.課程優(yōu)先級確定：《土力學與基礎工程》>《建筑電工學》>《施工技術》>《鋼筋混凝土》>《施工組織》>《現(xiàn)代施工》=《高層建筑結構》=《事故分析》=《結構穩(wěn)定理論》=《土木工程施工（二）》=《系統(tǒng)工程》=《有限元素法》。 

            2.課程的分類：公共必修課，0個；專業(yè)必修課，《土力學與基礎工程》、《施工技術》、《鋼筋混凝土》、《建筑電工學》、《施工組織》；選修課，《現(xiàn)代施工》、《系統(tǒng)工程》、《有限元素法》、《高層建筑結構》、《事故分析》、《土木工程施工（二）》、《結構穩(wěn)定理論》。 

            3.課程布置步驟：

                1）鑒于《高層建筑結構》與《施工組織》、《事故分析及處理》與《結構穩(wěn)定理論》上課時間的連續(xù)性及間隔周期的相似性，可分別等效為一門課程進行安排，安排見表1；

                2）《電工學與施工技術》間隔周期均為1-2天，可將其對稱安排在周二與周四上午兩個時段，安排見表1；

                3）鑒于《土力學與基礎工程》的優(yōu)先性與重要性，應首先對其進行安排，間隔周期為1天，規(guī)定時段為第一時段，則安排為每周一、三、五第一時段； 

        二】班級26050801課表安排結果如下： 

                1、課程分類：公共必修課，《大學英語（四）》、《概率論與數(shù)理統(tǒng)計》、《毛澤東思想與鄧小平理論》；專業(yè)必修課，《積分變換》、《面向對象程序設計》、《經濟地理與區(qū)域規(guī)劃》、《測繪工程基礎》；選修課，0個。 

                2、課程優(yōu)先級：《測繪工程基礎》>《大學英語（四）》>《概率論與數(shù)理統(tǒng)計》=《毛澤東思想與鄧小平理論》=《面向對象程序設計》>《經濟地理與區(qū)域規(guī)劃》>《積分變換》。 

                3、課程布置步驟：

                ）鑒于《測繪工程基礎》和《大學英語（四）》的優(yōu)先性與重要性，應首先對這兩門課程進行安排，間隔周期均為1天，規(guī)定時段均為第一時段，安排見表2；

                2）鑒于每位《毛澤東思想與鄧小平理論》老師為多組班級授課，可將其安排在上午和下午的后兩節(jié)課（3-4節(jié)或7-8節(jié)），以保證老師上課的連續(xù)性、來渭水乘車次數(shù)最少，安排見表2；

        ) 《概率論與數(shù)理統(tǒng)計》安排原理同《毛澤東思想與鄧小平理論》，安排見表2；

        .所排課表與原課表的比較

                （1）兩者公共必修課及專業(yè)必修課所排時間段相差不大，選修課相差較大； 

                （2）所排課表所選時間段盡量往好的時間段內取，而原課表由于某些原因而選擇相對較差的時間段；

                （3）所排課表課程相對緊湊，學生、老師上課較原課表連續(xù)。

        （三）問題三：給出評價指標評價所建模型，并指出模型優(yōu)點與不足之處。

                對于模型的評價，可以各個影響因素進行加權綜合評價方法對模型進行綜合評價。提出滿意度的概念：教師、學生和學校對所排課表的滿意程度，用百分制的打分方式表示。滿意度越高，則老師、學生和學校最模型的綜合評價越高。

                1.滿意度的計算：

                滿意度P由教師的滿意度Pt、學生的滿意度Ps和學校的滿意度Pu表示。 并關于老師、學生和學校進行加權評價，其權重分別為：0.4,0.3,0.3。 P=0.4*Pt 0.3*Ps 0.3*Pu 2.滿意度的影響條件：

                        （1）教師的滿意度：教師一周內在渭水校區(qū)的逗留總時間，教師一周內前往渭水的乘車次數(shù)；

                        （2）學生的滿意度：教師在一周內兩次上課的時間間隔，優(yōu)先等級高的課程安排的時段的好壞；

                        （3）學校的滿意度：學校一周派往渭水的車次數(shù)。 

                3.評價滿意度的具體評價指標： 

                        （1）教師的初始滿意度（100分），在學校逗留一次扣去10分，因乘車次數(shù)扣去（實際乘車次數(shù)—最小乘車次數(shù)）乘以10分； 

                        （2）學生的初始滿意度（100分），教師在一周內兩次上課的時間間隔小于一天或大于兩天扣10分，公共必修課和專業(yè)必修課分配在下午每課扣10分，選修課分配在晚上或周末每課扣10分； 

                        （3）學校的初始滿意度（100分），根據乘車次數(shù)，扣去（教師實際乘車次數(shù)—教師最少乘車次數(shù)）乘以10分。 

                4.滿意度指標的轉化： 將教師、學生和學校的初始滿意度—相應扣去的分數(shù)為教師、學生和學校的滿意度，再將這個滿意度化為百分制。

                5.對模型所排出的課表進行抽樣評價，以問題二中隨機抽取的兩個班級進行評價，其評價結果如下：

        第一組評價：

        （一）所排課表：

                轉化后的滿意度Pt=90

                轉化后的滿意度Ps=97.5

                轉化后的滿意度Pu=90.8

                加權后總滿意度P=0.4*Pt 0.3*Ps 0.3*Pu=92.49 原課表，見附表：

                轉化后的滿意度Pt=81.2

                轉化后的滿意度Ps=95

                轉化后的滿意度Pt=81.2

                加權后總滿意度P=0.4*Pt 0.3*Ps 0.3*Pu=85.34 

        （二）第二組評價 所排課表：

                轉化后的滿意度Pt=88.6

                轉化后的滿意度Ps=98.6

                轉化后的滿意度Pu=88.6

                加權后總滿意度P=0.4*Pt 0.3*Ps 0.3*Pu=91.6 原課表，見附表：

                轉化后的滿意度Pt=85.7

                轉化后的滿意度Pu=85.7

                加權后總滿意度P=0.4*Pt 0.3*Ps 0.3*Pu=87

                根據數(shù)據及圖可以得出：利用模型建立的課表，根據統(tǒng)計學知識，抽樣調查，調查的結果模型建立的課表的總滿意度和各種滿意度都略高于原課表。

        六、模型的優(yōu)缺點分析

                優(yōu)點：

                （1） 由于考慮老師的帶課班數(shù)及所授課程的重要程度，所以安排課程后可行性得到較好的保證。 

                （2） 根據這種根據優(yōu)先級先后排課表的方式即要比精確排表方式要簡單和快捷，而且所得到的實驗結果也較好，滿意度均在90分以上，保持了原課表一樣的高效性；

                缺點：

                （1） 由于模型許多條件都是根據經驗進行的人為規(guī)定，所以并不能達到最優(yōu)化的程度。

                （2） 由于模型未考慮到教室數(shù)量對排課的限制，也未考慮到其他各種客觀或主觀條件對排課的限制，故排課后的準確性比原課表要差。 

        七、模型的改進

                1．由于在建立模型時只是單純的減少老師次數(shù)來減少車次數(shù)，而實際上一個車次可以移動40多為老師，那么41與80所排出的車次數(shù)一樣，那么可以讓一部分老師乘車回家，而讓一部分老師留校休息，而這個數(shù)量需要準確計算才能得出，所以對車次的優(yōu)化對模型的改進也很有意義。

                2.由于在建立模型時未考慮到一個老師教授不同課程和老師由于生病或其他原因而臨時改變課程時間段等實際較可能出現(xiàn)的情況。所以要準確的排出課表就需將每個老師用程序編碼，將每個課程也用程序編碼，一個老師碼可以對應多個課程碼，同時老師碼可以缺碼或編碼號后移，也可以是課程號缺碼或課程碼后移，這樣就可以增加模型的機動性，使得程序更加實用。

        八、模型的總結

                高校排課系統(tǒng)一直是高校教務管理中難以解決的問題, 由于約束條件多, 教學資源要求復雜, 而且每個學校有其特殊情況, 因此排課要求也不完全一樣。按照渭水校區(qū)班級較多、課程任務繁重和老師離學校距離遠和來校難度大等特點, 設計出系統(tǒng),能較準確高效的作出安排, 滿足必要的約束條件, 能夠在一定程度上避免沖突, 提高教學管理水平。

        九、可行性建議

                1、較為重要的課程一次上課所對應的班級不宜過多，這樣既可以減輕老師上課負擔，提高教學進度，又可以避免學生因教室面積大、人數(shù)多等原因而對聽課效果產生的不良影響。

                2、重要或是較為重要的課程盡量不要安排在晚上，由于學生的學習習慣和規(guī)律以及客觀條件的限制，學習效率較白天低?？梢钥紤]把公共選修課或專業(yè)選修課安排在晚間，以減小腦力負擔。此外，重要的課程也盡量不要安排在周末，因受主觀條件等的影響，不利于學生對知識的消化。

                3、諸如C語言，C  ，數(shù)據結構，數(shù)據庫等計算機方面的課程，應盡量安排在計算機機房上課，在學習課程內容的同時鍛煉編程等實際動手操作能力。

                4、制定課表時，應盡量安排出機動課時段，機動教室，以配合由于種種原因所導致的臨時調課情況。

                5、在教室分配上，應盡量避免相臨的兩節(jié)課所用教室距離過遠，如連續(xù)兩節(jié)課教室分別在WM3501和WX1504，由于課間時間較為短暫，會在路上耽誤過多時間甚至遲到，從而影響教學進度。

                6、在教室分配方面，應避免僅有一個或兩個班所上的課程占用大教室，這會因學生就座相對分散，而導致老師不便授課、影響課程進度，另一方面，影響學生聽課效果。

                7、盡量避免把兩門以及兩門以上難度較大的課程安排在連續(xù)時段上，這會增加學生腦力負擔，不利于學生對知識的吸收。

                8、英語等需要記憶的課程應盡量避免安排在一天的最后時段，此階段學生大腦進入疲勞期，學習效果不佳。