基于整數規劃的排課模型研究

【摘要】根據本校教學資源的擁有情況，分析并提出了排課問題中的關鍵要素和約束條件，并基于此建立優化排課問題的數學模型，確定排課目標函數，主要對排課問題進行嚴格的數量關系描述。排課問題就是要在滿足一定約束條件下來協調各種教學資源之間的多維沖突，同時還要盡可能滿足一些軟性約束條件，從而使排出的課表更加合理，滿足人性化的需求。

整數規劃是一類要求問題中的全部或一部分變量為整數的數學規劃。如果所有變量都限制為整數，則稱為純整數規劃；如果僅一部分變量限制為整數，則稱為混合整數規劃。在數學規劃問題中，有些最優解可能是分數或小數，但對于某些具體問題，常要求結果必須是整數。本文采用整數規劃的方法建立排課問題的數學模型，優化高等院校的排課。

1.排課問題描述

1.1 排課問題要素

從本校的實際情況來看，排課主要考慮時間、班級、課程、教室和教師這五個要素。對這些要素進行透徹的分析以及適當的預處理，是建立排課模型的基礎。

（1）時間：排課問題中涉及的時間概念有學年、學期、周、天、時間段等。結合本校上課時間安排，只考慮按周來組織課表。每周5天教學日，每天10節課，分5個時間段，每2節課為一個時間段，每學期每周課表固定。

（2）課程：每門課程都有自己的編號、名稱、學時和學分等要求，每門課程每周需要安排的學時體現為課程的學分，1學分的概念就是在每個教學周安排1個學時；周學時為奇數的課程，排課時的實際周學時，取為比該課程周學時數大的最小偶數。

（3）教室：每個教室要有自己的編號和類別名稱（如普通教室、多媒體教室、微機室等）等，每個教室在同一時間只能上一門課，且滿足教室的類型和教室的容量等要求。

（4）班級：每個班級要有自己的編號和名稱，在同一時間一個班級只能上一門課程。

（5）教師：每個教師要有自己的工號和名稱，在同一時間一個教師只能上一門課程。

1.2 排課問題約束條件

因為排課問題要滿足多種約束條件，為了降低問題復雜度，可將排課的約束條件按照程度分為兩大類：硬性約束和軟性約束。前者是排課問題中必須遵循的原則，是衡量排課方案是否切實可行的標準，后者是排課過程中應當予以考慮，不一定必須滿足，但如果滿足可使排課結果更加合理，是衡量排課方案優劣的標準。

2.排課數學模型的建立

基于排課問題涉及的要素和約束條件建立如下排課問題的數學模型，主要對排課問題進行嚴格的數量關系描述。

2.1 模型參數

3.結論

雖然我們給出了排課問題的目標方程。但是，在不同的教學環境和不同的評價人的主觀因素下，很難確定各個目標方程的權重。所以，對于課表優劣的衡量仍然是一個模糊的概念?；谝陨系那闆r，我們不需要尋找問題的最優解，而應該尋找滿足約束條件（F，C，L，R，T）的較優組合，從中選擇一個作為較優課表。后續我們將進一步研究求解整數規劃問題的算法，使排課達到最優組合。

參考文獻

[1]鄂強金.基于混沌遺傳算法的排課問題研究[碩士學位論文].哈爾濱工程大學，2009.

[2]A.S.Asratian.Investigation of some mathematical model of scheduling theory[D].Moscow University，1980.

[3]于艷東.基于遺傳模擬退火算法的智能組卷系統研究[碩士學位論文].內蒙古大學，2011.

[4]C c Gotlieb.The Construction of Class-Teacher Time-Tables.1963.

[5]基于分治和貪心相結合的排課算法研究[D].課程論文：青島農業大學，2010.