基于整數(shù)規(guī)劃的排課模型研究

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

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

1.排課問題描述

1.1 排課問題要素

從本校的實際情況來看，排課主要考慮時間、班級、課程、教室和教師這五個要素。對這些要素進(jìn)行透徹的分析以及適當(dāng)?shù)念A(yù)處理，是建立排課模型的基礎(chǔ)。

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

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

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

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

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

1.2 排課問題約束條件

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

2.排課數(shù)學(xué)模型的建立

基于排課問題涉及的要素和約束條件建立如下排課問題的數(shù)學(xué)模型，主要對排課問題進(jìn)行嚴(yán)格的數(shù)量關(guān)系描述。

2.1 模型參數(shù)

3.結(jié)論

雖然我們給出了排課問題的目標(biāo)方程。但是，在不同的教學(xué)環(huán)境和不同的評價人的主觀因素下，很難確定各個目標(biāo)方程的權(quán)重。所以，對于課表優(yōu)劣的衡量仍然是一個模糊的概念。基于以上的情況，我們不需要尋找問題的最優(yōu)解，而應(yīng)該尋找滿足約束條件（F，C，L，R，T）的較優(yōu)組合，從中選擇一個作為較優(yōu)課表。后續(xù)我們將進(jìn)一步研究求解整數(shù)規(guī)劃問題的算法，使排課達(dá)到最優(yōu)組合。

參考文獻(xiàn)

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

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

[3]于艷東.基于遺傳模擬退火算法的智能組卷系統(tǒng)研究[碩士學(xué)位論文].內(nèi)蒙古大學(xué)，2011.

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

[5]基于分治和貪心相結(jié)合的排課算法研究[D].課程論文：青島農(nóng)業(yè)大學(xué)，2010.