基于整數(shù)規(guī)劃的答辯排班模型

摘 要：針對目前答辯越來越多的現(xiàn)象和答辯排班越來越復(fù)雜的問題，在對答辯排班的本質(zhì)和面臨問題進行系統(tǒng)分析后，應(yīng)用整數(shù)規(guī)劃建立了數(shù)學(xué)模型，以實現(xiàn)評審人員與答辯人員的合理安排，并通過實例驗證了模型的可靠性，從而極大地提高了答辯排班的效率。

關(guān)鍵詞：答辯排班 整數(shù)規(guī)劃 排班模型

中圖分類號：G4 文獻標識碼：A 文章編號：1673-9795（2014）05（a）-0111-02

答辯在現(xiàn)實生活中越來越多，尤其是在高校里，例如畢業(yè)論文答辯、優(yōu)秀生答辯等等。答辯排班就是將評審人與答辯人分組并安排好參與評審和答辯的時間。以往這些工作是由工作人員手工完成，但隨著答辯人數(shù)的增加，排班就變得十分復(fù)雜，往往會花費工作人員大量時間。

在排班問題的研究中，謝屹紅等對護士排班的問題進行了早期的研究，沈吟東等則在模型和算法上對護士排班的問題進行了深入探討。孫宏等建立的規(guī)劃模型并利用分階段指派算法研究了航空公司飛機排班問題。梁建波等建立了公交智能排班方法，并對其應(yīng)用進行了研究。馬榮昌、謝傳柳等在對呼叫中心話務(wù)量預(yù)測的基礎(chǔ)上設(shè)計了呼叫中心排班模型和算法。魏紅翠針對圖書館人員排班問題建立了優(yōu)化模型。前人對排班問題已經(jīng)有了較為深入的研究，但答辯排班的問題有自身的獨特性，在約束條件方面與其他排班問題有很大不同之處，而在這一方面尚未有人涉足。

本文即針對答辯排班問題，根據(jù)此類問題的特性，建立整數(shù)規(guī)劃模型，并對一高校畢業(yè)論文答辯進行分析和求解。

1 答辯排班問題

在答辯中，每個答辯人的研究方向會有所不同，每個評審人對各個方向的擅長程度也不同；答辯一般持續(xù)1～3天，有些甚至更長，每天的答辯分為上午、下午兩班，各評審人在此期間是否能參加評審也存在差異；答辯中，評審人可能與答辯人存在利害關(guān)系而影響答辯的公平性：以上這些都是答辯排班問題的特性。

答辯排班問題是一種在滿足時間、研究方向等約束條件下，實現(xiàn)將答辯人和評審人最優(yōu)分組的問題。在答辯排班問題中，約束條件主要包括評審人時間偏好要求、評審人熟悉答辯人所研究問題的要求、評審人與答辯人無利害關(guān)系的要求（簡稱背對背要求）、答辯時間場地的要求等。具體約束如下。

約束1：評審人有時間參加答辯評審。

約束2：評審人熟悉答辯人所研究的問題。

約束3：每個答辯小組的評審人數(shù)為固定值。

約束4：評審人與所評審的答辯人無利害關(guān)系（即背對背）。

約束5：每個答辯小組答辯人數(shù)不低于下限，也不超過上限。

約束：6：每個評審人評審組數(shù)不能超過上限。

約束7：任何班次答辯組數(shù)不能超過場地上限。

約束8：每個答辯人都要分入答辯小組，每一答辯小組都要安排時間答辯。

2 答辯排班模型

答辯排班模型的目標是在滿足各種約束條件下，使此次答辯能夠得到最好的評審，即讓更多擅長的評審人進行評審。

用表示評審人的集合，用表示答辯人的集合，用表示答辯所涉及方向的集合，表示答辯期間所有班次的集合，用表示答辯小組的集合。

如果評審人l有時間參加第i班次的評審，則，否則。表示評審人l對答辯方向j的擅長度，記為

。如果答辯人s涉及的方向為j，記，否則記。如果答辯人s與評審人l有利害關(guān)系，則，否則。表示答辯人s被分配到第k答辯小組，表示評審人l評審第k答辯小組，表示第k答辯小組在第i班次進行答辯。表示每個答辯小組的評審人數(shù)，分別表示每個答辯小組答辯人數(shù)的下限和上限，表示每個評審人評審組數(shù)的上限，表示答辯場地的上限。

其中為待求量，均為0-1變量，其余均為已知量?；谏鲜龆x的參數(shù)，可建立如下答辯排班模型：

（1）

約束1：

≤（2）

約束2：≤

（3）

約束3： （4）

約束4：

（5）

約束5：≤≤ （6）

約束6：≤ （7）

約束7：≤ （8）

約束8：

（9）

公式（1）為此模型的目標函數(shù)，即讓更多更擅長的評審人來評審答辯；公式（2）～（9）分別表示上文所述的約束條件1～8。

3 算例實驗

本文利用某大學(xué)工程碩士答辯排班作為算例進行實驗。此算例即對該校工程碩士論文答辯進行排班。

3.1 數(shù)據(jù)假設(shè)

（1）此例中評審人有22位，答辯人有40位，答辯所涉及的方向有3個，答辯要在兩天內(nèi)完成，所以答辯期間班次有4班。要求每個答辯小組的評審人數(shù)為5人，每個答辯小組答辯人數(shù)的下限為8人、上限為10人，每個評審人最多評審兩個答辯小組，答辯場地有5個。

（2）評審人答辯期間時間安排如表1所示。

表1中數(shù)字“1”表示評審人可以評審該班次答辯，“0”表示評審人沒有時間參加該班次的評審。

（3）評審人對答辯方向擅長程度如表2所示。

（4）答辯人s1～s13的答辯方向為j1，s14～s26的答辯方向為j2，s27～s40的答辯方向為j3。

4 結(jié)論

本文研究了答辯排班這一問題，在對問題進行綜合分析的基礎(chǔ)上建立了答辯排班模型，并通過一個實際算例證明了本模型的可靠性。此模型可以解決手工排班速度慢、準確性低的問題，并且兼顧評審準確性方面，大大提高了答辯排班的效率。但利用lingo中的分支定界算法求解大規(guī)模的答辯排班問題時效率還有待提高，答辯排班的智能算法會是以后的研究方向。

參考文獻

[1]謝屹紅.護士排班方式與護理人力資源的合理利用[J].中國實用護理雜志，2004（7）：65.

[2]彭剛藝，李亞潔，李茶香.連續(xù)排班模式對護士工作壓力影響的評價[J].中華護理雜志，2009（5）：407-409.

[3]張莉，彭剛藝，劉雪琴，蘇敏誼，程云，袁衛(wèi)紅，張秀平，嚴素芬.連續(xù)性排班模式有助于推動護士分層級管理[J].中華護理雜志，2009（2）：99-103，111.

[4]沈吟東，蘇光輝.帶約束的護士排班模型和基于變換規(guī)則的優(yōu)化算法[J].計算機工程與科學(xué)，2010（7）.

[5]王昌毓，沈吟東，陳凱.帶個人偏好的多級別護士排班問題研究[C]//第三十一屆中國控制會議論文集B卷，2012.

[6]孫宏，杜文.航空公司飛機排班問題的排序模型及算法[J].系統(tǒng)工程理論方法應(yīng)用，2002（3）：244-247.

[7]孫宏，杜文.航空公司飛機排班問題的分階段指派算法[J].系統(tǒng)工程學(xué)報，2003（2）：168-172.

[8]孫宏，杜文.飛機排班數(shù)學(xué)規(guī)劃模型[J].交通運輸工程學(xué)報，2004（3）：117-120.