方 剛， 徐 哲， 顧 坤

(北京航空航天大學(xué) 經(jīng)濟(jì)管理學(xué)院，北京 100191)

高校論文答辯排班模型與應(yīng)用

方 剛， 徐 哲， 顧 坤

(北京航空航天大學(xué) 經(jīng)濟(jì)管理學(xué)院，北京 100191)

論文答辯排班是高校教務(wù)管理中的重要任務(wù)，答辯排班結(jié)果的質(zhì)量直接影響評(píng)審的公平性。詳細(xì)分析高校論文答辯排班問(wèn)題的特性和情景，保證評(píng)審的公平性，考慮評(píng)審人在不同研究方向上擅長(zhǎng)程度的差異、評(píng)審人能參加答辯的時(shí)間安排要求、評(píng)審人與答辯人可能存在的師生關(guān)系、評(píng)審人評(píng)審工作量的限制、每個(gè)答辯組中答辯人數(shù)和評(píng)審人數(shù)的限制，等等因素，建立答辯分組和組內(nèi)評(píng)審指派的兩階段非線性整數(shù)規(guī)劃人員排班模型，對(duì)答辯排班問(wèn)題的復(fù)雜性進(jìn)行分析，基于lingo軟件中的分支定界算法對(duì)問(wèn)題進(jìn)行求解，通過(guò)實(shí)例驗(yàn)證了模型的可靠性和求解結(jié)果的合理性，較好地解決了高校答辯排班問(wèn)題。

教務(wù)管理； 答辯排班； 人員排班； 非線性規(guī)劃； 整數(shù)規(guī)劃

答辯排班是高校教務(wù)管理中的重要工作。近年來(lái)，隨著高校招生規(guī)模的擴(kuò)大，畢業(yè)生答辯排班工作變得復(fù)雜和困難，傳統(tǒng)的手工排班方式難以解決大規(guī)模答辯排班問(wèn)題，極大影響了答辯工作的順利開展。

人員排班問(wèn)題是NP-hard問(wèn)題[1]，已有相關(guān)文獻(xiàn)發(fā)表了諸多研究成果。文獻(xiàn)[2]將人員排班問(wèn)題分為：一般的人員排班問(wèn)題，大眾運(yùn)輸?shù)娜藛T排班問(wèn)題，航空公司的人員排班問(wèn)題。其中，一般的人員排班問(wèn)題是一種小型的人員排班問(wèn)題，如護(hù)士排班問(wèn)題[3-5]和作業(yè)人員排班問(wèn)題[6]等；而大眾運(yùn)輸?shù)娜藛T排班問(wèn)題[7]和航空人員的排班問(wèn)題則屬于大型的排班問(wèn)題，這類排班問(wèn)題往往計(jì)算復(fù)雜度高，排班過(guò)程復(fù)雜繁瑣。護(hù)士排班問(wèn)題是一類經(jīng)典的人員排班問(wèn)題，這類人員排班問(wèn)題要考慮的特殊因素是護(hù)士需要在不同的班次之間進(jìn)行輪換，這不僅擾亂了護(hù)士正常的作息時(shí)間，而且很可能影響其正常的家庭生活和對(duì)其自身的健康造成影響[8]。因此，如何通過(guò)合理安排護(hù)士的排班班次，使得她們既能完成應(yīng)有的工作，又能得到充分的休息，并能履行好其家庭角色是研究護(hù)士排班問(wèn)題的重點(diǎn)[9]。目前國(guó)內(nèi)外對(duì)護(hù)士排班問(wèn)題[10]的研究分為以下幾種。1)基于人員特性和排班班次的護(hù)士排班問(wèn)題的研究，這類問(wèn)題往往需要考慮一些人員特性(諸如人員的技能差異、人員間的配合默契程度等)和排班班次(如三班制、組別等)等因素。如文獻(xiàn)[11]通過(guò)調(diào)整排班班次的方法，一定程度上解決了護(hù)士班次頻繁變化的問(wèn)題。2)基于約束的護(hù)士排班問(wèn)題，主要是從護(hù)士排班問(wèn)題的約束條件入手，將其約束條件分為硬性約束[12-16]和非硬性約束[17-21]，如文獻(xiàn)[22]針對(duì)護(hù)士排班問(wèn)題建立了一個(gè)完整的帶有勞動(dòng)法規(guī)約束和考慮護(hù)士級(jí)別差異的問(wèn)題模型。文獻(xiàn)[23]將護(hù)士的工作滿意度以及個(gè)人偏好等因素條件考慮進(jìn)護(hù)士排班問(wèn)題中，一定程度上解決了護(hù)士排班問(wèn)題中護(hù)士滿意度以及個(gè)性化要求等問(wèn)題。3)基于護(hù)士排班問(wèn)題求解方法的研究，有數(shù)學(xué)規(guī)劃方法、智能算法、啟發(fā)式方法、元啟發(fā)式方法等[24-26]。

高校答辯排班問(wèn)題和護(hù)士排班問(wèn)題具有一定的相似性，目前這類排班問(wèn)題相關(guān)的研究文獻(xiàn)很少。文獻(xiàn)[27]在答辯排班問(wèn)題中利用時(shí)間位圖算法求解基于各種資源(評(píng)審人、答辯時(shí)間、答辯場(chǎng)地等)沖突的答辯排班問(wèn)題，并在此基礎(chǔ)上研發(fā)了一個(gè)研究生畢業(yè)答辯信息系統(tǒng)；文獻(xiàn)[28]綜合考慮師生關(guān)系約束、答辯評(píng)委的組成和時(shí)間安排約束等因素，建立了一個(gè)考慮答辯評(píng)委的工作強(qiáng)度以及評(píng)審時(shí)間連續(xù)性的雙目標(biāo)規(guī)劃模型。以上文獻(xiàn)一定程度上研究了答辯排班分組的問(wèn)題，但對(duì)于答辯排班問(wèn)題中評(píng)審的“公平性”原則未有涉及。本文認(rèn)為答辯排班問(wèn)題需要考慮評(píng)審人在不同研究方向上擅長(zhǎng)程度的差異、評(píng)審人與答辯人之間可能存在的師生關(guān)系、答辯周期短和時(shí)間緊湊等因素，滿足評(píng)審人對(duì)答辯時(shí)間安排的特殊要求，為了保證答辯質(zhì)量還要規(guī)定評(píng)審人的勞動(dòng)強(qiáng)度上限，等等，合理優(yōu)化答辯人和評(píng)審人分組和評(píng)審指派任務(wù)，實(shí)現(xiàn)答辯排班問(wèn)題中評(píng)審的“公平性”。

本文在現(xiàn)有的人員排班問(wèn)題研究的基礎(chǔ)上，充分考慮答辯排班問(wèn)題的特性,即排班工作的任務(wù)、內(nèi)容、技能差異、師生關(guān)系、人員的勞動(dòng)強(qiáng)度與時(shí)間等因素，分別以評(píng)審人和答辯人在研究方向上的“最大匹配度”以及“評(píng)審的公平性”為優(yōu)化目標(biāo)，建立一個(gè)兩階段的非線性整數(shù)規(guī)劃模型(分組階段以及組內(nèi)指派階段)，并基于lingo軟件中的分支定界算法對(duì)小規(guī)模答辯排班的模型進(jìn)行了求解，最后通過(guò)實(shí)際算例驗(yàn)證了本文建立的答辯排班模型的可靠性和求解結(jié)果的合理性。

1 問(wèn)題描述

高校答辯排班問(wèn)題中，每個(gè)答辯人的論文研究方向不盡相同，評(píng)審人對(duì)各個(gè)研究方向的熟悉程度也并非相同。為了提高答辯過(guò)程和結(jié)果的公正性和有效性，在進(jìn)行答辯排班時(shí)需要根據(jù)答辯人的論文研究方向進(jìn)行合理分組，并指派對(duì)此研究方向熟悉的評(píng)審人對(duì)其論文進(jìn)行評(píng)審。因此，基于某一研究方向，盡可能將具有相同或者相似研究方向的答辯人，以及對(duì)此研究方向盡可能熟悉的評(píng)審人分在一組。除此之外，還要考慮到評(píng)審人在時(shí)間安排上的特殊要求，以及考慮到答辯人與評(píng)審人之間可能存在的師生關(guān)系而不能安排在同一個(gè)答辯組，等等。具體而言，答辯排班問(wèn)題必須滿足以下要求：

1)答辯時(shí)間為教學(xué)規(guī)定的日期；

2)答辯場(chǎng)所為教學(xué)規(guī)定的地點(diǎn)；

3)每個(gè)答辯組的評(píng)審人數(shù)在一定的范圍內(nèi)；

4)每位評(píng)審人參加的答辯組數(shù)在一定的范圍內(nèi)；

5)每個(gè)答辯組參加答辯的人數(shù)在一定的范圍內(nèi)；

6)評(píng)審人參加答辯的時(shí)間與評(píng)審人要求的時(shí)間不相沖突；

7)評(píng)審人應(yīng)該對(duì)本組答辯人的研究方向盡可能熟悉；

8)每個(gè)答辯組中評(píng)審人與答辯人之間不存在師生關(guān)系；

9)每個(gè)評(píng)審人在一個(gè)時(shí)間段內(nèi)只能被安排在一個(gè)地點(diǎn)參加答辯工作；

10)每個(gè)答辯人有且只能參加某個(gè)答辯組(某個(gè)地點(diǎn)的某個(gè)時(shí)間段)的一場(chǎng)答辯。

2 建模分析

2.1 變量與參數(shù)說(shuō)明

1)決策變量。

(1)xltp為0-1變量，xltp=1表示評(píng)審人l被安排在第t時(shí)間段第p場(chǎng)地的答辯小組，反之為0；

(2)ystp為0-1變量，ystp=1表示答辯人s被安排在第t時(shí)間段第p場(chǎng)地的答辯小組，否則為0。

2)參數(shù)。

(1)blt為0-1變量，blt=1表示第l個(gè)評(píng)審人參加第t時(shí)間段的答辯，反之則為0；

(2)clm為等級(jí)變量，取值為0,1,2,3,4,5，數(shù)值越大表示評(píng)審人l對(duì)研究方向m越擅長(zhǎng)；

(3)asl為0-1變量，asl=1表示評(píng)審人l與答辯人s之間存在師生關(guān)系，反之則為0；

(4) ?1、?2分別為每個(gè)答辯小組評(píng)審人數(shù)的下限和上限;

(5)v為一個(gè)排班周期內(nèi)，每位評(píng)審人參加的答辯組數(shù)的上限；

(6)β1,β2分別表示每個(gè)答辯小組答辯人數(shù)的下限和上限;

(7)ms為答辯人s的論文研究方向m的編號(hào)；

(8)ktp為0-1變量，ktp=1表示第t時(shí)間段第p個(gè)答辯地點(diǎn)可以安排答辯，反之則為0。

2.2 建立模型

答辯排班模型的優(yōu)化目標(biāo)是在一個(gè)答辯周期內(nèi)，滿足一系列約束條件的限制，使得評(píng)審人和答辯人在研究方向上實(shí)現(xiàn)最大匹配，由此保證答辯的公正性和公平性。本文將答辯排班過(guò)程分為2個(gè)階段：答辯分組階段和組內(nèi)評(píng)審指派階段。答辯分組階段的任務(wù)是將所有的答辯人和所有的評(píng)審人分組，即綜合各組(某個(gè)地點(diǎn)和某個(gè)時(shí)間段)的評(píng)審人和答辯人在研究方向上實(shí)現(xiàn)最大匹配。組內(nèi)指派階段的任務(wù)是在已分組的情況下，在組內(nèi)依據(jù)研究方向匹配原則為每個(gè)答辯人指派若干名論文評(píng)審人。

2.2.1 建立答辯分組模型

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

xltp∈{0,1},ystp∈{0,1}。

(10)

式(1)為答辯分組階段的優(yōu)化目標(biāo)，即綜合所有答辯人被指派的論文評(píng)審人對(duì)其論文研究方向的熟悉程度賦值總和最大；

約束(2)為每組評(píng)審人數(shù)的上下限；

約束(3)為每位評(píng)審人參加的答辯組數(shù)的上限；

約束(4)為每組答辯人數(shù)的上下限；

約束(5)為評(píng)審人能夠在指派的時(shí)間參加評(píng)審與答辯，該時(shí)間與評(píng)審人的時(shí)間要求不沖突；

約束(6)為指派的評(píng)審人要擅長(zhǎng)答辯人論文研究方向，即擅長(zhǎng)程度的取值不能為0；

約束(7)為在同一答辯小組，評(píng)審人與答辯人不能存在師生關(guān)系；

約束(8)為每個(gè)評(píng)審人一個(gè)時(shí)間段只能被安排在一個(gè)地點(diǎn)參加答辯工作；

約束(9)為每個(gè)答辯人必須有且只能參加一個(gè)答辯組(某個(gè)時(shí)間的某個(gè)地點(diǎn))的答辯；

約束(10)為評(píng)審人和答辯人的決策變量。

2.2.2 建立組內(nèi)評(píng)審指派模型

定義Li′為第i組評(píng)審人的集合，Si′為第i組答辯人的集合，wi,ni分別為第i組評(píng)審人和答辯人的數(shù)量，zls=1表示評(píng)審人l被指派評(píng)審答辯人s的論文，zls=0表示不存在評(píng)審關(guān)系。組內(nèi)指派階段的任務(wù)是在第一階段答辯排班分組的基礎(chǔ)上，在各組內(nèi)依據(jù)研究方向匹配原則為每個(gè)答辯人指派若干名論文評(píng)審人。

(11)

(12)

(13)

zls∈{0,1}。

(14)

式(11)為組內(nèi)評(píng)審指派階段的優(yōu)化目標(biāo)，表示在組內(nèi)為每個(gè)答辯人指派若干名評(píng)審人，要求最大化評(píng)審的公平性，即組內(nèi)為所有答辯人指派的評(píng)審人在研究方向的擅長(zhǎng)值總和與最大擅長(zhǎng)值總和之間的偏差最小。c=5為常數(shù)，表示評(píng)審人和答辯人在研究方向的最大匹配值。若某個(gè)答辯組共有8名答辯人，為每位答辯人指派2位評(píng)審人，則針對(duì)每個(gè)答辯人而言，最大擅長(zhǎng)值總和為2×5=10，則該組的最大擅長(zhǎng)值總和為10×8=80。

約束(12)表示每名評(píng)審人至少評(píng)審1名答辯人的論文，至多評(píng)閱h名；

約束(13)表示必須為每個(gè)答辯人指派g名評(píng)審人；

約束(14)為答辯人與評(píng)審人評(píng)審關(guān)系的決策變量。

2.3 答辯排班結(jié)果的評(píng)價(jià)指標(biāo)

為了評(píng)價(jià)計(jì)算結(jié)果的合理性和可靠性，本文分別提出了2個(gè)階段計(jì)算結(jié)果的評(píng)價(jià)指標(biāo)。在答辯分組階段采用研究方向匹配度表示組內(nèi)擅長(zhǎng)答辯人研究方向的評(píng)審人數(shù)占該組總的評(píng)審人數(shù)的比例，該比例越大說(shuō)明分組結(jié)果越合理；在組內(nèi)評(píng)審指派階段采用評(píng)審匹配度更精準(zhǔn)地評(píng)價(jià)評(píng)審指派的合理性和有效性，用組內(nèi)為所有答辯人指派的評(píng)審人在答辯人研究方向上的擅長(zhǎng)程度值的總和與當(dāng)取最大擅長(zhǎng)值(取值為5)總和的比值表示，該比值越大說(shuō)明評(píng)審過(guò)程和結(jié)果越公平合理。

2.3.1 研究方向匹配度

(15)

式中，i為答辯小組的編號(hào)；qil定義第i組第l個(gè)評(píng)審人對(duì)組內(nèi)答辯人研究方向的擅長(zhǎng)關(guān)系取值，假設(shè)Ai為第i組答辯人研究方向的集合，Bi為第i組評(píng)審人研究方向的集合，則當(dāng)且僅當(dāng)qil∈Ai且qil∈Bi時(shí)，有qil=1，表示該評(píng)審人擅長(zhǎng)組內(nèi)某個(gè)答辯人的研究方向，否則，qil=0。

2.3.2 評(píng)審匹配度

(16)

式中，t為評(píng)審人的編號(hào)；cltms為評(píng)審人lt對(duì)答辯人s的研究方向ms的擅長(zhǎng)程度值；g表示為每個(gè)答辯人指派的評(píng)審人數(shù)。

2.4 問(wèn)題復(fù)雜度分析

在所有的人員排班問(wèn)題中，很少有研究答辯排班問(wèn)題求解的復(fù)雜性的文獻(xiàn)。本文試圖通過(guò)將該答辯排班分組階段問(wèn)題降解轉(zhuǎn)化為0-1背包問(wèn)題，以此來(lái)證明該答辯排班問(wèn)題是NP-hard。

(17)

(18)

(19)

(20)

(21)

x1tp∈{0,1},ystp∈{0,1}。

(22)

上述簡(jiǎn)化形式是一個(gè)0-1背包問(wèn)題，這表明任何0-1背包問(wèn)題都可以轉(zhuǎn)換為該答辯排班問(wèn)題的一個(gè)特例，即該答辯排班問(wèn)題是NP-hard。

3 算例研究

3.1 實(shí)例數(shù)據(jù)

本文的實(shí)例數(shù)據(jù)采集自北京某大學(xué)某次碩士答辯數(shù)據(jù)庫(kù)，描述了某個(gè)答辯周期內(nèi)有40位答辯人，共涵蓋了6個(gè)研究方向，有22位評(píng)審人可以參加本次評(píng)審工作，所有答辯人被安排在2d(4個(gè)時(shí)間段)內(nèi)進(jìn)行答辯，所有答辯被安排在3個(gè)場(chǎng)地進(jìn)行答辯；每個(gè)答辯小組的答辯人數(shù)限制在8～9人，評(píng)審人數(shù)限制在6人，在每個(gè)答辯組內(nèi)每個(gè)評(píng)審人最多可評(píng)閱3個(gè)答辯人的論文，每個(gè)答辯人的論文有且只能由2名評(píng)審人進(jìn)行評(píng)閱；考慮到評(píng)審人員的精力有限，為保證評(píng)審質(zhì)量，要求在一個(gè)答辯周期間，每個(gè)評(píng)審人最多可以參加3個(gè)答辯小組的評(píng)審工作。

所有采集的數(shù)據(jù)列于表1～5，其中：表1為評(píng)審人對(duì)答辯時(shí)間的要求；表2為評(píng)審人對(duì)研究方向的擅長(zhǎng)程度的賦值，要求每位評(píng)審人分別給出3個(gè)最擅長(zhǎng)的研究方向，并按照擅長(zhǎng)程度，賦值為1～5，在其余方向均賦值為0；表3為答辯人的研究方向，“1”表示為答辯人的研究方向，否則為“0”；表4為評(píng)審人和答辯人的師生關(guān)系表，表中共有10對(duì)有師生關(guān)系的答辯人和評(píng)審人；表5為答辯時(shí)間和答辯地點(diǎn)關(guān)系表，“1”表示某個(gè)答辯時(shí)間和某個(gè)答辯地點(diǎn)可安排答辯，“0”則表示不可安排。

表1 評(píng)審人對(duì)答辯時(shí)間要求表Tab.1 Arrangement of the reviewers’ time

表2 評(píng)審人對(duì)研究方向的熟悉程度表Tab.2 The extent to which the reviewers are familiar with the research

表3 答辯人研究方向表Tab.3 The research field of the respondents

表4 評(píng)審人和答辯人的師生關(guān)系表Tab.4 Relationships between respondents and reviewers

表5 時(shí)間地點(diǎn)關(guān)系表Tab.5 Relationship between time and place

3.2 計(jì)算結(jié)果

本文對(duì)答辯排班問(wèn)題的求解是在win7(CPU AMD A10-7300 Radeon R6,10 Compute Cores 4C+6G 1.90GHz)64位系統(tǒng)下，由lingo軟件中的分支定界算法計(jì)算得到的。

3.2.1 答辯分組階段的計(jì)算結(jié)果

表6是答辯排班分組階段的計(jì)算結(jié)果，本次答辯排班共分為5組，表6列出了每組的答辯時(shí)間、地點(diǎn)、研究方向、評(píng)審人和答辯人的相關(guān)信息。

表6 排班分組階段結(jié)果表Tab.6 Results of grouping stage

3.2.2 組內(nèi)指派階段的計(jì)算結(jié)果

答辯排班組內(nèi)評(píng)審指派階段以“評(píng)審的公平性”為目標(biāo)，在第一階段答辯分組的基礎(chǔ)上，進(jìn)行組內(nèi)的人員指派，得到最終的答辯排班結(jié)果。表7分別給出了各組的答辯時(shí)間、答辯地點(diǎn)、答辯人及其研究方向、為每個(gè)答辯人指派的評(píng)審人，最后還給出了每個(gè)答辯小組答辯排班結(jié)果的評(píng)價(jià)指標(biāo)值。

3.3.3 計(jì)算結(jié)果的評(píng)價(jià)

從表7可以看出答辯排班分組結(jié)果合理，研究方向匹配度均為100%，反映了在各個(gè)答辯排班分組中，每個(gè)評(píng)審人至少對(duì)組內(nèi)包含的一個(gè)研究方向是擅長(zhǎng)的；組內(nèi)指派結(jié)果中各組評(píng)審匹配度均在80%以上，其中第4組的答辯排班評(píng)審匹配度最高，達(dá)到97.5%，該組中答辯人的研究方向與指派的評(píng)審人的研究方向匹配程度高，僅有答辯人S34的論文為研究方向5，而指派的2名評(píng)審人對(duì)該研究方向非最擅長(zhǎng)；而第2組的評(píng)閱匹配度最低，為82.5%，這是因?yàn)樵摻M中有6名答辯人的論文為研究方向3，而為他們指派的2名評(píng)審人中至少有1名對(duì)該研究方向非最擅長(zhǎng)(評(píng)審人在各個(gè)研究方向上的擅長(zhǎng)程度值見表2)。

為了進(jìn)一步分析各組評(píng)審匹配度存在差異的原因，本文繪制了在不同研究方向上不同擅長(zhǎng)程度的評(píng)審人數(shù)分布圖(圖1)，以及在各個(gè)研究方向上答辯人數(shù)分布圖(圖2)。從圖1和圖2可以看出研究方向1(M1)的答辯人數(shù)最多，為10人，且十分擅長(zhǎng)該方向的評(píng)審人數(shù)也最多(D5表示擅長(zhǎng)程度值為5)，有8人，所以在滿足師生關(guān)系以及評(píng)審人時(shí)間要求等約束條件下，第5組的評(píng)審匹配度較高，達(dá)到95%；從表7可知，第2組中研究方向3的答辯人數(shù)較多(6人)。但從圖1和圖2可知，十分擅長(zhǎng)該方向的評(píng)審人數(shù)最少，為1人，因而該組的評(píng)審匹配度較低，為82.5%。

由以上分析可以看出，本次答辯排班結(jié)果滿足所有約束條件，該結(jié)果能夠充分發(fā)揮評(píng)審人的優(yōu)勢(shì)，使評(píng)審更加公平、客觀和精準(zhǔn)，由此可說(shuō)明本文建立的答辯排班模型能夠較好地解決答辯排班問(wèn)題。

圖1 在各個(gè)研究方向上不同擅長(zhǎng)程度的評(píng)審人數(shù)分布圖Fig.1 Number of reviewers in each research direction

圖2 在各個(gè)研究方向上答辯人數(shù)分布圖Fig.2 Number of respondents in each research direction 表7 組內(nèi)指派結(jié)果表Tab.7 Results of assignment stage

組號(hào)時(shí)間/地點(diǎn)答辯人評(píng)審人方向2方向4匹配度值1T1/P1S16L2,L14研究方向匹配度S17L2,L14d1:100%S26L11,L15評(píng)審匹配度S27L11,L15p1:90%S28L11,L13S29L7,L15S30L7,L13S31L7,L13方向1方向3方向62T1/P3S3L4,L19研究方向匹配度S19L18,L19d2:100%S20L4,L20評(píng)審匹配度S21L18,L22p2:82.5%S22L12,L20S24L4,L20S25L18,L22S36L12,L22方向3方向5方向63T2/P2S23L17,L20研究方向匹配度S32L5,L17d3:100%S33L17,L20評(píng)審匹配度S35L8,L20p3:96.25%S37L12,L22S38L8,L12S39L12,L22S40L8,L22方向1方向2方向54T3/P2S7L1,L9研究方向匹配度S11L5,L9d4:100%S12L11,L13評(píng)審匹配度S13L11,L13p4:97.5%S14L11,L13S15L5,L14S18L9,L14S34L5,L14方向15T4/P3S1L3,L5研究方向匹配度S2L1,L5d5:100%S4L1,L2評(píng)審匹配度S5L3,L11p5:95%S6L2,L21S8L1,L3S9L2,L11S10L5,L21

4 結(jié)論

本文針對(duì)高校畢業(yè)生答辯排班問(wèn)題，詳細(xì)分析了問(wèn)題的特性和情景，建立了答辯分組和組內(nèi)指派兩階段的非線性整數(shù)規(guī)劃排班模型，并且通過(guò)實(shí)例驗(yàn)證了模型的可靠性和求解結(jié)果的合理性，較好地解決了高校答辯排班工作復(fù)雜和準(zhǔn)確性差等問(wèn)題。除此以外，本文還探討了影響答辯排班問(wèn)題求解效果的因素，開展了部分相關(guān)因素的參數(shù)分析，研究結(jié)果表明：評(píng)審人和答辯人在各個(gè)研究方向上人數(shù)分布的匹配性、每個(gè)答辯組評(píng)審人數(shù)和答辯人數(shù)的取值范圍、評(píng)審人的時(shí)間要求、評(píng)審人與答辯人師生關(guān)系對(duì)的多少，等等，這些因素對(duì)排班結(jié)果的質(zhì)量有著重要的影響。由于篇幅所限，本文未列出這部分的研究過(guò)程。

由于答辯排班問(wèn)題屬于NP-hard問(wèn)題，針對(duì)大規(guī)模的畢業(yè)生答辯排班問(wèn)題，利用分支定界算法求解此問(wèn)題的時(shí)間過(guò)長(zhǎng)，因而設(shè)計(jì)一種有效的啟發(fā)式算法和智能優(yōu)化算法，既能保證解的質(zhì)量又能縮短求解的時(shí)間將是今后研究的重點(diǎn)。另外，還可以根據(jù)實(shí)際情況進(jìn)一步改進(jìn)答辯排班模型。例如，考慮到評(píng)審人的勞動(dòng)強(qiáng)度，可以增加評(píng)審人一天只能參加一個(gè)時(shí)間段答辯工作的要求，還可以根據(jù)實(shí)際情況對(duì)評(píng)審人在所有研究方向的擅長(zhǎng)程度賦值，而不僅僅對(duì)最擅長(zhǎng)的3個(gè)研究方向賦值。

[1] YAN S, YANG T H, CHEN Y C. A model and a solution algorithm for airline line maintenance manpower supply planning with multiple aircraft type maintenance certificates[J].Journal of the Chinese Institute of Engineers,2004,27 (5):719-729.

[2]BEASLEY J E, CAO B. A tree search algorithm for the crew scheduling problem[J]. European Journal of Operational Research, 1996, 94(3): 517-526.

[3]WARNER D M, PRAWDA J.A mathematical programming model for scheduling nursing personnel in a hospital[J]. Management Science, 1972, 19(4-part-1): 411-422.

[4]WARNER D M.Scheduling nursing personnel according to nursing preference:a mathematical programming approach[J]. Operations Research, 1976, 24(5): 842-856.

[5]MUSA A A, SAXENA U. Scheduling nurses using goal-programming techniques[J].IIE transactions,1984,16(3):216-221.

[6]BUFFA E S, COSGROVE M J, LUCE B J. An integrated work shift scheduling system[J].Decision Sciences,1976,7(4):620-630.

[7]WREN A, WREN D O. A genetic algorithm for public transport driver scheduling[J].Computers & Operations Research, 1995, 22(1): 101-110.

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

SHEN Yindong, SU Guanghui. Models and solutions based on switch rules for nurse scheduling with constraints[J].Computer Engineering & Science, 2010,32(7):99-103

[9]劉曉榮,陳國(guó)良,顧仁萍,等.護(hù)士排班決策支持系統(tǒng)模型的研究[J].解放軍護(hù)理雜志,2006,23(2):7-9.

LIU Xiaorong,CHEN Guoliang,GU Renping,et al.A study on nurse scheduling decision support system model[J].Nursing Journal of PLA,2006,23(2):7-9.

[10] VAN DEN BERGH J, BELIЁN J, DE BRUECKER P, et al. Personnel scheduling: a literature review[J]. European Journal of Operational Research, 2013, 226(3): 367-385.

[11]BRUCKER P, BURKE E K, CURTOIS T, et al. A shift sequence based approach for nurse scheduling and a new benchmark dataset[J]. Journal of Heuristics, 2010, 16(4): 559-573.

[12]AICKELIN U, BURKE E K, LI J P. An evolutionary squeaky wheel optimization approach to personnel scheduling[J].IEEE Transactions on Evolutionary Computation, 2009,13(2):433-443.

[13]AVRAMIDIS A N, CHAN W, GENDREAU M, et al. Optimizing daily agent scheduling in a multiskill call center[J].European Journal of Operational Research, 2010, 200(3):822-832.

[14]VALOUXIS C, GOGOS C, GOULAS G, et al. A systematic two phase approach for the nurse rostering problem[J].European Journal of Operational Research, 2012, 219(2):425-433.

[15]AICKELIN U, WHITE P. Building better nurse scheduling algorithms[J].Annals of Operations Research 2004,128:159-177.

[16]AL-YAKOOB S M, SHERALI H D.Mixed-integer programming models for an employee scheduling problem with multiple shifts and work locations[J].Annals of Operations Research, 2007,155(1):119-142.

[17]MORA M, MUSLIU N. Genetic algorithm for rotating workforce scheduling problem[C/OL].(2005-06-13).http://ieeexplore.ieee.org/document/1437685.

[18]MUSLIU N.Combination of local search strategies for rotating workforce scheduling problem[C].International Joint Conference on Artificial Intelligence.Edinburgh:Lawrence Erlbaum Associates LTD, 2005.

[19]NAUDIN E, CHAN P Y C, HIROUX M, et al. Analysis of three mathematical models of the staff rosteringproblem[J].Journal of Scheduling, 2012, 15(1):23-38.

[20]NI H, ABELEDO H.A branch-and-price approach for large-scale employee tour scheduling problems[J].Annals of Operations Research, 2007, 155(1):167-176.

[21]NISSEN V,GüNTHERM.Staff scheduling with particle swarm optimisation and evolution strategies[M]. Berlin:Springer Berlin Heidelberg,2009.

[22]沈吟東,陳名暉,鄧婕.利用矩陣向量化變換求解護(hù)士排班問(wèn)題[C/OL].(2008-07-02).http://www.docin.com/p-596489962.html.

SHEN Y D,CHEN M H,DENG J.Solving nurse scheduling problems aided by vectorization of matrices[C].(2008-07-02).http://www.docin.com/p-596489962.html.

[23]MAENHOUT B,VANHOUCKE M.Analyzing the nursing organizational structure and process from a scheduling perspective[J]. Health Care Management Science, 2013, 16(3): 177-196.

[24]HASEGAWA S,KOSUGI Y.Solving nurse scheduling problem by integer-programming-based local search[C/OL].(2016-10-08).http://ieeexplore.ieee.org/document/4274059.

[25]ISKEN M W,HANCOCK W M.A heuristic approach to nurse scheduling in hospital units with non-stationary, urgent demand, and a fixed staff size[J]. Journal of the Society for Health Systems, 1990, 2(2): 24-41.

[26]JAFARI H,SALMASI N.Maximizing the nurses′ preferences in nurse scheduling problem: mathematical modeling and a meta-heuristic algorithm[J]. Journal of Industrial Engineering International, 2015,11(3): 439-458.

[27]郝瑞.高校論文答辯系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)[D].太原:太原理工大學(xué),2007.

HAO R.Design and implementation of thesis defense system in colleges and universities[D].Taiyuan:Taiyuan University of Technology,2007.

[28]BUI L T, HOANG V.A multi-objective approach for master′s thesis committees scheduling using DMEA[M]. Berlin:Springer Berlin Heidelberg,2012.

A Thesis Oral Defense Scheduling Model and Its Application

FANG Gang, XU Zhe, GU Kun

(School of Economic Management, Beihang University, Beijing 100191, China)

Thesis oral defense scheduling is an important part of educational administration in colleges and universities. It has a direct influence on the fairness of review. Factors including characteristics and situations of oral defense scheduling, differences between reviewers who are in different research fields, time request of different reviewers, existing relationships between reviewers and respondents, the workload limit of reviewers who are assessing respondents′ thesis and the constraints that limit the number of reviewers and respondents of different groups have been considered. A two phase nonlinear integer programming model which includes group stage and reviewers′ assignment stage is built. Then a complexity analysis is executed which confirms that thesis oral defense scheduling problem is a NP-hard problem. The rationality and validity of the model are proved with an example using lingo mathematics software. It can be confirmed by the experiment that the model is helpful in improving the work efficiency of administrative staff and quality of defense management work.

educational administration management; oral defense scheduling problem; personnel rostering; nonlinear programming; integer programming

2016- 05- 10

國(guó)家自然科學(xué)基金資助項(xiàng)目(71571005，71271019)

方剛(1991-)，男，安徽省人，碩士研究生，主要研究方向?yàn)轫?xiàng)目管理與調(diào)度.

10.3969/j.issn.1007- 7375.2016.06.019

C93

A

1007-7375(2016)06- 0123- 08