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

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

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

中圖分類(lèi)號(hào)：G4 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1673-9795（2014）05（a）-0111-02

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

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

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

1 答辯排班問(wèn)題

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

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

約束1：評(píng)審人有時(shí)間參加答辯評(píng)審。

約束2：評(píng)審人熟悉答辯人所研究的問(wèn)題。

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

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

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

約束：6：每個(gè)評(píng)審人評(píng)審組數(shù)不能超過(guò)上限。

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

約束8：每個(gè)答辯人都要分入答辯小組，每一答辯小組都要安排時(shí)間答辯。

2 答辯排班模型

答辯排班模型的目標(biāo)是在滿(mǎn)足各種約束條件下，使此次答辯能夠得到最好的評(píng)審，即讓更多擅長(zhǎng)的評(píng)審人進(jìn)行評(píng)審。

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

如果評(píng)審人l有時(shí)間參加第i班次的評(píng)審，則，否則。表示評(píng)審人l對(duì)答辯方向j的擅長(zhǎng)度，記為

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

其中為待求量，均為0-1變量，其余均為已知量。基于上述定義的參數(shù)，可建立如下答辯排班模型：

（1）

約束1：

≤（2）

約束2：≤

（3）

約束3： （4）

約束4：

（5）

約束5：≤≤ （6）

約束6：≤ （7）

約束7：≤ （8）

約束8：

（9）

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

3 算例實(shí)驗(yàn)

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

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

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

（2）評(píng)審人答辯期間時(shí)間安排如表1所示。

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

（3）評(píng)審人對(duì)答辯方向擅長(zhǎng)程度如表2所示。

（4）答辯人s1～s13的答辯方向?yàn)閖1，s14～s26的答辯方向?yàn)閖2，s27～s40的答辯方向?yàn)閖3。

4 結(jié)論

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

參考文獻(xiàn)

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

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

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

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

[5]王昌毓，沈吟東，陳凱.帶個(gè)人偏好的多級(jí)別護(hù)士排班問(wèn)題研究[C]//第三十一屆中國(guó)控制會(huì)議論文集B卷，2012.

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

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

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