基于動態(tài)規(guī)劃的面試時間優(yōu)化模型概述

1、2015年天津商業(yè)大學(xué)數(shù)學(xué)建模競賽承 諾 書我們完全明白，在競賽開始后參賽隊員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與隊外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問題。我們知道，抄襲別人的成果是違反競賽規(guī)則的, 如果引用別人的成果或其他公開的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻(xiàn)的表述方式在正文引用處和參考文獻(xiàn)中明確列出。我們鄭重承諾，嚴(yán)格遵守競賽規(guī)則，以保證競賽的公正、公平性。如有違反競賽規(guī)則的行為，我們將受到嚴(yán)肅處理。我們參賽選擇的題號是（從A/B中選擇一項填寫）： B 參賽隊員 (打印并簽名) ：1. 葉恒揚 2. 施藝敏 3. 張一鳴 日期： 2015 年

2、4 月 27 日基于動態(tài)規(guī)劃的面試時間優(yōu)化模型摘 要現(xiàn)代信息社會中，求職面試已經(jīng)成為就業(yè)的一個重要環(huán)節(jié)?？茖W(xué)有效的組織和安排無論對面試者還是對組織單位、用人單位都是省時省力、節(jié)略成本的。因此如何緊湊、高效、省時地安排面試者按順序完成面試具有重要研究意義。本文綜合運用運籌學(xué)、統(tǒng)計學(xué)、經(jīng)濟(jì)學(xué)、平面設(shè)計、計算機(jī)軟件等知識，通過建立數(shù)學(xué)模型來求解面試的最短時間，進(jìn)一步規(guī)劃最優(yōu)的面試流程。針對問題一，通過分析給定的面試階段順序和不允許插隊等特性，為滿足面試時間最短，建立了求解最短時間的0-1非線性規(guī)劃模型（見公式（1），然后利用Lingo11.0程序（見附錄1），求解出最短面試時間為100分鐘，最佳安排

3、順序為：，同學(xué)最早9:40一起離開。接著利用AutoCAD2007分別繪制出同學(xué)和面試官的面試過程時間圖（見圖12）。在此基礎(chǔ)上，利用Excel2007制作出同學(xué)的具體面試流程表：秘書副主管主管經(jīng)理開始時刻結(jié)束時刻開始時刻結(jié)束時刻開始時刻結(jié)束時刻開始時刻結(jié)束時刻同學(xué)48:008:088:088:188:188:338:338:41同學(xué)18:088:218:218:368:368:568:569:01同學(xué)28:218:318:368:568:569:149:149:20同學(xué)58:318:458:569:079:149:229:229:31同學(xué)38:459:059:079:239:239:339:

4、339:40針對問題二，同樣滿足給定的面試階段順序、不允許插隊和同學(xué)們約定一起離開等特性，對于未知的m名同學(xué)和n個階段構(gòu)成的面試時間矩陣，以最后一名同學(xué)面試的結(jié)束時間最早為目標(biāo)函數(shù)，以不允許插隊和同一面試官同一階段只能面試一個同學(xué)為約束條件，建立求解面試最短時間的動態(tài)規(guī)劃模型（見公式（15），并由Matlab生成隨機(jī)面試時間矩陣（面試由5名同學(xué)和5階段組成）和（面試由6名同學(xué)和5階段組成），由Lingo程序（見附錄3、5）求解出最短面試時間分別為101分鐘和135分鐘，比未經(jīng)優(yōu)化按原始順序面試的110分鐘和142分鐘分別縮短9分鐘和7分鐘，接著運用AutoCAD2007分別繪制出優(yōu)化前后的面試

5、過程時間圖（見圖313）。同樣，運用Excel2007制作出同學(xué)的具體面試流程表(見表36)。優(yōu)化后的面試時間較未優(yōu)化的面試時間有所縮短，驗證了模型的正確性，也是對模型的檢驗。針對問題三，基于第一問和第二問的建模思想，同時進(jìn)一步考慮到同學(xué)和面試官的等待過程是對時間成本的極大消耗，摒棄現(xiàn)有面試模式中同學(xué)同時到達(dá)再一起離開這一傳統(tǒng)模式，建立無論是對于同學(xué)還是面試官只要完成自己的面試便可離開的新模式，基于問題一的已知面試時間矩陣，繪制出同學(xué)和面試官的面試時間圖（圖1和圖11），并分別繪制同學(xué)和面試官的具體面試時間流程表（見表78），同學(xué)和面試官可根據(jù)時間流程表提前安排行程和合理利用等待時間，節(jié)約時間

6、見下表： 【關(guān)鍵字】 面試時間，排序，動態(tài)規(guī)劃，優(yōu)化模型，lingo軟件一、問題的提出與重述 現(xiàn)代信息社會中，求職面試已經(jīng)成為就業(yè)的一個重要環(huán)節(jié)。在面試的組織實施過程中，一個常見的基本問題是如何緊湊、高效、省時地安排面試者按順序完成面試，科學(xué)有效的組織和安排無論對面試者還是對組織單位、用人單位都是省時省力、節(jié)略成本的。面試過程的安排無疑要根據(jù)面試者的基本情況、用人單位的要求與面試設(shè)置項目有直接關(guān)系。比較典型的情況是用人單位或組織單位設(shè)置了幾個階段的面試，參加面試的人員必須逐一完成各個階段的面試才能錄取，另外由于面試者各自的學(xué)歷、專業(yè)背景等因素的差異，每個面試者在每個階段的面試時間也有所不同。對

7、上述面試情況，作簡化和抽象后可描述為以下數(shù)學(xué)問題。問題一 某高校畢業(yè)生中有5名同學(xué)到一家公司參加四個階段的面試。面試程序上，要求每個同學(xué)都必須從第一階段面試開始，然后進(jìn)行第二階段面試,，最后進(jìn)行第四階段的面試，并且在任何一個階段5名同學(xué)的順序是一樣的,假定開始面試時間是早晨8:00，建立的數(shù)學(xué)模型，求出他們最早離開公司的時間。問題二 假設(shè)該高校畢業(yè)生中有m名同學(xué)到一家公司應(yīng)聘，按類似于問題1的面試規(guī)則需要參加該公司人事部門組織的n個階段的面試。由于m名同學(xué)的專業(yè)背景不同,所以每人在每個階段的面試時間也不同，這m名同學(xué)約定他們?nèi)棵嬖囃暌院笠黄痣x開公司。請建立數(shù)學(xué)模型，以此討論他們最早何時能離開

8、該面試的公司?問題三 試設(shè)計一種更科學(xué)、更公平、更合理的面試模式，并給出理由。2、 基本假設(shè)1假設(shè)面試者從一個階段到下一個階段參加面試的時間間隔為0；2假定面試者都能在8：00準(zhǔn)時到達(dá)面試地點；3假定可以任意排列面試者的面試順序；4假定面試者均會參加每個階段的面試，而且沒有中途退場的情況出現(xiàn)；5假設(shè)參加面試的求職者都是平等且獨立的，即他們面試的順序與考官無關(guān)。三、主要變量的符號說明為了便于描述問題，本文將問題中涉及的主要變量用下表符號來表示： 表一 主要變量符號說明一覽表符號表示的意義完成全部面試所花費的最少時間第名同學(xué)參加第階段面試的開始時刻第名同學(xué)參加第階段面試需要的時間第名同學(xué)參加第階段

9、面試的開始時刻第名同學(xué)是否排在第名同學(xué)前面(1表示是，0表示否)面試時間矩陣 四、問題分析 問題是“面試如何安排才能盡早結(jié)束”，根據(jù)題意可知，因為面試者各自的學(xué)歷、專業(yè)背景等因素的差異，每個面試者在每個階段的面試時間有所不同，這樣就造成了按某種順序進(jìn)入各面試階段時不能緊鄰順序完成，即當(dāng)面試正式開始后，在某個面試階段，某個面試者會因為前面的面試者所需時間長而等待，也可能會因為自己所需時間短而提前完成。因此本問題實質(zhì)上是求面試時間總和的最小值問題，其中一個面試時間總和就是指在一個確定面試順序下所有面試者按序完成面試所花費的時間之和，這樣的面試時間總和的所有可能情況則取決于面試者的面試順序的所有排列

10、數(shù)。從而原問題可等價于:求所有可能的面試順序中，使花費總時間最少的那種順序，并求出所花費的總時間。就問題一而言，實際上，這個問題就是要安排5名面試者的面試順序，使完成全部面試所花費的時間最少。通過分析給定的面試階段順序和不允許插隊等特性，為滿足面試時間最短，可建立求解最短時間的0-1非線性規(guī)劃模型，然后利用lingo11.0程序求解出最短面試時間以及最佳安排順序。最后根據(jù)模型結(jié)果可得出同學(xué)最早離開面試地點的時間。另外我們可以利用AutoCAD2007分別繪制出同學(xué)和面試官的面試過程時間圖，在此基礎(chǔ)上，還可以利用Excel2007制作出同學(xué)的具體面試流程表；就問題二而言，實際上就是要安排m名面試

11、者的面試順序，使完成全部面試階段n所花費的時間最少。同樣滿足給定的面試階段順序、不允許插隊和同學(xué)們約定一起離開等特性，我們可以嘗試建立求解面試最短時間的動態(tài)規(guī)劃模型，并可由Matlab生成隨機(jī)面試時間矩陣，然后由Lingo程序求解出最短面試時間，再運用AutoCAD2007分別繪制出優(yōu)化前后的面試過程時間圖。同樣，可運用Excel2007制作出同學(xué)的具體面試流程表。最后可以比較一下優(yōu)化后的面試時間較未優(yōu)化的面試時間的改變，從而驗證模型的正確性，也是對模型的檢驗。就問題三而言，需要我們從科學(xué)性、公平性、合理性三個方面對面試模式進(jìn)行改進(jìn)。我們可以通過查閱資料了解當(dāng)前面試模式中存在的普遍性不合理現(xiàn)象

12、，然后針對不合理現(xiàn)象進(jìn)行面試模式的改進(jìn)。五、模型的建立與求解1. 問題一建模和求解（1）模型建立記為第名同學(xué)參加第階段面試需要的時間(已知)，令表示第名同學(xué)參加第階段面試的開始時刻(不妨記早上8：00面試開始為0時刻)為完成全部面試所花費的最少時間。 則有優(yōu)化目標(biāo)為： （1）面試時間矩陣：約束條件： 對時間先后次序進(jìn)行約束，即每人只有參加完前一個階段的面試后才能進(jìn)入下一個階段： （2） 每個階段同一時間只能面試1名同學(xué)，用0-1變量表示第名同學(xué)是否排在第名同學(xué)前面(1表示是，0表示否),則： , （3） , （4） 可以將非線性的優(yōu)化目標(biāo)改寫為如下線性優(yōu)化目標(biāo)： （5） （6） （7） （8）

13、 （9）這個問題的0-1非線性規(guī)劃模型1為: （10） ， （11） ， （12） ， （13） ， （14）（2） 模型求解根據(jù)以上所建的模型，我們可編出Lingo程序（詳見附錄1），部分運行結(jié)果見圖1（詳細(xì)結(jié)果請見附錄2）：圖1 問題一部分運行結(jié)果（3） 結(jié)果分析由變量的最優(yōu)解值為100.00000，知最短時間為100分鐘，即5名同學(xué)一起離開公司的時間是9：40。 由變量Y(S1,S2)的最優(yōu)解值為0.000000，知student1排在student2之前，即1號同學(xué)排在2號同學(xué)之前。  由變量Y(S1,S3)的最優(yōu)解值為0.000000，知student1排在stu

14、dent3之前，即1號同學(xué)排在3號同學(xué)之前。  由變量Y(S1,S4)的最優(yōu)解值為1.000000，知student4排在student1之前，即4號同學(xué)排在1號同學(xué)之前。由變量Y(S1,S5)的最優(yōu)解值為0.000000，知student1排在student5之前，即1號同學(xué)排在5號同學(xué)之前。 由變量Y(S2,S3)的最優(yōu)解值為0.000000，知student2排在student3之前，即2號同學(xué)排在3號同學(xué)之前。 由變量Y(S2,S4)的最優(yōu)解值為1.000000，知student4排在student2之前，即4號同學(xué)排在2號同學(xué)之前。由變量Y(S2,S5)的最優(yōu)解值

15、為0.000000，知student2排在student5之前，即2號同學(xué)排在5號同學(xué)之前。 由變量Y(S3,S4)的最優(yōu)解值為1.000000，知student4排在student3之前，即4號同學(xué)排在3號同學(xué)之前。由變量Y(S3,S5)的最優(yōu)解值為1.000000，知student5排在student3之前，即5號同學(xué)排在3號同學(xué)之前。由變量Y(S4,S5)的最優(yōu)解值為0.000000，知student4排在student5之前，即4號同學(xué)排在5號同學(xué)之前。根據(jù)模型得出的結(jié)果，我們可以作出整個面試過程的圖解如下：圖2 整體面試過程（同學(xué)）圖3 整體面試過程（面試官）根據(jù)圖解,我們可做出這五

16、位同學(xué)的具體面試安排如下（不妨設(shè)8：00為0時刻）： 第一個進(jìn)行面試的是4號同學(xué)。4號同學(xué)在0時刻開始秘書面試，用時8分鐘；秘書處面試結(jié)束后去副主管處進(jìn)行面試，用時10分鐘；接著去主管處面試，用時15分鐘；最后去經(jīng)理處面試，用時8分鐘；最終，4號同學(xué)在8：41完成整個面試過程。 第二個進(jìn)行面試的是1號同學(xué)。1號同學(xué)在8分鐘時刻開始秘書面試，用時13分鐘，此時4號同學(xué)已經(jīng)完成副主管面試；1號同學(xué)直接進(jìn)行副主管面試，用時15分鐘，此時4號同學(xué)已經(jīng)完成主管面試；1號同學(xué)直接進(jìn)行主管面試，用時20分鐘，此時4號同學(xué)已經(jīng)完成經(jīng)理面試；1號同學(xué)開始經(jīng)理面試，用時5分鐘；最終，1號同學(xué)在9:01完成整個面試

17、過程。第三個進(jìn)行面試的是2號同學(xué)。2號同學(xué)在21分鐘時刻開始秘書面試，用時10分鐘完成秘書面試，此時1號同學(xué)還未完成副主管面試；2號同學(xué)等待5分鐘后進(jìn)行副主管面試，面試用時20分鐘，此時1號同學(xué)剛好結(jié)束主管面試；2號同學(xué)直接進(jìn)行主管面試，用時18分鐘，此時1號同學(xué)已經(jīng)完成經(jīng)理面試；2號同學(xué)直接進(jìn)行經(jīng)理面試，用時6分鐘。最終，2號同學(xué)在9:20完成整個面試過程。第四個進(jìn)行面試的是5號同學(xué)。5號同學(xué)在31分鐘時刻開始秘書面試，用時14分鐘完成秘書面試，此時2號同學(xué)還未完成副主管面試；5號等待11分鐘后進(jìn)行副主管面試，面試副主管用時11分鐘，副主管面試完，2號同學(xué)還未完成主管面試；5號同學(xué)等待7分鐘

18、后開始主管面試，用時8分鐘，此時2號同學(xué)已經(jīng)完成經(jīng)理面試；5號同學(xué)直接進(jìn)行經(jīng)理面試，用時9分鐘。最終，5號同學(xué)在9:31完成整個面試過程。最后進(jìn)行面試的是3號同學(xué)。3號同學(xué)在45分鐘時刻開始秘書面試，用時20分鐘完成秘書面試，此時5號同學(xué)還未完成副主管面試；3號同學(xué)等待2分鐘后開始面試副主管，用時16分鐘，此時5號同學(xué)已經(jīng)完成主管面試；3號同學(xué)直接開始主管面試，用時10分鐘，此時5號同學(xué)已經(jīng)完成經(jīng)理面試；3號同學(xué)直接進(jìn)行經(jīng)理面試，用時7分鐘，最終，3號同學(xué)在9:40完成整個面試過程。為了更加直觀地表示整個面試過程的時間安排，我們作出面試的時間安排表如下：表2 面試時間安排表秘書副主管主管經(jīng)理開

19、始時刻結(jié)束時刻開始時刻結(jié)束時刻開始時刻結(jié)束時刻開始時刻結(jié)束時刻同學(xué)48:008:088:088:188:188:338:338:41同學(xué)18:088:218:218:368:368:568:569:01同學(xué)28:218:318:368:568:569:149:149:20同學(xué)58:318:458:569:079:149:229:229:31同學(xué)38:459:059:079:239:239:339:339:40至此，模型所得五位同學(xué)的面試順序為，以此順序依次進(jìn)行面試，總計用時最短，為100分鐘，即這五位同學(xué)最早可在9:40離開公司。2. 問題二建模和求解 對于問題一，所建立的數(shù)學(xué)模型是針對具體面

20、試者與面試階段的特定模型。而問題二需要針對面試者與面試階段不確定建立相應(yīng)的數(shù)學(xué)模型，進(jìn)而求出最短面試時間。為此，借助問題一的建模思想，將模型進(jìn)一步推廣，假設(shè)有m名面試者，n個面試階段，建立求解最小面試時間的數(shù)學(xué)模型。（1）模型建立 實際上，這個問題就是要安排m名面試者的面試順序，使完成全部面試所花費的時間最少。 面試時間矩陣： 優(yōu)化目標(biāo)： （15） 約束條件： 時間先后次序約束(每人只有參加完前一個階段的面試后才能進(jìn)入下一個階段) （16） 每個階段j同一時間只能面試1名同學(xué)：用0-1變量表示第名同學(xué)是否排在第名同學(xué)前面(1表示是，0表示否)，則, （17）, （18） 可以將非線性的優(yōu)化目標(biāo)

21、改寫為如下線性優(yōu)化目標(biāo)： （19） s.t. （20） （21） （22） 則這個問題的0-1非線性規(guī)劃模型為： （23） s.t. ， （24） ， （25） ， （26） ， （27）（2） 模型求解 根據(jù)模型，我們可編寫LINGO程序如下：Model:SETS:! Person = 被面試者集合，Stage = 面試階段的集合;Person/1.m/;Stage/1.n/;! T = 已知的面試所需要的時間，X = 面試開始時間;PXS(Person,Stage): T, X;! Y(i,k) = 1: k排在i前，0：否則;PXP(Person,Person)|&1 #LT#

22、&2: Y;ENDSETSDATA: T=;ENDDATAobj min =MAXT;! MAXT是面試的最后結(jié)束時間;MAXT >= max(PXS(i,j)|j#EQ#size(stage): x(i,j)+t(i,j);! 只有參加完前一個階段的面試后才能進(jìn)入下一個階段;for(PXS(i,j)|j#LT#size(stage):ORDERx(i,j)+t(i,j)<x(i,j+1);! 同一時間只能面試1名同學(xué);for(Stage(j): for(PXP(i,k):SORT1x(i, j)+t(i, j)-x(k,j)<MAXT*Y(i,k) ); for(P

23、XP(i,k):SORT2x(k,j)+t(k,j)-x(i, j)<MAXT*(1-Y(i,k) ););for(PXP: bin(y);End 具體情況中，只需將面試人數(shù)m、面試階段n以及初始時間矩陣的具體值代入程序即可得最優(yōu)面試順序以及最短面試時間。（3）結(jié)果分析依照題設(shè)要求，我們利用Excel隨機(jī)生成5人面試5階段的面試時間和6人面試5階段的面試時間進(jìn)行模型結(jié)果分析，并對隨機(jī)產(chǎn)生的面試順序得出的結(jié)果與模型計算得出的面試順序所得的結(jié)果進(jìn)行對比分析說明，具體內(nèi)容如下：A.5名同學(xué)進(jìn)行5個階段的面試。面試程序上，每個同學(xué)都必須從第一階段面試開始，然后進(jìn)行第二階段面試，最后進(jìn)行第五階段的

24、面試，并且在任何一個階段5名同學(xué)的順序是一樣的。 用Matlab2隨機(jī)生成面試時間矩陣即具體的面試時間如表三所示: 表3 具體面試時間表（A)同學(xué)編號第一階段第二階段第三階段第四階段第五階段19151711122167912831081417144116676517151569 按照原始同學(xué)編號排序進(jìn)行面試； 根據(jù)隨機(jī)排列的順序我們可計算出每個面試者的面試時間和等待時間，以及每階段面試的面試官的等待時間，并作出面試時間圖分別如下：圖4 面試時刻（同學(xué)）圖5 面試時刻（面試官） 由圖可知，整個面試過程共花費110分鐘，同學(xué)累計等待時間為50分鐘，面試官累計等待時間為40分鐘。下面我們將應(yīng)用所建模

25、型求解，進(jìn)行比較。 按照模型排序進(jìn)行面試根據(jù)以上所建模型，用Lingo3軟件運行（程序請見附錄3）可得最優(yōu)面試順序為，部分結(jié)果如下圖（詳見附錄4）：圖6 Lingo部分運行結(jié)果（B）根據(jù)模型所得結(jié)果，我們可計算出每個面試者的面試時間和等待時間，以及每階段面試的面試官的等待時間，并作出面試時間圖分別如下：圖7 A.面試時刻（同學(xué)）圖8 A.面試時刻（面試官） 由圖可知，整個面試過程共花費101分鐘，比隨機(jī)生成面試順序得到總時間減少9分鐘，同學(xué)累計等待時間為23分鐘，比隨機(jī)生成面試順序同學(xué)累計等待時間減少27分鐘；面試官累計等待時間為22分鐘，比隨機(jī)生成面試順序面試官等待時間減少18分鐘。根據(jù)結(jié)論

26、，我們可作出最優(yōu)面試時間安排表如下：表4 最優(yōu)面試時間安排表第一階段第二階段第三階段第四階段第五階段開始時刻結(jié)束時刻開始時刻結(jié)束時刻開始時刻結(jié)束時刻開始時刻結(jié)束時刻開始時刻結(jié)束時刻面試者38:008:108:108:188:188:328:328:498:499:03面試者18:108:198:198:348:348:518:519:029:039:15面試者58:198:368:368:518:519:069:069:129:159:24面試者28:368:528:528:599:069:159:159:279:279:35面試者48:529:039:039:099:159:219:279:

27、349:359:41 至此可知，這五位同學(xué)最早可于9:41離開該面試公司。 B.6個面試者進(jìn)行5個階段的面試； 面試程序上，每個同學(xué)都必須從第一階段面試開始，然后進(jìn)行第二階段面試，最后進(jìn)行第5階段的面試，并且在任何一個階段5名同學(xué)的順序是一樣的。 用Matlab隨機(jī)生成面試時間矩陣即具體的面試時間如下表所示: 表5 B.具體面試時間表同學(xué)編號第一階段第二階段第三階段第四階段第五階段196128725168171838179101241479191859178191561113141918按照原始同學(xué)編號排序進(jìn)行面試 根據(jù)隨機(jī)排列的順序我們可計算出每個面試者的面試時間和等待時間，以及每階段面試的

28、面試官的等待時間，并作出時刻表分別如下：圖9 B.面試時刻（同學(xué)）圖10 B.面試時刻（面試官） 由圖可知，整個面試過程共花費142分鐘，同學(xué)累計等待時間為70分鐘，面試官累計等待時間為47分鐘。下面我們將應(yīng)用所建模型求解，進(jìn)行比較。 按照模型排序進(jìn)行面試根據(jù)以上所建模型，用Lingo軟件運行（程序請見附錄5）可得最優(yōu)面試順序為，部分結(jié)果如下圖（詳見附錄6）：圖11 B.Lingo軟件部分運行圖根據(jù)模型所得結(jié)果，我們可計算出每個面試者的面試時間和等待時間，以及每階段面試的面試官的等待時間，并作出面試時間圖分別如下：圖12 B.面試時刻（同學(xué)）圖13 B.面試時刻（面試官） 由圖可知，整個面試過

29、程共花費135分鐘，比隨機(jī)生成面試順序得到總時間減少7分鐘，同學(xué)累計等待時間為119分鐘，比隨機(jī)生成面試順序同學(xué)累計等待時間增加49分鐘；面試官累計等待時間為15分鐘，比隨機(jī)生成面試順序面試官等待時間減少32分鐘。根據(jù)結(jié)論，我們可作出面試時刻安排表如下：表6 B.面試時刻安排表第一階段第二階段第三階段第四階段第五階段開始時刻結(jié)束時刻開始時刻結(jié)束時刻開始時刻結(jié)束時刻開始時刻結(jié)束時刻開始時刻結(jié)束時刻面試者28:008:058:058:218:218:298:298:468:469:04面試者48:058:198:218:288:298:388:469:059:059:23面試者38:198:278

30、:288:458:458:549:059:159:239:35面試者68:278:388:458:588:589:129:159:349:359:53面試者58:388:478:589:159:159:239:349:539:5310:08面試者18:478:569:159:219:239:359:5310:0110:0810:153. 問題三建模和求解 經(jīng)過查閱大量的文獻(xiàn)及數(shù)據(jù)，我們發(fā)現(xiàn)，當(dāng)前大部分面試的組織實施過程中均存在著一些不科學(xué)、不公平、不合理的面試模式，一個常見的基本問題是如何緊湊、高效、省時地安排面試者按順序完成面試?？茖W(xué)有效地組織和安排無論對面試者還是對組織單位、用人單位都是省

31、時省力、節(jié)略成本的。面試過程的安排無疑要根據(jù)面試者的基本情況、用人單位的要求與面試設(shè)置項目有直接關(guān)系。比較典型的情況是用人單位或組織單位設(shè)置了幾個階段的面試，參加面試的人員必須逐一完成各個階段的面試才能錄取，另外由于面試者各自的學(xué)歷、專業(yè)背景等因素的差異，每個面試者在每個階段的面試時間也有所不同。如何來合理有效地安排類似這種情況的一場面試以充分利用時間、節(jié)約雙方成本，是現(xiàn)在面試過程面臨的最主要的問題。經(jīng)過問題一和問題二的建模我們很容易發(fā)現(xiàn)，如果在面試過程中要求面試者在全部面試完以后一起離開公司無疑是浪費面試者的時間，而且對于面試官來說，由于面試者必須按階段面試，所以面試官在面試過程中也存在等待

32、時間。為了節(jié)約雙方的時間成本，我們基于問題一的結(jié)果，對面試過程進(jìn)行了更科學(xué)、更公平、更合理的規(guī)劃。基于問題一的結(jié)果，我們可以作出五個同學(xué)參加整個面試過程（包括等待時間）的時間表，如下表所示表7 同學(xué)面試時刻表到達(dá)時刻秘書面試等待時間副主管面試等待時間主管面試等待時間經(jīng)理面試離開時刻開始時刻結(jié)束時刻開始時刻結(jié)束時刻開始時刻結(jié)束時刻開始時刻結(jié)束時刻同學(xué)48:008:008:080分鐘8:088:180分鐘8:188:330分鐘8:338:418:41同學(xué)18:088:088:210分鐘8:218:360分鐘8:368:560分鐘8:569:019:01同學(xué)28:218:218:315分鐘8:368

33、:560分鐘8:569:140分鐘9:149:209:20同學(xué)58:318:318:4511分鐘8:569:077分鐘9:149:220分鐘9:229:319:31同學(xué)38:458:459:052分鐘9:079:230分鐘9:239:330分鐘9:339:409:40 由表7可以看出，當(dāng)每個同學(xué)在自己面試的時刻到面試地點以及在結(jié)束面試之后就離開面試地點的話，同學(xué)4節(jié)約時間59分鐘，同學(xué)1節(jié)約時間47分鐘，同學(xué)2節(jié)約時間41分鐘，同學(xué)5節(jié)約時間40分鐘，同學(xué)3節(jié)約時間45分鐘，整體節(jié)約時間232分鐘，即近4個小時，平均每人節(jié)約46分鐘。并且，在他們等待面試過程中，如果他們知道自己下一階段面試的開

34、始時刻，就可以利用等待時間作為機(jī)動時間來做一些其他事情。 對于面試官來說，由于面試者必須按階段面試，所以面試官在面試過程中也存在等待時間，基于問題一的結(jié)論，我們可以作出關(guān)于面試官在面試過程中等待時間的圖解如下：圖14 面試官等待時間 根據(jù)圖14，我們整理出了面試官的面試時間表如下：表8 面試官工作時間表到達(dá)時刻離開時刻休息時間休息時間段秘書8:009:050分鐘無副主管8:089:233分鐘8:18-8:21主管8:189:333分鐘8:33-8:36經(jīng)理8:339:4032分鐘8:41-8:56,9:01-9:14,9:20-9:22,9:31-9:33 根據(jù)上表我們可以看出，面試官在需要自

35、己進(jìn)行面試的時刻到面試地點以及在結(jié)束面試之后就離開面試地點的話，秘書可以節(jié)約時間35分鐘，副主管可以節(jié)約時間25分鐘，主管可以節(jié)約時間25分鐘，經(jīng)理可以節(jié)約時間33分鐘，整體節(jié)約時間118分鐘，即近2小時，并且，在他們等待面試者的過程中，如果他們知道每名面試者的開始、結(jié)束時間，他們就可以合理利用等待時間進(jìn)行休息或其他活動。 由此分析可知，對于面試公司安排面試模式時，可以預(yù)算時間，根據(jù)本文模型進(jìn)行面試者的排序，然后分別作出面試者與面試官的面試時刻表，從而通知面試者和面試官在指定面試時刻到達(dá)面試地點即可，還可以通知他們合適是休息時間，以此便建立了一個更加科學(xué)、公平、合理的面試模式，在此面試模式中，

36、可以減少面試者與面試官更多的時間成本，而在節(jié)約下來的機(jī)會成本中，他們可以創(chuàng)造更多的價值。六、模型評價與推廣1. 模型的優(yōu)點(1) 優(yōu)化模型中將面試時間最短轉(zhuǎn)化為最后一名同學(xué)面試結(jié)束時刻最早，將復(fù)雜問題極大簡化，增加模型的實用性和可靠性。(2) 所建立的最短面試時間模型具有一般性，對任意給定的面試時間矩陣均可使用，并編寫了求解最短面試時間的lingo程序，具有較大的應(yīng)用價值。2. 模型的不足：模型均是建立在不可插隊和順序面試等特性下，可能不是全局最優(yōu)。3. 模型的推廣: 在這種模型可以應(yīng)用于某工廠用n種原料經(jīng)過s個階段生產(chǎn)出不同的產(chǎn)品，并且是一種原料生產(chǎn)必須經(jīng)過第一個階段，然后經(jīng)過第二個階段直到

37、第s個階段才能生產(chǎn)出一種產(chǎn)品，并且一種原料在第k個階段生產(chǎn)的時候，其他原料不能進(jìn)行第k個階段的生產(chǎn)。原料i在j階段生產(chǎn)的時間為c(i,j) i=1到n，j1到s。問如何安排這n種原料的生產(chǎn)順序?使這n種產(chǎn)品在最短的時間內(nèi)生產(chǎn)出來七、參考文獻(xiàn)1 譚代倫, 劉益, 張世祿.多階段有序面試問題的數(shù)學(xué)模型與算法研究 J .人類工效學(xué), 2007.2 王正林，劉明.精通MATLABM.北京:電子工業(yè)出版社,2011.3 謝金星，薛毅.優(yōu)化建模與LINDO/LIMGO軟件M.北京：清華大學(xué)出版社,2007.附錄1 問題一模型的Lingo程序Model:SETS:! Person = 被面試者集合，Stag

38、e = 面試階段的集合;Person/1.5/;Stage/1.4/;! T = 已知的面試所需要的時間，X = 面試開始時間;PXS(Person,Stage): T, X;! Y(i,k) = 1: k排在i前，0：否則;PXP(Person,Person)|&1 #LT# &2: Y;ENDSETSDATA: T= 13 15 20 510 20 18 620 16 10 78 10 15 814 11 8 9 ;ENDDATAobj min =MAXT;! MAXT是面試的最后結(jié)束時間;MAXT >= max(PXS(i,j)|j#EQ#size(stage):

39、x(i,j)+t(i,j);! 只有參加完前一個階段的面試后才能進(jìn)入下一個階段;for(PXS(i,j)|j#LT#size(stage):ORDERx(i,j)+t(i,j)<x(i,j+1);! 同一時間只能面試1名同學(xué);for(Stage(j): for(PXP(i,k):SORT1x(i, j)+t(i, j)-x(k,j)<MAXT*Y(i,k) ); for(PXP(i,k):SORT2x(k,j)+t(k,j)-x(i, j)<MAXT*(1-Y(i,k) ););for(PXP: bin(y);End 附錄2 問題一Lingo運行結(jié)果 Local optima

40、l solution found. Objective value: 100.0000 Objective bound: 100.0000 Infeasibilities: 0.000000 Extended solver steps: 117 Total solver iterations: 11943 Elapsed runtime seconds: 5.44 Model Class: MINLP Total variables: 31 Nonlinear variables: 16 Integer variables: 10 Total constraints: 97 Nonlinear constraints: 81 Total nonzeros: 357 Nonlinear nonzeros: 165 Variable Value Reduced Cost MAXT 100.0000 0.000000 T( 1, 1) 13.00000 0.000000 T( 1, 2) 15.00000 0.000000 T( 1, 3) 20.00000 0.000000 T( 1, 4) 5.000000 0.000