[發明專利]一種在多約束條件下高效分班、排課的方法

無效

• 申請號: 201010594378.0
• 申請日: 2010-12-14
• 公開（公告）號: CN102222155A
• 公開（公告）日: 2011-10-19
• 發明（設計）人: 賈永鑫;祁秀花
• 申請（專利權）人: 賈永鑫
• 主分類號: G06F19/00
• 分類號: G06F19/00;G06F9/44
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明涉及到學校利用計算機分班、排課的方法，具體為一種在多約束條件下高效分班、排課的方法。

背景技術

1975年，S.Even等人論證了課程表問題是NP完全類問題。由于課程表問題所涉及的信息較多，并且求解課程表問題最優解的時間復雜性是課程表規模的指數級，所以一般采用求近似最優解的算法。在現實生活中，人們一般也只是要一個滿足各種條件的近似最優解，或者說滿意解，而不一定非要最優解不可。因此，對于課程表問題，關鍵不是如何找到最優解，而是如何提高解的滿意度。

傳統的人工進行排課，最令人擔心的問題就是出現教師資源沖突或場地資源沖突的情況，而且工作繁瑣，工作量巨大，尤其是規模較大的中學進行排課時出現的問題更多。現有的解決排課問題的方法主要是回溯法和遺傳算法，其中回溯算法是所有搜索算法中最為基本的一種算法，其采用了一種走不通就返回的思想作為其控制結構，其相當于采用了先根遍歷的方法來構造解答樹，可用于找解或所有解以及最優解；回溯算法對空間的消耗較少，當其與分枝定界法一起使用時，對于所求解在解答樹中層次較深的問題有較好的效果，但其在后繼節點可能與前繼節點相同的問題中使用，會產生循環。回溯算法應用在排課問題中，就是排不過去就調課，不能調課就倒退，而且記憶走過的路，以此節約時間，但由于回溯法是一種窮舉的辦法，空間消耗雖然小，可是時間開銷卻非常大，時間收斂慢，有時可能將好的課表錯過。遺傳算法則是從代表問題可能潛在解集的一個種群開始的，在每一代，根據問題域中個體的適應度大小挑選個體，并借助代表于自然遺傳學的遺傳算子進行組合交叉和變異，產生出代表新的解集的種群。這個過程導致種群像自然進化一樣，后生代種群比前代更加適應于環境，末代種群中最優個體經過解碼，可以作為問題的近似最優解。遺傳算法應用在排課問題中，是逐步接近設定目標，先按初始條件將課程排入到課表中，排滿之后根據后續條件逐步通過調課達到目標，進行逐步的進化，用遺傳算法排課空間消耗大，其是隨機產生很多課表之后根據條件檢查，不符合條件的放棄，留下來的再模仿遺傳做隨機改動，形成很多新的子課表，不符合條件的放棄，直到完成任務；其模擬自然選擇和遺傳，即優勝劣汰、適者生存，并沒有主動依據條件生成課表，存在一定的盲目性，這也必然導致大量時間的浪費。

發明內容

本發明的目的在于，針對現有技術中存在的技術缺陷，提供一種可在多個約束條件下，能夠節省空間和時間，有明確目的，可以主動的快速合理完成分班、排課任務的方法。

為達到以上目的，本發明采用的技術方案是：一種在多約束條件下高效分班、排課的方法，包括以下步驟：

(1)賦值：制定并公布學期課程列表，設定每門課程的場地范圍、一周課時量和課程允許的排課時段，給每個學生分配100分的選擇教師的總權分，學生選課時給每位任課老師給出分數；

(2)分班：統計學生選課信息，按以下規定分班：a.同一個行政班的選課相同的學生盡量分在一個教學班中，同時兼顧一個教學班來源的行政班數盡可能少；b.在場地和科目的實際要求下，每門選修課按權分從高到低吸收選課學生，組成新的教學班；c.每個教學班中設置一定比例的名額按b規定實施，剩余比例按a規定辦法實施；

(3)換算：根據設定數據和統計數據，換算所設置課程進行排課的難度系數z，并按從大到小的順序為其排序，其中z＝(s/t)+(k/w)；k為系數、w為場地范圍、s為一周課時量、t為課程允許的排課時段；

(4)排課：開始進行排課，在任課指定的場地，從符合任課時段的初始位置找能排的位置。不能排好的，在一個設定的時間內反復找合適的位置；依然不能排好的，做少量調課再排；若還不能滿足條件則跳過這一排課任務，接著排下一課程；完成最后一個排課任務后檢查所用課程是否排完；沒有排完的課程再通過補排課自動逐一按順序排課，若多次補排課依舊不能排好的；最后由人工半自動輔助排完所有的課。