課表編排問題

1、魅力數(shù)模 美麗力建力建學院第六屆數(shù)學建模競賽自信 堅強 團結 創(chuàng)新 論文題目 A題：課表編排問題 參賽編號 2009tm0502 監(jiān) 制：力建學院團委 數(shù)學建模協(xié)會（2010年11月）力建學院第六屆數(shù)學建模競賽承 諾 書我們仔細閱讀了第六屆建工數(shù)學建模竟賽的競賽規(guī)則。我們完全明白，在競賽開始后參賽隊員不能以任何方式（包括電話、電子郵件、網上咨詢等）與本隊以外的任何人（包括指導教師）研究、討論與賽題有關的問題。我們知道，抄襲別人的成果是違反競賽規(guī)則的, 如果引用別人的成果或其他公開的資料（包括網上查到的資料），必須按照規(guī)定的參考文獻的表述方式在正文引用處和參考文獻中明確列出。我們鄭重承諾，嚴格遵

2、守競賽規(guī)則，以保證競賽的公正、公平性。如有違反競賽規(guī)則的行為，我們愿意承擔由此引起的一切后果。我們的參賽編號為：2009tm0502 參賽隊員 (簽名) ：隊員1：李超隊員2：王超隊員3：秦允皓A題：課表編排問題摘 要 在學校的教務管理工作中，課程表的編排是一項十分復雜、棘手的工作。排課需要考慮時間、課程、教學區(qū)域、教室、院系、班級、教師等因素。我們經過討論后，對題目的要求進行分析，并認為可以規(guī)劃為優(yōu)化問題，可以將“教師”，“教室”“課程”作為優(yōu)化因素討論，以便分配到不同的時間段上，形成課表。 首先，確定各優(yōu)化因素之間的約束關系，根據(jù)各因素間約束關系的不同，將多重約束條件分為硬約束（強制要求）

3、和軟約束（用偏好系數(shù)表示），編制出各因素間的效用矩陣。其次，把課程隨機分配到課表上的每一個時間段，再以0-1規(guī)劃方法分別將教師、教室分配到課表上的不同時間段上。形成時間+課程+教師+教室的組合。最終，形成滿足要求的課表。 我們優(yōu)化、0-1規(guī)劃的方法，加入多重約束條件，引入了偏好系數(shù)，形成排課模型，根據(jù)題目給的數(shù)據(jù)，通過計算機編程，進行模型驗證，求出了所需課表。最后給出了教師、教室的配置建議。【關鍵詞】：優(yōu)化因素 排課模型 多重約束條件 0-1規(guī)劃1 問題的重述在學校的教務管理工作中，課程表的編排是一項十分復雜、棘手的工作。排課需要考慮時間、課程、教學區(qū)域、教室、院系、班級、教師等等因素。經優(yōu)化

4、的排課，可以在任意一段時間內，教師不沖突，授課不沖突，授課的班級不沖突，教室占用不沖突，且綜合衡量全校課表在宏觀上是合理的。如何利用有限的師資力量和有限教學資源，排出一個合理的課程安排結果，對穩(wěn)定教學秩序、提高教學質量有著積極的意義。某高校現(xiàn)有課程40門，編號為C01C40；教師共有25名，編號為T01T25；教室18間，編號為R01R18。具體屬性及要求見表1，表2，表3：課表編排規(guī)則：每周以5天為單位進行編排；每天最多只能編排8節(jié)課，上午4節(jié)，下午4節(jié)，特殊情況下可以編排10節(jié)課，每門課程以2節(jié)課為單位進行編排，同類課程盡可能不安排在同一時間。 你所要解決的問題：請你結合實際情況給出較為合

5、理的課表編排方案，分析你所給出的方案的合理性。對教師聘用，教室配置給出合理化建議。2 問題的假設 假設課程全部編排；假設是學生自選課程；假設在課程要求為強制要求（硬約束）；假設在教師屬性中，能勝任課程類別、周最大課時數(shù)為強制要求（硬約束）；對教室類別要求、上課時間要求用偏好程度衡量（軟約束）；假設所得4張課表中2張同時上課，上完后另外2張課表開始上課；假設課表內容由上課時間、教師、教室、課程組成。3 符號說明 主要符號 符號意義 A1A2A3A4A5 效用矩陣 Ti教師編號 Ri 教室編號 Ci 課程編號 偏好系數(shù)，表示教師對教室、教師對上課時間的偏好系數(shù)。 Si 課程表上時間段的編號 ST一

6、 為T一教師的要求課時數(shù) SCi 為Ci課程的要求課時數(shù) Si=Yij,T一,R一 課程表上某一時間段的課程-教師-教室組合 5模型準備根據(jù)關聯(lián)關系，刻畫每個關系的效果指標矩陣 根據(jù)分析，關聯(lián)關系有教師教室、教師課程、教師上課時間、課程教室、課程上課時間一共五個。 圖 1關聯(lián)關系示意圖（實線表示“硬約束”，虛線表示“軟約束”）依次建立A1，A2A4 七個效用矩陣。其中，為強制約束的有A2、A4。A2 矩陣：A2 = (aij)（刻畫i 教師上j 課程時的效果指標） 其中：aij = 0,1A4 矩陣：A4 = (aij)（刻畫i 課程在j 教室上時的效果指標） 其中：aij = 0,1偏好約束

7、有A1、A3。A1 矩陣A1 = (aij)（刻畫i 教師上j 教室的偏好效果指標） 其中：0 £ aij £1A3 矩陣A3 = (aij)（刻畫i 教師上j 時間段上課時的偏好效果指標） 其中：0 £ aij £1時間段Si 的編號每一張課表上有星期一到星期五，每天有4 個時間段（每兩個課時算一個時間段）。根據(jù)假設，假設題目需要同時排四張課程表，需要對四張課程表上的時間段都進行編號星期一 星期五 星期一 星期五 星期五上午1、2 節(jié) s1 s5 s6 s10 s20上午3、4 節(jié) s21 s25 s26 s30 s40下午5、6 節(jié) s41 s45

8、s46 s50 s60下午7、8 節(jié) s61 s65 s66 s70 s80表1 時間段編號對課程的處理當某一課程的課時數(shù)為奇數(shù)時，取大于他的最小偶數(shù)。對所有課程的課時數(shù)進行調整。新的課時數(shù)為Ki（i=1,240，即為40 位教師），原課程編號為Ci（i=1,240），Yij（i表示原課程的編號，j =1,2=（k1+k2+ki）/2）, 待排課程集合為Yij教師的課時數(shù)為。 課程的課時數(shù)為。 STi(k=1.2.25) SCi(i=1.2.40)å 6 模型的建立與求解 6.1 模型的建立 6.1.1 隨機分配課程到各個時間段 當課程的上課時間（上下午）要求為強制性約束時，分別選出

9、上下午的課程集合B上午=Y11Yij，B下午=Y21Yij。我們隨機 給中的每一個元素抽取一個上午的時間段，其中滿足的條件是，給中的每一個元素抽取一個下午的時間段。組成時間段課程(SiYij)組合。此時，Si= Yij（某一時間段對應的某一課程）。 6.1.2 給每一個時間段安排教師 6.1.2.1 結合教師、課程的Si根據(jù)教師Tk 對課程Cj 的效用矩陣A2，對i s 進行第二次賦值。當?shù)趇 個時間段上的初值是Yij，若aij=1,則Si =1,否則，Si =0。6.1.2.2 結合效用矩陣A3 的Si根據(jù)教師Tk 對上課時間的偏好A3 矩陣，對i s 進行第三次賦值，Si =Si -aij

10、。6.1.2.3 結合效用矩陣 A1 的 Si根據(jù)教師 Tk 對 si時間段上的課程所要求的教室的偏好 A1 矩陣，對 si進行第四次賦值， si=si-aij。最終得到 6.1.2.4 0-1 規(guī)劃目標是將Tk教師分配到不同的時間段上，約束條件是分配結果必須滿足教師的課時數(shù)要求。因此，問題轉化為求有約束條件的 0-1 規(guī)劃問題。目標函數(shù)：nnmax Z = åå ski ´ xkik=1i=1約束條件： 14所得解為：將教師安排到最優(yōu)的時間段，此時Si=Yij,Ti,Ri。若無最優(yōu)解，重回 6.1.1。6.1.3 為每一個時間段安排教室Ri教室對Si這一時間段的

11、效果指標：（1）該時間段的老師對教室的偏好（2）該時間段課程對教室的效果指標 6.1.3.1 結合效用矩陣 A4 的 Si根據(jù) si時段課程 Ci 對教室 Ru 的效果矩陣 A4，對 si進行第一次賦值，若 aij=1,則si=1,否則， si=0。6.1.3.2 結合效用矩陣 A1 的 Si根據(jù) si時段教師 Ti 對教室 Ru 的效用矩陣 A1，對 si進行第二次賦值，si=si-aij。最終得到：6.1.3.3 0-1 規(guī)劃目標是將Ru教師分配到不同的時間段上，約束條件是分配結果必須滿足同一間教室在四張課表的同一時間段不重復。因此，問題轉化為求有約束條件的 0-1 規(guī)劃問題。目標函數(shù)：

12、nnmax Z = åå sui ´ xuiu 1i=1約束條件： 所得解為：將教室安排到最優(yōu)的時間段，此時 s = = Yjk,Ti,Ri 。若無最優(yōu)解，重回 6.1.1。6.1.4 安排課程表將每個 Si的組合按照其編號讀入到表 1 中，得到最后的課程表。6.2 模型的求解6.2.1 為時間段編號并隨機分配課程充分考慮課程的時間要求（上午或下午），隨機分配課程，得到“時間段-課程”組合。分配示例見附錄一。由于，題目所給數(shù)據(jù)中，教師的總課時數(shù)小于課程總課時數(shù)，又經過計算，設定目標是為做成四張課表，其中兩張先行開課，上完后，另外兩張課表再開課。利用 0-1 規(guī)劃求

13、解，構造要用矩陣時，要考慮的是，教師對這一事件的偏好，教師對這一試點的課程的效用兩個因素，利用 excel 構造出效用矩陣。lingo 編程計算。程序代碼見附錄二。6.2.2 分配教師結合效用矩陣，為每個“時間段-課程”組合分配教師，得到“時間段-課程-教師”組合。6.2.3 分配教室結合效用矩陣，為每個“時間段-課程-教師”組合分配教室，得到“時間段-課程教師-教室”的最優(yōu)組合，從而得到所求課程表。課程表見附錄三6.2.3 編排課表將獲得的時間段編號+課程+教師+教室的組合編制成課表，編制結果參看附錄。其中，第一、二張課表同時開課，上完后，第三、四張課表開課。7 模型的檢驗與分析7.1 模型

14、的檢驗（偏好系數(shù)的檢驗=1 時，課表中教師所上課程滿足其對時間、教室類別的要求。當=0 時，課表中教師所上課程完全不滿足其對時間、教室類別的要求。另外，當教師和教室的偏好度越大時，0-1 規(guī)劃得到的效用最小，例如當偏好系數(shù)為 0.1 時，效用只有 38.2，當偏好系數(shù)為 0 時，為最大效用 40?？梢砸姷?，取極限，當偏好度為 1 時，無解。所以，我們的模型能較大程度地滿足教師、課程和教室的要求，給出最終符合條件的課表。7.2 模型的分析7.2.1 合理性分析模型充分考慮了課程、教室、教師等的相互約束，建立了關系關聯(lián)，并對約束采用0-1 規(guī)劃，確定出“時間段-課程-教師-教室”組合。同時，我們也

15、充分考慮了教師對教室和上課時間的偏好，建立了一個偏好系數(shù)可調的模型，使所得課表盡量滿足課程、教室、教師的各種屬性及要求，對教師聘用，教室配置給出合理化建議。但是，當四張課表一起開課時，無法達到教師的學時要求，即四張課表總需要周學時數(shù)為 160，但教師所能提供的只有 116 學時。計算機模擬表示，沒有最優(yōu)解。于是，我們做出以下調整：將題目簡化為兩張課表一同開課，待到上完課程后，再開另外兩張課表。7.2.2 幾種特殊情況的處理在模型準備的對課程的課時數(shù)的處理中，將奇數(shù)課時的處理成偶數(shù)，以便計算。在最終課表中，對排好的課表進行調動，奇數(shù)課時課程只上其要求的課時數(shù)，即找到課程所在時間段，隨機取消一節(jié)課

16、。如果所給課程的總課時數(shù)（取偶后的總和）大于教師的總課時數(shù)，則按照教師的課時數(shù)取 n 個課表，且 n 個課表同時開課。如果所給課程的總課時數(shù)（取偶后的總和）小于或等于教師的總課時數(shù)，則將課程安排到 n 個課表中，且 n 個課表同時開課。8 模型的評價8.1 模型的優(yōu)點引入了偏好系數(shù)，能較大程度地滿足教師、課程和教室的要求；建立了關聯(lián)關系，使模型建立更清晰、明確、具有條理性；用 0-1 規(guī)劃解決相互約束問題，形成“時間段-課程-教師-教室”組合，科學合理；逐步優(yōu)化，層層遞進，思路清晰，簡單易懂。充分考慮各個教師、教室、課程的要求，具有良好實用性。8.2 模型的缺點當課時數(shù)為奇數(shù)時，將其近似為偶數(shù)

17、計算，導致課表中所有時間未能充分利用；在隨機給每個時間段安排課程時，未能確立完善的分配方式；9 參考文獻(1) 韓中庚，數(shù)學建模方法與應用，北京：高等教育出版社，2005。(2) 張小紅、張建勛，數(shù)學軟件與數(shù)學實驗，北京：清華大學出版社，2004。附錄附錄一程序代碼：model: sets: teacher/file('偏好0.1.txt') /:teacheryaoqiu;kecheng/file('偏好0.1.txt') /:kechengyaoqiu; links(teacher,kecheng):c,x; endsetsdata: teacheryaoqiu=file(