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

20２3年天津商業(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/Ｂ中選擇一項填寫）：Ｂ參賽隊員(打印并署名)：１.葉恒揚(yáng)２.施藝敏３.張一鳴日期：20２3年４月基于動態(tài)規(guī)劃的面試時間優(yōu)化模型摘要現(xiàn)代信息社會中,求職面試已經(jīng)成為就業(yè)的一個重要環(huán)節(jié)?？茖W(xué)有效的組織和安排無論對面試者還是對組織單位、用人單位都是省時省力、節(jié)略成本的。因此如何緊湊、高效、省時地安排面試者按順序完畢面試具有重要研究意義。本文綜合運(yùn)用運(yùn)籌學(xué)、記錄學(xué)、經(jīng)濟(jì)學(xué)、平面設(shè)計、計算機(jī)軟件等知識，通過建立數(shù)學(xué)模型來求解面試的最短時間,進(jìn)一步規(guī)劃最優(yōu)的面試流程。針對問題一,通過度析給定的面試階段順序和不允許插隊等特性，為滿足面試時間最短,建立了求解最短時間的0-１非線性規(guī)劃模型（見公式（1)),然后運(yùn)用Lingo11.0程序（見附錄1),求解出最短面試時間為１00分鐘，最佳安排順序為:，同學(xué)最早9:４０一起離開。接著運(yùn)用AｕtｏＣAＤ２02３分別繪制出同學(xué)和面試官的面試過程時間圖（見圖1~2)。在此基礎(chǔ)上，運(yùn)用Eｘｃeｌ20２３制作出同學(xué)的具體面試流程表:秘書副主管主管經(jīng)理開始時刻結(jié)束時刻開始時刻結(jié)束時刻開始時刻結(jié)束時刻開始時刻結(jié)束時刻同學(xué)4８:008：08８:０88:188:１8８：338:338:４1同學(xué)18:088:2１8：２１8：3６8：36８:5６8：5６9:01同學(xué)2８:2１8：318:3６8:568:569:149:149：20同學(xué)５8:318:4５8:5６9:079:１49：２2９:229:31同學(xué)３８:４５9:０５９:079:２39:239:33９:33９:40針對問題二，同樣滿足給定的面試階段順序、不允許插隊和同學(xué)們約定一起離開等特性,對于未知的m名同學(xué)和n個階段構(gòu)成的面試時間矩陣,以最后一名同學(xué)面試的結(jié)束時間最早為目的函數(shù),以不允許插隊和同一面試官同一階段只能面試一個同學(xué)為約束條件,建立求解面試最短時間的動態(tài)規(guī)劃模型(見公式(15)),并由Ｍａt(yī)ｌab生成隨機(jī)面試時間矩陣（面試由５名同學(xué)和5階段組成）和(面試由6名同學(xué)和5階段組成）,由Lingo程序（見附錄3、5)求解出最短面試時間分別為101分鐘和13５分鐘，比未經(jīng)優(yōu)化按原始順序面試的１1０分鐘和１42分鐘分別縮短9分鐘和7分鐘，接著運(yùn)用AutｏCAＤ２０２3分別繪制出優(yōu)化前后的面試過程時間圖（見圖3~１3）。同樣,運(yùn)用Eｘcel２023制作出同學(xué)的具體面試流程表(見表3~6）。優(yōu)化后的面試時間較未優(yōu)化的面試時間有所縮短,驗證了模型的對的性,也是對模型的檢查。針對問題三,基于第一問和第二問的建模思想,同時進(jìn)一步考慮到同學(xué)和面試官的等待過程是對時間成本的極大消耗,摒棄現(xiàn)有面試模式中同學(xué)同時到達(dá)再一起離開這一傳統(tǒng)模式，建立無論是對于同學(xué)還是面試官只要完畢自己的面試便可離開的新模式,基于問題一的已知面試時間矩陣,繪制出同學(xué)和面試官的面試時間圖(圖1和圖１1）,并分別繪制同學(xué)和面試官的具體面試時間流程表（見表７～8)，同學(xué)和面試官可根據(jù)時間流程表提前安排行程和合理運(yùn)用等待時間,節(jié)約時間見下表:【關(guān)鍵字】面試時間,排序,動態(tài)規(guī)劃，優(yōu)化模型，lｉｎgｏ軟件一、問題的提出與重述現(xiàn)代信息社會中，求職面試已經(jīng)成為就業(yè)的一個重要環(huán)節(jié)。在面試的組織實行過程中，一個常見的基本問題是如何緊湊、高效、省時地安排面試者按順序完畢面試，科學(xué)有效的組織和安排無論對面試者還是對組織單位、用人單位都是省時省力、節(jié)略成本的。面試過程的安排無疑要根據(jù)面試者的基本情況、用人單位的規(guī)定與面試設(shè)立項目有直接關(guān)系。比較典型的情況是用人單位或組織單位設(shè)立了幾個階段的面試,參與面試的人員必須逐個完畢各個階段的面試才干錄取,此外由于面試者各自的學(xué)歷、專業(yè)背景等因素的差異,每個面試者在每個階段的面試時間也有所不同。對上述面試情況,作簡化和抽象后可描述為以下數(shù)學(xué)問題。問題一某高校畢業(yè)生中有5名同學(xué)到一家公司參與四個階段的面試。面試程序上,規(guī)定每個同學(xué)都必須從第一階段面試開始，然后進(jìn)行第二階段面試,…，最后進(jìn)行第四階段的面試，并且在任何一個階段5名同學(xué)的順序是同樣的,假定開始面試時間是上午８：００，建立的數(shù)學(xué)模型,求出他們最早離開公司的時間。問題二假設(shè)該高校畢業(yè)生中有ｍ名同學(xué)到一家公司應(yīng)聘,按類似于問題１的面試規(guī)則需要參與該公司人事部門組織的ｎ個階段的面試。由于m名同學(xué)的專業(yè)背景不同，所以每人在每個階段的面試時間也不同，這m名同學(xué)約定他們所有面試完以后一起離開公司。請建立數(shù)學(xué)模型，以此討論他們最早何時能離開該面試的公司？問題三試設(shè)計一種更科學(xué)、更公平、更合理的面試模式，并給出理由?；炯僭O(shè)1．假設(shè)面試者從一個階段到下一個階段參與面試的時間間隔為0；２.假定面試者都能在8：０0準(zhǔn)時到達(dá)面試地點;3.假定可以任意排列面試者的面試順序;4．假定面試者均會參與每個階段的面試,并且沒有半途退場的情況出現(xiàn)；5.假設(shè)參與面試的求職者都是平等且獨立的，即他們面試的順序與考官無關(guān)。三、重要變量的符號說明為了便于描述問題,本文將問題中涉及的重要變量用下表符號來表達(dá):表一重要變量符號說明一覽表符號表達(dá)的意義完畢所有面試所花費的最少時間第名同學(xué)參與第階段面試的開始時刻第名同學(xué)參與第階段面試需要的時間第名同學(xué)參與第階段面試的開始時刻第名同學(xué)是否排在第名同學(xué)前面(１表達(dá)是，0表達(dá)否)面試時間矩陣四、問題分析問題是“面試如何安排才干盡早結(jié)束”,根據(jù)題意可知,由于面試者各自的學(xué)歷、專業(yè)背景等因素的差異,每個面試者在每個階段的面試時間有所不同,這樣就導(dǎo)致了按某種順序進(jìn)入各面試階段時不能緊鄰順序完畢，即當(dāng)面試正式開始后,在某個面試階段，某個面試者會由于前面的面試者所需時間長而等待，也也許會由于自己所需時間短而提前完畢。因此本問題實質(zhì)上是求面試時間總和的最小值問題，其中一個面試時間總和就是指在一個擬定面試順序下所有面試者按序完畢面試所花費的時間之和，這樣的面試時間總和的所有也許情況則取決于面試者的面試順序的所有排列數(shù)。從而原問題可等價于:求所有也許的面試順序中，使花費總時間最少的那種順序，并求出所花費的總時間。就問題一而言，事實上，這個問題就是要安排５名面試者的面試順序，使完畢所有面試所花費的時間最少。通過度析給定的面試階段順序和不允許插隊等特性,為滿足面試時間最短，可建立求解最短時間的0－1非線性規(guī)劃模型,然后運(yùn)用lingo11．0程序求解出最短面試時間以及最佳安排順序。最后根據(jù)模型結(jié)果可得出同學(xué)最早離開面試地點的時間。此外我們可以運(yùn)用AutoCAＤ20２３分別繪制出同學(xué)和面試官的面試過程時間圖,在此基礎(chǔ)上,還可以運(yùn)用Eｘｃel２0２3制作出同學(xué)的具體面試流程表;就問題二而言,事實上就是要安排m名面試者的面試順序,使完畢所有面試階段ｎ所花費的時間最少。同樣滿足給定的面試階段順序、不允許插隊和同學(xué)們約定一起離開等特性,我們可以嘗試建立求解面試最短時間的動態(tài)規(guī)劃模型，并可由Matlaｂ生成隨機(jī)面試時間矩陣，然后由Lingo程序求解出最短面試時間，再運(yùn)用AuｔｏCAD2０２3分別繪制出優(yōu)化前后的面試過程時間圖。同樣，可運(yùn)用Excel2023制作出同學(xué)的具體面試流程表。最后可以比較一下優(yōu)化后的面試時間較未優(yōu)化的面試時間的改變,從而驗證模型的對的性，也是對模型的檢查。就問題三而言，需要我們從科學(xué)性、公平性、合理性三個方面對面試模式進(jìn)行改善。我們可以通過查閱資料了解當(dāng)前面試模式中存在的普遍性不合理現(xiàn)象，然后針對不合理現(xiàn)象進(jìn)行面試模式的改善。五、模型的建立與求解問題一建模和求解（1）模型建立記為第名同學(xué)參與第階段面試需要的時間（已知）,令表達(dá)第名同學(xué)參與第階段面試的開始時刻(不妨記早上8：００面試開始為０時刻)為完畢所有面試所花費的最少時間。則有優(yōu)化目的為:（1）面試時間矩陣:約束條件:①對時間先后順序進(jìn)行約束,即每人只有參與完前一個階段的面試后才干進(jìn)入下一個階段：（２)②每個階段同一時間只能面試1名同學(xué),用0-1變量表達(dá)第名同學(xué)是否排在第名同學(xué)前面（1表達(dá)是，0表達(dá)否),則:,（3）,（4）可以將非線性的優(yōu)化目的改寫為如下線性優(yōu)化目的:（5）(6）(7）(８)(9）這個問題的0-1非線性規(guī)劃模型[１]為:(10)，(1１),(12），(１3)，(14）模型求解根據(jù)以上所建的模型,我們可編出Ｌingo程序（詳見附錄1)，部分運(yùn)營結(jié)果見圖1（具體結(jié)果請見附錄2)：圖1問題一部分運(yùn)營結(jié)果結(jié)果分析由變量的最優(yōu)解值為10０.00000,知最短時間為100分鐘,即5名同學(xué)一起離開公司的時間是9:40。

由變量Y（S1，S2)的最優(yōu)解值為0．０0０0０0,知ｓｔｕdent1排在ｓtudeｎt2之前,即1號同學(xué)排在２號同學(xué)之前。

由變量Ｙ(S1,S3)的最優(yōu)解值為0.0０0000,知ｓtｕｄｅnｔ1排在stuｄent3之前,即1號同學(xué)排在3號同學(xué)之前。

由變量Y(S1，S4）的最優(yōu)解值為1.00０000，知ｓｔudｅｎt4排在ｓｔudent1之前,即4號同學(xué)排在1號同學(xué)之前。由變量Y(S1,S5）的最優(yōu)解值為0.000００0,知sｔuｄent１排在ｓtuｄent5之前，即１號同學(xué)排在5號同學(xué)之前。?由變量Y(Ｓ2，S3)的最優(yōu)解值為0.000000，知stｕｄｅnt2排在sｔudent３之前,即２號同學(xué)排在3號同學(xué)之前。?由變量Y(Ｓ2,S4)的最優(yōu)解值為１．０0００00，知student4排在stuｄent2之前,即4號同學(xué)排在２號同學(xué)之前。由變量Y（Ｓ2,S5）的最優(yōu)解值為0.０0000０,知sｔｕdｅnt2排在studenｔ5之前，即2號同學(xué)排在５號同學(xué)之前。?由變量Y(S３,Ｓ4)的最優(yōu)解值為1.０000０0,知sｔudent４排在stｕdent3之前,即4號同學(xué)排在3號同學(xué)之前。由變量Y（S３，Ｓ５)的最優(yōu)解值為1.00０0０0,知stｕｄent5排在sｔｕdeｎt3之前，即５號同學(xué)排在３號同學(xué)之前。由變量Y(S4，S５)的最優(yōu)解值為0.00００00,知sｔｕdeｎt4排在stuｄent5之前，即4號同學(xué)排在5號同學(xué)之前。根據(jù)模型得出的結(jié)果,我們可以作出整個面試過程的圖解如下：圖2整體面試過程（同學(xué))圖３整體面試過程(面試官）根據(jù)圖解,我們可做出這五位同學(xué)的具體面試安排如下（不妨設(shè)８:00為0時刻):?第一個進(jìn)行面試的是4號同學(xué)。４號同學(xué)在０時刻開始秘書面試,用時8分鐘；秘書處面試結(jié)束后去副主管處進(jìn)行面試,用時1０分鐘；接著去主管處面試，用時１5分鐘;最后去經(jīng)理處面試,用時8分鐘；最終,４號同學(xué)在8:41完畢整個面試過程。?第二個進(jìn)行面試的是1號同學(xué)。1號同學(xué)在8分鐘時刻開始秘書面試，用時１3分鐘，此時4號同學(xué)已經(jīng)完畢副主管面試;１號同學(xué)直接進(jìn)行副主管面試,用時15分鐘，此時4號同學(xué)已經(jīng)完畢主管面試;1號同學(xué)直接進(jìn)行主管面試，用時2０分鐘，此時4號同學(xué)已經(jīng)完畢經(jīng)理面試;1號同學(xué)開始經(jīng)理面試,用時5分鐘;最終,1號同學(xué)在9：01完畢整個面試過程。第三個進(jìn)行面試的是2號同學(xué)。2號同學(xué)在21分鐘時刻開始秘書面試，用時10分鐘完畢秘書面試,此時1號同學(xué)尚未完畢副主管面試;２號同學(xué)等待5分鐘后進(jìn)行副主管面試,面試用時20分鐘,此時1號同學(xué)剛好結(jié)束主管面試;2號同學(xué)直接進(jìn)行主管面試，用時1８分鐘，此時1號同學(xué)已經(jīng)完畢經(jīng)理面試;２號同學(xué)直接進(jìn)行經(jīng)理面試,用時6分鐘。最終,2號同學(xué)在９:20完畢整個面試過程。第四個進(jìn)行面試的是5號同學(xué)。5號同學(xué)在31分鐘時刻開始秘書面試，用時１4分鐘完畢秘書面試，此時2號同學(xué)尚未完畢副主管面試；５號等待1１分鐘后進(jìn)行副主管面試，面試副主管用時11分鐘，副主管面試完，2號同學(xué)尚未完畢主管面試；5號同學(xué)等待7分鐘后開始主管面試,用時８分鐘，此時２號同學(xué)已經(jīng)完畢經(jīng)理面試;5號同學(xué)直接進(jìn)行經(jīng)理面試，用時9分鐘。最終,5號同學(xué)在9:31完畢整個面試過程。最后進(jìn)行面試的是3號同學(xué)。３號同學(xué)在4５分鐘時刻開始秘書面試,用時２0分鐘完畢秘書面試，此時５號同學(xué)尚未完畢副主管面試;3號同學(xué)等待2分鐘后開始面試副主管,用時1６分鐘,此時5號同學(xué)已經(jīng)完畢主管面試；３號同學(xué)直接開始主管面試,用時1０分鐘,此時5號同學(xué)已經(jīng)完畢經(jīng)理面試；３號同學(xué)直接進(jìn)行經(jīng)理面試，用時7分鐘,最終,３號同學(xué)在9:4０完畢整個面試過程。為了更加直觀地表達(dá)整個面試過程的時間安排，我們作出面試的時間安排表如下:表2面試時間安排表秘書副主管主管經(jīng)理開始時刻結(jié)束時刻開始時刻結(jié)束時刻開始時刻結(jié)束時刻開始時刻結(jié)束時刻同學(xué)48:008:08８:088:1８８：188:３3８:338:41同學(xué)18:０88:218:21８：3６８:368:568:569:０1同學(xué)28：２1８:318:３６8:56８:５６９：14９:1４9:20同學(xué)５8：３18:458：569:0７9：14９:2２9：22９:３1同學(xué)３8:459:059:０７9:239：２３９:339:339:4０至此，模型所得五位同學(xué)的面試順序為，以此順序依次進(jìn)行面試,總計用時最短，為100分鐘,即這五位同學(xué)最早可在9：40離開公司。問題二建模和求解對于問題一,所建立的數(shù)學(xué)模型是針對具體面試者與面試階段的特定模型。而問題二需要針對面試者與面試階段不擬定建立相應(yīng)的數(shù)學(xué)模型,進(jìn)而求出最短面試時間。為此，借助問題一的建模思想,將模型進(jìn)一步推廣，假設(shè)有m名面試者,n個面試階段,建立求解最小面試時間的數(shù)學(xué)模型。（１)模型建立事實上，這個問題就是要安排m名面試者的面試順序,使完畢所有面試所花費的時間最少。面試時間矩陣:優(yōu)化目的：(15)約束條件：時間先后順序約束(每人只有參與完前一個階段的面試后才干進(jìn)入下一個階段)（16）每個階段j同一時間只能面試1名同學(xué):用0－1變量表達(dá)第名同學(xué)是否排在第名同學(xué)前面(1表達(dá)是,0表達(dá)否）,則,(１7），(18）可以將非線性的優(yōu)化目的改寫為如下線性優(yōu)化目的:(19）s．t.(2０）（21)……(22)則這個問題的０－1非線性規(guī)劃模型為:（23）s.t.,（2４),(25）,(2６），(2７)模型求解根據(jù)模型，我們可編寫ＬＩNGO程序如下：Modeｌ:SETS:！Person=被面試者集合，Stａge=面試階段的集合;Persｏｎ/1..m／;Stａge/1..n/;!T=已知的面試所需要的時間,X=面試開始時間;ＰXS（Pｅrsｏn,Stagｅ):T,X;!Y(i,k)=１：k排在i前,0：否則；ＰXP(Person,Peｒson）|＆1#LT#&2：Y;ENＤＳETSDATＡ:T=;EＮＤDAＴA[obj]ｍin＝MＡXT;！MAXＴ是面試的最后結(jié)束時間;MＡXT>=＠m(xù)ａｘ（ＰXS(i,ｊ)|j#ＥQ#@sｉze（staｇe):ｘ（ｉ,j)＋t(i,j）)；！只有參與完前一個階段的面試后才干進(jìn)入下一個階段;@fｏｒ(ＰXS（ｉ,j)|ｊ#LT#@sｉze(sｔage）：［ORＤEＲ]x(i,j)＋t（ｉ,j)＜x(i,j+1）);!同一時間只能面試１名同學(xué)；＠for(Stａgｅ（j):@fｏr(PＸP（i,k）:[SOＲT1］ｘ（i，j）＋t(i,j）-ｘ(k,j)<MAXＴ*Y(i,ｋ))；@for(PXP(ｉ,k):[SORＴ2]x(ｋ,j)+ｔ（ｋ，j)－x(i,ｊ)<MAXT＊(１－Y(i,k))）；);@ｆor(PXP:＠ｂin(y）);End具體情況中，只需將面試人數(shù)m、面試階段n以及初始時間矩陣的具體值代入程序即可得最優(yōu)面試順序以及最短面試時間。(3）結(jié)果分析依照題設(shè)規(guī)定,我們運(yùn)用Ｅxｃel隨機(jī)生成５人面試５階段的面試時間和6人面試5階段的面試時間進(jìn)行模型結(jié)果分析,并對隨機(jī)產(chǎn)生的面試順序得出的結(jié)果與模型計算得出的面試順序所得的結(jié)果進(jìn)行對比分析說明，具體內(nèi)容如下：A．５名同學(xué)進(jìn)行5個階段的面試。面試程序上,每個同學(xué)都必須從第一階段面試開始，然后進(jìn)行第二階段面試，…，最后進(jìn)行第五階段的面試,并且在任何一個階段5名同學(xué)的順序是同樣的。用Mａt(yī)laｂ[2］隨機(jī)生成面試時間矩陣即具體的面試時間如表三所示:表3具體面試時間表(Ａ)同學(xué)編號第一階段第二階段第三階段第四階段第五階段19１5171１122１67912８310814１７１441166７６5１7151569按照原始同學(xué)編號排序進(jìn)行面試;根據(jù)隨機(jī)排列的順序我們可計算出每個面試者的面試時間和等待時間,以及每階段面試的面試官的等待時間，并作出面試時間圖分別如下:圖4面試時刻（同學(xué))圖5面試時刻（面試官)由圖可知，整個面試過程共花費１1０分鐘,同學(xué)累計等待時間為５0分鐘,面試官累計等待時間為40分鐘。下面我們將應(yīng)用所建模型求解,進(jìn)行比較。按照模型排序進(jìn)行面試根據(jù)以上所建模型,用Linｇo［３］軟件運(yùn)營（程序請見附錄3)可得最優(yōu)面試順序為，部分結(jié)果如下圖（詳見附錄4）:圖6Lingｏ部分運(yùn)營結(jié)果（Ｂ)根據(jù)模型所得結(jié)果,我們可計算出每個面試者的面試時間和等待時間，以及每階段面試的面試官的等待時間，并作出面試時間圖分別如下：圖7A.面試時刻（同學(xué)）圖8Ａ.面試時刻(面試官)由圖可知,整個面試過程共花費1０1分鐘,比隨機(jī)生成面試順序得到總時間減少9分鐘,同學(xué)累計等待時間為2３分鐘,比隨機(jī)生成面試順序同學(xué)累計等待時間減少27分鐘;面試官累計等待時間為2２分鐘，比隨機(jī)生成面試順序面試官等待時間減少１8分鐘。根據(jù)結(jié)論，我們可作出最優(yōu)面試時間安排表如下:表4最優(yōu)面試時間安排表第一階段第二階段第三階段第四階段第五階段開始時刻結(jié)束時刻開始時刻結(jié)束時刻開始時刻結(jié)束時刻開始時刻結(jié)束時刻開始時刻結(jié)束時刻面試者38:00８:10８:108:１88:１88：３28:3２8:4９8:４99:03面試者18:108：１98:198：3４８:３4８:5１8:5１9:029:０39：１5面試者５8:198:３68:36８:５18:５19：０69:06９:１29：159：2４面試者28:３68:５2８：52８:599：06９：159:159:２7９:2７9:３５面試者48:５29:039：039：０99:15９:２19:279：３49:3５9：41至此可知,這五位同學(xué)最早可于9:４1離開該面試公司。Ｂ．6個面試者進(jìn)行５個階段的面試;面試程序上,每個同學(xué)都必須從第一階段面試開始,然后進(jìn)行第二階段面試,…,最后進(jìn)行第5階段的面試,并且在任何一個階段5名同學(xué)的順序是同樣的。用Ｍaｔlａb隨機(jī)生成面試時間矩陣即具體的面試時間如下表所示：表5B.具體面試時間表同學(xué)編號第一階段第二階段第三階段第四階段第五階段1９612８7251６81７1838１７９１0１24147919１8591781915６1１13141918按照原始同學(xué)編號排序進(jìn)行面試根據(jù)隨機(jī)排列的順序我們可計算出每個面試者的面試時間和等待時間，以及每階段面試的面試官的等待時間，并作出時刻表分別如下:圖9B.面試時刻(同學(xué))圖１0Ｂ．面試時刻(面試官)由圖可知,整個面試過程共花費１42分鐘，同學(xué)累計等待時間為7０分鐘,面試官累計等待時間為47分鐘。下面我們將應(yīng)用所建模型求解,進(jìn)行比較。按照模型排序進(jìn)行面試根據(jù)以上所建模型，用Lingｏ軟件運(yùn)營(程序請見附錄5)可得最優(yōu)面試順序為,部分結(jié)果如下圖(詳見附錄６）:圖１１B．Liｎgo軟件部分運(yùn)營圖根據(jù)模型所得結(jié)果，我們可計算出每個面試者的面試時間和等待時間，以及每階段面試的面試官的等待時間,并作出面試時間圖分別如下:圖1２B．面試時刻(同學(xué)）圖13B.面試時刻(面試官)由圖可知,整個面試過程共花費135分鐘，比隨機(jī)生成面試順序得到總時間減少7分鐘，同學(xué)累計等待時間為1１9分鐘，比隨機(jī)生成面試順序同學(xué)累計等待時間增長4９分鐘；面試官累計等待時間為1５分鐘,比隨機(jī)生成面試順序面試官等待時間減少32分鐘。根據(jù)結(jié)論,我們可作出面試時刻安排表如下：表6B.面試時刻安排表第一階段第二階段第三階段第四階段第五階段開始時刻結(jié)束時刻開始時刻結(jié)束時刻開始時刻結(jié)束時刻開始時刻結(jié)束時刻開始時刻結(jié)束時刻面試者28:00８:０５8:058:218:218:298:2９8：４68：469:0４面試者48:0５8：１98:2１8:288:2９８:３88:469:059:059:23面試者３8：1９８:２７８:2８8:458:45８:549:059:159：239:35面試者68:278:３88:４58:5８8:５89:129:１59:34９:359:53面試者5８:388：4７8:5８９:159：1５9：２39:349:５3９:５31０：08面試者1８:478:5６9:１59:219:２3９:3５9:５３10:01１0:0８1０:１５問題三建模和求解通過查閱大量的文獻(xiàn)及數(shù)據(jù),我們發(fā)現(xiàn)，當(dāng)前大部分面試的組織實行過程中均存在著一些不科學(xué)、不公平、不合理的面試模式,一個常見的基本問題是如何緊湊、高效、省時地安排面試者按順序完畢面試?？茖W(xué)有效地組織和安排無論對面試者還是對組織單位、用人單位都是省時省力、節(jié)略成本的。面試過程的安排無疑要根據(jù)面試者的基本情況、用人單位的規(guī)定與面試設(shè)立項目有直接關(guān)系。比較典型的情況是用人單位或組織單位設(shè)立了幾個階段的面試，參與面試的人員必須逐個完畢各個階段的面試才干錄取，此外由于面試者各自的學(xué)歷、專業(yè)背景等因素的差異，每個面試者在每個階段的面試時間也有所不同。如何來合理有效地安排類似這種情況的一場面試以充足運(yùn)用時間、節(jié)約雙方成本，是現(xiàn)在面試過程面臨的最重要的問題。通過問題一和問題二的建模我們很容易發(fā)現(xiàn)，假如在面試過程中規(guī)定面試者在所有面試完以后一起離開公司無疑是浪費面試者的時間,并且對于面試官來說,由于面試者必須按階段面試，所以面試官在面試過程中也存在等待時間。為了節(jié)約雙方的時間成本，我們基于問題一的結(jié)果，對面試過程進(jìn)行了更科學(xué)、更公平、更合理的規(guī)劃?；趩栴}一的結(jié)果，我們可以作出五個同學(xué)參與整個面試過程（涉及等待時間）的時間表,如下表所示表7同學(xué)面試時刻表到達(dá)時刻秘書面試等待時間副主管面試等待時間主管面試等待時間經(jīng)理面試離開時刻開始時刻結(jié)束時刻開始時刻結(jié)束時刻開始時刻結(jié)束時刻開始時刻結(jié)束時刻同學(xué)48:008:008：080分鐘8:08８:１8０分鐘8：188:330分鐘8:338:418：41同學(xué)18：088:088:210分鐘8:21８:３60分鐘８:368:560分鐘8:５６9:019:01同學(xué)28:218:218:315分鐘8:3６８:５６０分鐘8:５６９：140分鐘９:149:２09：20同學(xué)58：31８:３18:4５1１分鐘８:569：0７7分鐘9:149:220分鐘9：229:３19:３１同學(xué)3８:458：4５９：052分鐘９:０79:23０分鐘９:23９：33０分鐘９：339：４０９:４０由表7可以看出，當(dāng)每個同學(xué)在自己面試的時刻到面試地點以及在結(jié)束面試之后就離開面試地點的話,同學(xué)４節(jié)約時間59分鐘，同學(xué)１節(jié)約時間47分鐘，同學(xué)２節(jié)約時間41分鐘，同學(xué)5節(jié)約時間40分鐘，同學(xué)3節(jié)約時間４5分鐘，整體節(jié)約時間232分鐘,即近４個小時,平均每人節(jié)約46分鐘。并且，在他們等待面試過程中,假如他們知道自己下一階段面試的開始時刻，就可以運(yùn)用等待時間作為機(jī)動時間來做一些其他事情。對于面試官來說，由于面試者必須按階段面試,所以面試官在面試過程中也存在等待時間，基于問題一的結(jié)論,我們可以作出關(guān)于面試官在面試過程中檔待時間的圖解如下：圖１4面試官等待時間根據(jù)圖１4,我們整理出了面試官的面試時間表如下：表8面試官工作時間表到達(dá)時刻離開時刻休息時間休息時間段秘書8:009:050分鐘無副主管8：089:233分鐘8:1８-8：21主管8:189：333分鐘８：33-8：36經(jīng)理8:339:40３2分鐘8:41-8:5６，9:01－9:１4，9:２0-９：22,9：3１-９：３3根據(jù)上表我們可以看出，面試官在需要自己進(jìn)行面試的時刻到面試地點以及在結(jié)束面試之后就離開面試地點的話,秘書可以節(jié)約時間３5分鐘，副主管可以節(jié)約時間２５分鐘，主管可以節(jié)約時間25分鐘，經(jīng)理可以節(jié)約時間3３分鐘,整體節(jié)約時間118分鐘,即近2小時，并且，在他們等待面試者的過程中,假如他們知道每名面試者的開始、結(jié)束時間，他們就可以合理運(yùn)用等待時間進(jìn)行休息或其他活動。由此分析可知，對于面試公司安排面試模式時,可以預(yù)算時間,根據(jù)本文模型進(jìn)行面試者的排序，然后分別作出面試者與面試官的面試時刻表，從而告知面試者和面試官在指定面試時刻到達(dá)面試地點即可，還可以告知他們合適是休息時間，以此便建立了一個更加科學(xué)、公平、合理的面試模式，在此面試模式中,可以減少面試者與面試官更多的時間成本,而在節(jié)約下來的機(jī)會成本中,他們可以發(fā)明更多的價值。六、模型評價與推廣1.模型的優(yōu)點（1)優(yōu)化模型中將面試時間最短轉(zhuǎn)化為最后一名同學(xué)面試結(jié)束時刻最早,將復(fù)雜問題極大簡化，增長模型的實用性和可靠性。（２）所建立的最短面試時間模型具有一般性,對任意給定的面試時間矩陣均可使用,并編寫了求解最短面試時間的lingo程序，具有較大的應(yīng)用價值。2.模型的局限性：模型均是建立在不可插隊和順序面試等特性下，也許不是全局最優(yōu)。3.模型的推廣:在這種模型可以應(yīng)用于某工廠用n種原料通過s個階段生產(chǎn)出不同的產(chǎn)品，并且是一種原料生產(chǎn)必須通過第一個階段,然后通過第二個階段直到第s個階段才干生產(chǎn)出一種產(chǎn)品,并且一種原料在第ｋ個階段生產(chǎn)的時候，其他原料不能進(jìn)行第k個階段的生產(chǎn)。原料i在j階段生產(chǎn)的時間為c(i,j）i＝1到ｎ，ｊ＝1到s。問如何安排這n種原料的生產(chǎn)順序?使這n種產(chǎn)品在最短的時間內(nèi)生產(chǎn)出來七、參考文獻(xiàn)[1］譚代倫,劉益，張世祿.多階段有序面試問題的數(shù)學(xué)模型與算法研究[Ｊ].人類工效學(xué),２０23.[2]王正林,劉明.精通MAＴLAB［Ｍ]．北京:電子工業(yè)出版社,２02３.[3]謝金星,薛毅.優(yōu)化建模與ＬINDO/ＬIMＧO軟件[M］.北京:清華大學(xué)出版社,2０23.附錄1問題一模型的Linｇo程序Ｍodｅl:SEＴS：!Pｅｒsｏn=被面試者集合,Sｔagｅ＝面試階段的集合;Ｐerson/1..５/；Ｓtagｅ／１．.４／;!Ｔ=已知的面試所需要的時間，X=面試開始時間;PXS(Pｅrson,Staｇe）：T，Ｘ；!Y（i,ｋ）=１:k排在i前，０：否則;PXP（Perｓon，Perｓon)|＆1#LT#&2:Y;ＥNＤSＥＴSＤＡTA：T=1３15２０51０２0１862０１610781015８141189;ＥNDDATA[obj］miｎ=MAＸT;!ＭAXT是面試的最后結(jié)束時間;MＡXＴ>=@mａx(ＰＸＳ(i,ｊ)|ｊ#EQ#@sizｅ(stage）：x（i,j)＋t(i,j));!只有參與完前一個階段的面試后才干進(jìn)入下一個階段；＠ｆor(ＰXS（i,j)|j#LT#@sｉze（stage）:［ORDER］ｘ(i，ｊ)+t(ｉ,j)<ｘ(i,j+1));!同一時間只能面試１名同學(xué);@for（Sｔage(j）:@ｆor（PXP(i，k):[SＯＲT1]ｘ(i,j)＋t(ｉ,j)-x(k,j)<MAXT*Y（ｉ,k))；@foｒ(PXP(i,k):[SORT2]x(ｋ,j)＋t（k，j)-x(i，j)<MAXT＊(1-Ｙ（i,k）)););@foｒ(PXP:＠ｂin(y));Ｅnd附錄２問題一Lｉngｏ運(yùn)營結(jié)果Loｃalopｔiｍalsolutionfoｕnd.Objecｔｉveｖａlｕe:１00.０000Objectiveｂｏund:1０0.0000Iｎfeａsｉbilities：0．０0０0０0Exteｎdeｄsｏlｖｅrｓteps:117Totalsolveriteratｉons:1１９43Ｅlapsedruntimｅsｅｃｏnｄｓ：５.４4ＭodelClａｓs:MINLPTｏtａlvariables:31Noｎlｉneａrvariabｌes:1６Integervariableｓ:１0Ｔotalcoｎsｔraｉｎts:97Nonlinearconstraiｎts:8１Totalnｏnｚerｏs:3５7Nonｌｉnearnonzｅｒoｓ:165VariaｂｌeValueRｅdｕceｄCｏstMAXT１00.000０0.000000T（１,1)１3.0０0００0.0000０0T（1,２)15.0０0000.0000０0T(１,3)20.000０00.000000T（１,4）5．００00000．00００00T(２,1）1０.0００00０.00０00０T(２，2）20．0000０0.00０000T（2，3）18.００0000.000００0T(2，4）6.0０0000０.000０00T(３,1)2０．00００00.0０0000Ｔ(3,２)１6.0０００00.０00０0０T(3,3)10.0000０0.0０0000T(3,4)7.0０0０００0．000000T(4,1)8．0０00000.００0000T(４,2)１０.000０００.０000０0T（4，3)１5.0０0０００．00０00０Ｔ(4,4)8．0000000．００000０T（５，1)14.000000.00０00０T(５,2）11.00０0０0.0００000T(５,３）８．000000０.0０00０0T(5,4)９.000０0０0．0０00０0X（1,1)8.000０000.0000００X（1，2）２１.000０0０.0000００X(1,3）3６.000000.０00000X(1,4)5６.000００0．000０00X（2,1)２3.000０00.０0０0００Ｘ(2,2)36．０0０0０0.000000X(2,３)56.000000．００0000X（2,４）74.０00000.000000Ｘ(3，1)４7.00０000．0０00０0X(3,2)67．0０0000.000000X(３,3)８3.000000.０0０000Ｘ(３,４)93.00000０.00000０X(4，1)0．００００000．999９960X(4,2)８.６0000０0．0０0000X(4,3)21.0０0０00.0０0000X(4，４)４8．0００000．0０0000Ｘ(5,1)33.00０000．0００000X(5,２)56.０0０000.000000X(５，3)74．000000.００0０００X(5,4)84.０000０0.000０0０Y（1，2)０．000０００-9９.999２0Y(1,３)0.００00000．00０000Ｙ（1,４)１．00０00099.99９20Ｙ(1,5)０.0000000.0０0０００Ｙ(2,3)0.00000０0.０000０0Y（2，4)1.000０００0.00０000Y(2,５)０.00000０-99.99920Y(3，４)1.0０0０0００.000000Y(3,５)１.0000009９.９99２０Y（4，5）０.000000０.000000RoｗSｌａckorSｕrｐｌuｓＤｕaｌＰriceOBJ100．０00０-1.0000０020.００0000-0.9９999６０OＲDER(１,1)0.０00０００0.99999６０OＲDＥＲ（1,2）０.００00000.000000OＲDEＲ(1,3)0.０000０00．00０000OＲDEＲ(2,1)3．000０000．０00000OＲDEＲ(2,2)0.０00０00０.0００0０0ORDEＲ（２,3)０．0０000００.0０0000ＯRDER（3,１）0．0000000．00000０ＯRＤER(３，2)0.０000000.9９９9９60ＯRDER（3,3)0.000０000.９９99９６0OＲDＥR(4,1)0．６0０00000.000000ORDER(4,2)２.４0000０0.000000OＲDER(4,3)1２.000００0.0００00０ORDER(5，１)9.０000000.0０0000ORＤEＲ(5,2)７.000０00０.０0000０ORＤEＲ(5，３)2.０000000．000０00SORT1(1,1,2)2.0000000.0０００00ＳＯRT１（1，1，３)26.000000.00000０ＳORT1(1,1，４）79.000000.000０00SORT1(1,1,5)１2．0000００．0００000SOＲT1(１,2，3)14.00000０.0０0０00SＯRT１(1,2,4)6７.０00００0.００000０SORT1(１，2，５)0．00００000.000000SOＲＴ１（1,3,４)33.000000.000000SORＴ1(1,3,５)66.00０00０.0０00０0ＳＯRＴ1(1,4,5）２5.０00000.0０0０00SORT2(1，1,２）７5.０00000.000000SOＲT2(1,1,3)41．0０000０．00００0０SORＴ2(１，1，4)０.0０00000．9999９６0SＯＲＴ2（1,1,5)6１.００000０．0000０0SORT2(1，2,3)５６.０00000.０00000SORT２(1,２,4)15.000000.00００0０SORT2(1，2,5)76.０0０000．000000ＳＯRＴ２(1,3,４）3９.00０0０0.0000０0SORＴ2(1,3，5)0．０00000０．000000SORT2(1,4，5)53.００0０00．0０0０00SORT１（2,1，2)0．００0０000.9999960SＯRT1（2，１,3）31.000000．000０00SＯRＴ1(2,１,4)７2.600000.0000０0SＯRＴ1（2,1,5)２0.00００00.0000００SOＲT１（2,2,3)１１.0000０0．00０000ＳＯRT1(2,2,4)５2.６000０0．0０0000ＳORT1（2,2，５)0．000０000.999996０SORＴ1（２,3,4）２5．６0000０.000000SORT１(２，3,5)73.000000.０00０００SORT１（２，４,5)37.４00０00.０000００SＯRT2(2,1，2）６5.０000０0.0００00０SＯRT2(２，1,3)3８．000000．0000０0SＯＲT2(２,１，４)2.4０0000０.000000SORＴ２(２，1,5)54.000０0０.0０0０00SOＲＴ２(2,2,3)53.00０００0.000００0SORT2（2，2,4)１7.４000０0.0０0000SＯRT2(２，2,5）6９.００0０0０.00０000SORT2(２，3,4)48.４000０0．000０0０SＯRT2(２，3,５)0.0００0000．9９99960ＳORT2(２,4,５）41.６００000.000００0ＳOＲT1(3，1,2）０.000０0０0.０00000ＳＯRT1(3，1，3)27.00000０.００００0０SORＴ１(3,1,４)65.00000０.000000ＳORＴ1(3，1，5)18.0０00０0．0０0000ＳORT1(3,2,3）9.０00００00.００0000SOＲT1(３，2,4)47.00０000.０00000SＯRT1(3,2,5)0.00000０0.0００00０SORT1(３,３，4)２8.0００0０0.000０00SORT1(3，3，5）８1．000000．000000SORT１(3,4,5)3８.０0０0０0.０00０00ＳORT２(３,1,2)62.0000０0.000000SＯRT2(3，１，3）4３.0００0０0.000000SORＴ2(3，1,4)０.000０0０0．000００0SＯRＴ2(3,1，５）54.00000０.00０00０SOＲＴ2(3,2,3)63.00000０．０0０000SORT2(3，2,4）20．０000０0.０0０0０0ＳOＲT2(3，2,5)74．０00000.000０00SOＲT2(3,3,４)４7.００0000.00０000ＳORT2（３,3，5)1.00０0０00.000000SORT2(3,４,5)3９.0０00０0.0０0000ＳORT1(４，１,２)13.００00０0.００0０0０ＳORT１(4,1,3）32.0000００．0000０0SORＴ1(4,1,4)87．000000.000000SORT1(４,１,５)23.０0000０.００000０SORT1(4，２，3)13．000０0０．０00000ＳＯＲT1(4，2,4)６8.０0０000.0０0000SＯRT1(4,2,5)4.00000０0.000０00SORT1(4,3,4)4８.000000.000000SORT1(4,3,5)８4.０00000．００0000ＳORT1（4，4,５)28.０0０000.000000SORＴ2（4，1,2）76.0000０0．０00000SORＴ2（4,1，3）5６.000０00.０00０00ＳＯRT２(4,1,4)０.00０00００．０0000０SＯRT2(４,1，５）６3.000000．00０000ＳORT2（4,２,３）７４.000000.０00000SＯRT2(4,2，４)18.000000.０00000ＳORT2（4,2,5)8１．0００000.００0000SＯRT2(4,3，4)３7．000０00.０00000SＯRT2(4,3，5)0.00０0000.000000SORT2(4,4,5）5５．０0０000．0００0０0附錄3問題二A的Ｌinｇｏ程序Moｄｅl:SETＳ:!Person=被面試者集合,Stage＝面試階段的集合；Person/1..5/；Stagｅ/1.．5/;!T＝已知的面試所需要的時間，X＝面試開始時間;PXＳ（Pｅrson，Ｓtage):T,X；!Y(i，k)=１:ｋ排在i前，0:否則；ＰXＰ(Ｐersoｎ,Ｐerｓｏｎ）|&１#LT#&２:Y；EＮＤSＥTSＤAＴA:T=９15171１121６791２81081４171411６6７６１715156９;ENDDAＴA[oｂj]mｉｎ=MＡXT;！MAＸT是面試的最后結(jié)束時間；MAXT>=@ｍａx(PXＳ(ｉ,ｊ)｜j#EQ#@ｓiｚe(staｇe):x(i,ｊ）+t(i,ｊ)）;!只有參與完前一個階段的面試后才干進(jìn)入下一個階段;@for(ＰＸS(i,j）|j#LT#@size(ｓtage)：[OＲDER］ｘ（i,ｊ)＋t(ｉ,j)<x(i，j+1));！同一時間只能面試１名同學(xué);@ｆor(Ｓtaｇｅ(j):＠fｏr（PXＰ（i，k):[SOＲT1]x(i，ｊ）+ｔ(i,j)-x（k,j)<MAXT*Y(ｉ,k）);@for(PＸP(i,ｋ):[ＳＯＲT2]ｘ(k,j）＋t(k,j)－x（i,j)＜MＡXT*(1-Y（i,ｋ))）;);＠foｒ(ＰXP:@biｎ(ｙ));Eｎｄ附錄4問題二A.Liｎgo運(yùn)營結(jié)果Lｏｃaloｐtｉｍalsolutｉonfound.Objｅｃtivｅｖalｕe:１01.0000Obｊectivｅｂound:10１.0000Infeasibiｌitｉeｓ:０.０000００Eｘtｅnｄedｓolveｒstｅps：５7Ｔｏtalｓolvｅriｔeraｔionｓ：77０7Elａpｓedｒuntiｍeseconｄs:9.6１MｏdｅlClass:ＭINLPTｏtaｌｖarｉａｂｌes:3６Nｏnlinearｖarｉaｂlｅs:1６Integervarｉaｂlｅs:1０Toｔalcｏnstraｉnts:１22Nonliｎeaｒｃｏnｓtｒaｉnts:1０１Toｔalｎoｎzeroｓ:44７Noｎｌｉneａrnonｚerｏｓ:205VａrｉablｅVaｌｕeReｄuceｄCostＭＡＸT1０１．0０0０0．00００00T(1，1）９.０00００00.000０00Ｔ（１,２)