【正文】 一、 問(wèn)題的重述 排課問(wèn)題是高校制定教學(xué)計(jì)劃、安排教學(xué)過(guò)程中的一項(xiàng)較為復(fù)雜的工作，在高校教務(wù)管理工作中處于重要地位。高校在每學(xué)期末都要根據(jù)培養(yǎng)計(jì)劃和教學(xué)資源作出下學(xué)期的教學(xué)安排, 這主要體現(xiàn)在對(duì)課表的編排上。其中涉及的關(guān)鍵要素很多, 包括教師、班級(jí)、教室和授課時(shí)段等。根據(jù)排課總體目標(biāo)、約束條件、及優(yōu)先級(jí), 充分利用緊缺資源, 設(shè)計(jì)并實(shí)現(xiàn)高校課表安排系統(tǒng)。我校所面臨的問(wèn)題主要有：第一，渭水校區(qū)有包括從大一至大三三個(gè)年級(jí)的學(xué)生，20個(gè)學(xué)院近700個(gè)班級(jí)，教學(xué)任務(wù)繁重，課表安排難度較大；第二，校區(qū)地處偏僻,距市區(qū)較遠(yuǎn)，老師上課需乘車(chē)來(lái)回奔波，如果課表安排不當(dāng)，就會(huì)導(dǎo)致部分老師前往渭水乘車(chē)次數(shù)過(guò)多或在渭水逗留時(shí)間過(guò)長(zhǎng)；第三，基于學(xué)生的學(xué)習(xí)規(guī)律與習(xí)慣，應(yīng)根據(jù)課程的難度與重要性進(jìn)行課程時(shí)段的安排，若安排不當(dāng)，會(huì)導(dǎo)致學(xué)生的學(xué)習(xí)效果不佳；第四，為節(jié)省學(xué)校在校車(chē)往返方面的開(kāi)支，安排課表時(shí)應(yīng)盡量減少校車(chē)運(yùn)行車(chē)次。為此應(yīng)根據(jù)教學(xué)計(jì)劃和排課要求,綜合考慮教師、課程、班級(jí)和授課時(shí)段等因素，協(xié)調(diào)合理的編排課表,制作一個(gè)系統(tǒng)模型，根據(jù)這個(gè)模型使老師、同學(xué)和學(xué)校盡可能滿(mǎn)意，并且具有足夠的可行性和可變動(dòng)性。讓老師滿(mǎn)意，即讓每位老師一周內(nèi)前往渭水的乘車(chē)次數(shù)盡可能少，同時(shí)還要使每位老師在渭水逗留的時(shí)間盡可能少；讓學(xué)生滿(mǎn)意，即同一班級(jí)同一門(mén)課程在時(shí)間段上盡量間隔開(kāi)來(lái)，另外相對(duì)重要的課程應(yīng)盡量安排在較好的教學(xué)時(shí)段上；讓學(xué)校滿(mǎn)意，即節(jié)約學(xué)校開(kāi)支，使每周派往渭水的車(chē)次盡可能少。二、問(wèn)題的分析課表安排的主要任務(wù)是把各學(xué)院的課程匯總, 然后根據(jù)教學(xué)計(jì)劃或教學(xué)環(huán)節(jié)制訂全校各班級(jí)的課表。根據(jù)學(xué)校的實(shí)際情況和學(xué)校所面臨的問(wèn)題，可以將這類(lèi)題歸為以老師、學(xué)生和學(xué)校的滿(mǎn)意情況為多目標(biāo)的多約束的規(guī)劃問(wèn)題。為了使課表的編排準(zhǔn)確、合理、快速、高效, 充分利用學(xué)校資源，根據(jù)已知條件提出以下可行性要求：課程的優(yōu)先級(jí)：將大學(xué)所有課程分為三類(lèi)，1）公共必修課：多個(gè)學(xué)院開(kāi)設(shè)的課程，課程重要且開(kāi)設(shè)的班級(jí)數(shù)最多，這類(lèi)課盡量安排在最好時(shí)段；2）專(zhuān)業(yè)必修課：少數(shù)學(xué)院或一個(gè)學(xué)院開(kāi)設(shè)的課程，課程重要且開(kāi)設(shè)的班級(jí)數(shù)較多，這類(lèi)課盡量安排在較好時(shí)段；3）其他如專(zhuān)業(yè)選修課或公共選修課等：少數(shù)班級(jí)開(kāi)設(shè)的課程，課程相對(duì)簡(jiǎn)單，可以任意安排時(shí)段授課。課程時(shí)段的規(guī)定：將每天分為5個(gè)時(shí)段(上午兩個(gè),下午兩個(gè),晚上一個(gè))，并規(guī)定為：12節(jié)課為第一時(shí)段，34節(jié)課為第二時(shí)段……依此類(lèi)推。根據(jù)學(xué)生的學(xué)習(xí)效果及課程難度與重要性，將課程時(shí)段按有利程度分為五個(gè)等級(jí)，即第一時(shí)段第二時(shí)段第三時(shí)段第四時(shí)段第五時(shí)段。時(shí)間段的分配優(yōu)先級(jí)：周一至周五的白天共20個(gè)時(shí)段用來(lái)安排公共必修課和專(zhuān)業(yè)必修課及部分選修課,每天晚上及周六、 周日安排其他課程；先安排公共必修課表,在剩余的時(shí)間段內(nèi)安排各系專(zhuān)業(yè)課程，最后再安排選修課程；將相對(duì)重要的課程安排在較好時(shí)段。時(shí)間段的有效性：1）同一班級(jí)同一門(mén)課的兩次授課時(shí)間必須隔天，但相隔天數(shù)不宜超過(guò)兩天；2）一個(gè)老師一天內(nèi)的兩節(jié)課應(yīng)連排, 即盡量安排在同一天上午或同一天下午, 為教師上課提供方便，同時(shí)也減少了派往渭水的車(chē)次應(yīng)避免各種沖突:1）教室不沖突, 同一教室同一時(shí)間不能安排兩門(mén)課程，人數(shù)不能超過(guò)教室的最大容量；2）學(xué)生不沖突, 同一班級(jí)學(xué)生不能在同一時(shí)間上兩門(mén)或兩門(mén)以上課程；3）課程不沖突, 同一班級(jí)同一課程不能同一時(shí)間在不同地點(diǎn)上課；4）教師不沖突, 同一教師不能同一時(shí)間在不同地點(diǎn)上課。根據(jù)上述可行性要求，解決以下問(wèn)題：?jiǎn)栴}一：要求建立排課表的數(shù)學(xué)模型，先確定公共基礎(chǔ)課的課程數(shù)，并將這些課程數(shù)聯(lián)系到教師和學(xué)生的滿(mǎn)意程度，在優(yōu)化滿(mǎn)意程度的條件下，排出各個(gè)公共基礎(chǔ)課的授課區(qū)域，指定老師在班級(jí)授課時(shí)間段的區(qū)域，并讓老師在這個(gè)區(qū)域內(nèi)對(duì)不同的班級(jí)的授課時(shí)間段進(jìn)行排布。然后將專(zhuān)業(yè)課安插到未被占用的時(shí)間段上，最后是選修課。同時(shí)課程的安排原則是盡可能選擇在較好時(shí)段。問(wèn)題二：要求對(duì)渭水校區(qū)的課表進(jìn)行重排，利用統(tǒng)計(jì)學(xué)知識(shí)，對(duì)學(xué)校所有班級(jí)進(jìn)行抽樣，隨機(jī)抽取三個(gè)班級(jí)，并對(duì)這三個(gè)班級(jí)的課表重排，得到的課程與現(xiàn)有的課程進(jìn)行比較。問(wèn)題三：利用加權(quán)綜合評(píng)判法，對(duì)老師滿(mǎn)意度、學(xué)生滿(mǎn)意度和學(xué)校滿(mǎn)意度進(jìn)行加權(quán)綜合評(píng)價(jià)。其中老師滿(mǎn)意度從老師的滯留時(shí)間和老師的乘車(chē)次數(shù)方面考慮，學(xué)生滿(mǎn)意度以重要課程的安排的時(shí)間段好壞考慮，學(xué)校的滿(mǎn)意度以校車(chē)的車(chē)次考慮。問(wèn)題四：從學(xué)生的學(xué)習(xí)效率和老師的教學(xué)效果等方面，對(duì)學(xué)校的軟件設(shè)施、教學(xué)設(shè)施及運(yùn)輸設(shè)施等提出一些可行性建議。三、符號(hào)說(shuō)明 CS：課程集合 CSi：課程類(lèi)別的編號(hào)； Cj：按優(yōu)先級(jí)程度規(guī)定的課程編號(hào)； CR：時(shí)段集合；CRi：空閑時(shí)段集合；Rk：滿(mǎn)足課程要求的空閑時(shí)段；0：否； 1：是；T：間隔周期，單位：天；days：每周上課天數(shù)，單位：天；counts：周課時(shí)數(shù)；chapt：一次上課的節(jié)數(shù)；Tc：班級(jí)的受限一維數(shù)組；Tt：教師的受限一維數(shù)組；P：加權(quán)后的總滿(mǎn)意度；Pt：老師的滿(mǎn)意度；Ps：學(xué)生的滿(mǎn)意度；Pu：學(xué)校的滿(mǎn)意度。四、模型的假設(shè)，不考慮教室資源對(duì)課程安排的約束；；，每位老師可為幾組班級(jí)授課，每組班級(jí)由若干個(gè)班級(jí)組成。五、模型的建立與求解（一）問(wèn)題一：建立排課表的模型，并研制出排課表的軟件包。利用對(duì)課程添加優(yōu)先級(jí)屬性，再根據(jù)優(yōu)先級(jí)程度每個(gè)課程進(jìn)行排課，即解決死鎖問(wèn)題。同時(shí)也對(duì)時(shí)間段添加優(yōu)先級(jí)屬性，在每個(gè)課程排課的同時(shí)進(jìn)行時(shí)間段的選擇。根據(jù)實(shí)際情況和所的資料綜合分析實(shí)行對(duì)課程和時(shí)間段優(yōu)先級(jí)的確定，并利用C++或FORTRAN軟件對(duì)最優(yōu)課程最優(yōu)時(shí)間段的選擇。其步驟如下：系統(tǒng)模型的設(shè)計(jì)系統(tǒng)模型數(shù)據(jù)庫(kù)是排課系統(tǒng)中的一個(gè)很重要的組成部分。數(shù)據(jù)庫(kù)中幾個(gè)主要的表如下, 其中“* ”號(hào)指出了各個(gè)表的主鍵:班級(jí)表(* 班級(jí)號(hào)、專(zhuān)業(yè)號(hào)、入學(xué)時(shí)間、學(xué)制)；課程表(課程號(hào)、*課程名稱(chēng)、課程性質(zhì)、授課要求、學(xué)時(shí)、選課人數(shù)、上課教室)；教師表(教師號(hào)、*教師名、所帶課程、*所帶班級(jí)數(shù))；排課結(jié)果表(*課程名稱(chēng)、*上課時(shí)段、上課周次)。模型的建立(1)教務(wù)處匯總開(kāi)課計(jì)劃時(shí), 進(jìn)行課程優(yōu)先級(jí)分類(lèi)。分類(lèi)的依據(jù)為課程的難度和重要性（公共必修課、專(zhuān)業(yè)必修課、專(zhuān)業(yè)選修課和公共選修課）分別為CS1, CS2,CS3，在對(duì)于這些類(lèi)別根據(jù)該課程老師是否教授其他班課程和該課程課時(shí)的多少，將課程按優(yōu)先級(jí)順序分為C1,C2……Cj。(2)判斷課程集合CS中所有課程集合是否都安排完成, 若再?zèng)]有待排課程則安排完畢, 否則根據(jù)順序從CS 中選擇一類(lèi)課程,記作CSi。(3)在CSi 中選擇一門(mén)未排課程Cj,在時(shí)段集合CR中查找有空閑的時(shí)段CRi。(4)從時(shí)段集合CRi中按序列獲取一個(gè)時(shí)段Rk, 根據(jù)課程Cj的上課要求判斷該時(shí)段是否可用并在可用時(shí)間段內(nèi)選取最好時(shí)間段。 (5)時(shí)段Rk 可用時(shí), 課程Cj的班級(jí)和老師在時(shí)段Rk 的對(duì)應(yīng)記錄上未分配,