自動排課算法的分析論文

時間：2025-10-10 07:34:59 論文范文

自動排課算法的分析論文

　　摘要：隨著我國教育事1業的不斷發展，課程編排問題在很大的程度上影響著學校教學質量的提高。近些年來，政府對教育事業的投入也是逐年加大，可見對教育事業的重視。為了保證教學的質量，學校應該制定出嚴密合理和規范的課程安排，課程的編制過程是十分復雜和繁重的。下面我們就分析一下排課研究的意義，如今排課問題的現狀，以及現有的幾種排課算法，詳細地分析一下排課算法，

自動排課算法的分析論文

　　關鍵詞：自動排課；排課算法；自動排課算法

　　1.排課算法研究的意義

　　不管是小初高還是大學，靠老師教課來學習還是占主要的部分，這是培養學生的主要途徑。在學期開始的時候，學校都會給每人發一張課程表，學生還有老師都是按照課程表來進行計劃。一張課程表打印出來十分簡單，但是想把課程安排的緊湊合格，管理人員是需要下很大苦工的。新學期開始前學校的管理人員都要整理教學計劃，根據教學計劃下教學任務書，然后結合教學計劃和任務開始編排課程。這個編排過程是繁重而關鍵的，因為在這些教學調度過程中，不僅有大量繁瑣的數據整理工作，還有嚴謹思維的腦力勞動，需要填寫并打印大量的表格。

　　21世紀以來，信息技術突飛猛進，計算機排課慢慢取代了手工排課，這一技術的發明大大減輕了管理人員的工作量，而且采用計算機排課有利于學校對老師教學貢獻的評估，有利于優化學生的學習過程，也有利于學校領導決策更合理化，最為重要的是有利于學校教學質量的提高。

　　2.排課的現狀分析

　　在國外很早就有人研究課程編排問題，在 1962年，Gotlieb提出了一個課表問題的數學模型，他利用匈牙利算法解決了三維線性運輸問題。然后，人們對課表問題的算法、解的存在性等方面做了許多深入探討。近40年來，在計算機新技術的基礎上，人們又進行了不斷地嘗試，并取得一些成效。如1965年，Mihoc和Balas將課表公式化為了一個優化問題；Krawczk提出了一種線性編程的方法；Junginger將課表問題簡化為一個三維運輸問題。最近幾年，我們在課程編排方面已經取得了一些成績，但是對于多數學校而言，這種課表編排還不具備實用價值，只能在極為簡單的情況下才能實現。

　　然而，人們并沒有放棄研究課表問題，在九十年代，國外在課表問題研究方面的主要代表人物有加拿大Montreal大學的Jean Aubin和Jacques Ferland、印度的Vastapur大學管理學院的ArabindaTripathy等。我國對課表問題的研究是開始于80年代初期，具有代表性的是南京工學院的UTSS（A University Timetable Scheduling System）系統，清華大學的TISER（Timetable SchedulER）系統，大連理工大學的智能教學組織管理與課程調度等。

　　不管是國外研究還是國內的研究，從實際使用情況來看，國內外研制開發的軟件系統都不是很實用，比如，我國研制的系統，這些系統大多是模擬手工排課過程的。這種系統課表編排經實踐證明是不適合進行大量推廣的，因為它過于依賴各個學校的教學體制，限制性較大。另外，排課系統本來就是很復雜的，排課很難做到面面俱到，而且，每個學校都有其特殊性，如果是想要改動某個地方，有可能使全部的課程發生大調整，這就是說全校的課程都會發生變動，在實際應用中我們會發現這是很難實現的。

　　經過長時間的研究，目前解決課表方法的問題有：模擬手工排課法，圖論方法，拉格朗日法，二次分配型法等多種方法。在排課算法上，目前，人們已經研制出了幾種，比較流行的是自動排課算法和基于時間片優先級的排課算法。下面我們主要介紹詳細一下自動排課算法。

　　3.自動排課算法

　　3.1問題的簡化描述

　　設要安排的課程為{ C1 , C2 , ., Cn} ,課程的總數設為為n , 各門課程每周安排的次數(每次為連續的2 學時) 則設為{ N1 , N2 , ., Nn} ;每星期教學五天，也就是從星期一到星期五;每天最多只能安排4 次教學課程,就是1 ～ 2 節、3 ～ 4 節、5 ～ 6 節和7 ～ 8 節，在以下我們將4次教學課程分別稱第1 、2 、3 、4 時間段 .這樣，在這種假設下,每周的教學總時間的段數就是5 ×4 = 20 ，如以下這種表達方式:

　　n ≤20 , (1)

　　N = 6n， i =1， Ni ≤20. (2)

　　我們要思考的就是如何設計出恰當的數據結構和算法, 從而確定{ C1 , C2 , ., Cn } 中每個課程的教學應該占據的時間段,還得保證美個時間段只能由一門課程占據.

　　3.2主要數據結構

　　對于每一門課程,分配2 個字節的"時間段分配字" :{ T1 , T2 , ., Tn} . 每個時間段分配字(假設為Ti )的格式為:

　　Ti 的數據類型C 語言格式定義為:unsigned int . 以Ti的最高位來表示該課程是否有效，如果是0的話表示有效，1的話則表示無效。其他的被稱為課程分配位，每個分配位占連續的3 個位，這里的位就是bit，用來表示星期一到星期五所安排課程的時間段的值，0是表示當日沒有排課，1～4是表示課程所安排的相應的時間段，如果值大于4的話就表示無效。

　　這樣的話，小于32 768 (十六進制8000)就是有效的時間段分配字的值，大于等于32 768 的時間段分配字則是對應無效的課程。

　　3.3排課算法

　　在上述假設下,我們可以看出，自動排課算法的目標就是確定{ C1 , C2 , ., Cn} 所對應的{ T1 , T2 , ., Tn} .

　　假設成立的話,我們發現一共可有20 !/ (20 - N) !種排法 . 假設一共有4 門課,每門課一個星期上2 次,則N = 8 ,就是說這8 次課安排的方法就可能會有20 !/ (20 - 8) ! = 5 079 110 400 ,即50 多億種.在這種多可能性的情況下，排課必須有一個確定的排課標準，這樣才能節省時間，提高效率。一般情況下我們會采用輪轉分配法來進行:首先從星期一開始就按{ C1 , C2 , ., Cn} 中的相應順序來安排課程，每門課程安排1 次,之后再按這樣的順序繼續排后面的課程,直到所有課程的開課次數都與{ N1 , N2 , ., Nn} 中給定的值相符合. 在算法描述中用{ C[1 ] , C[2 ] , ., C[ n ]} 表示{ C1 , C2 , ., Cn} ，{ N1 , N2 , ., Nn}以及{ T1 , T2 , ., Tn}。

　　3.4算法的優缺點分析

　　優點：這個算法是以課程為中心的，然后進行搜索匹配，取得最先匹配的值；它具有占有空間少，運算速度快這兩個特點。

　　缺點：該算法無法對數據進行擇優選取，所以不無法合理分配學校的教學資源，并不能滿足一些特殊要求，比如說有些老師喜歡上午上課，有些老師偏向于組織集體上課；有些課程安排到上午會更合適些，有些課程不能安排到上午等。

　　參考文獻：

　　[1]蔡啟明,吳新民;基于中小學校園網的自動排課系統的分析和設計[J];電化教育研究;2003年03期

　　[2]祝勇仁;鄧勁蓮;胡獻華;張煒;;排課問題的一種遺傳算法適應度求解方法[A];第四屆中國軟件工程大會論文集[C];2007年

【自動排課算法的分析論文】相關文章：

電氣自動化論文06-08

案例分析論文11-27

案例分析論文07-15