試談面試時(shí)間優(yōu)化安排

17/17面試時(shí)刻優(yōu)化安排一：提出問題：問題是如此產(chǎn)生的：有4名同學(xué)到一家公司參加三個(gè)時(shí)期的面試，公司要求每個(gè)同學(xué)都必須首先找公司秘書初試，然后到部門主管處復(fù)試，最后到經(jīng)理處參加面試，同時(shí)不同意插隊(duì)（即：在任何一個(gè)時(shí)期4名同學(xué)的順序是一樣的），由于4名同學(xué)的專業(yè)背景不同，因此每人在三個(gè)時(shí)期的面試時(shí)刻也不同，如下表所示：（單位：分鐘）秘書初試主管復(fù)試經(jīng)理面試同學(xué)甲131520同學(xué)乙102018同學(xué)丙201610同學(xué)丁81015這四名同學(xué)約定他們?nèi)棵嬖囃瓿梢院笠黄痣x開公司，假定現(xiàn)在時(shí)刻食早晨8：00，問他們最早何時(shí)能離開公司？能夠看到，那個(gè)例子是日常生活中常見的，尤其是還有一年就要畢業(yè)的我們，面試是找工作時(shí)必不可少的一個(gè)環(huán)節(jié)，幾個(gè)好朋友相約一同面試如此的問題是極有可能發(fā)生的，因此提出了如此的一個(gè)問題：好朋友約定全部面試完畢后一同離開公司，那么，如何來安排面試的順序呢？在當(dāng)今那個(gè)節(jié)約型社會(huì)，一切都提倡綠色，節(jié)約，重復(fù)利用；那么如何來最大限度地縮短總面試的時(shí)刻來達(dá)到我們節(jié)約型社會(huì)所提出的要求呢？我們從安排面試時(shí)刻那個(gè)小小的問題來看吧，從表中的數(shù)據(jù)，我們隨手算算便能夠看到面試順序的不同，最終造成的面試總時(shí)刻也是有長有短的。那個(gè)問題有點(diǎn)類似于小時(shí)候遇到的燒開水的問題，是時(shí)刻統(tǒng)籌的一種簡單應(yīng)用。二：問題的分析：按照公司給出的要求，四名求職者的順序一旦確定以后，在秘書初試、主管復(fù)試、經(jīng)理面試各時(shí)期中面試的順序?qū)⒉辉俑淖?，由于每個(gè)求職者在三個(gè)時(shí)期面試的時(shí)刻不同（且固定），我們考慮對(duì)任意兩名求職者P、Q，不妨設(shè)按P在前，Q在后的順序進(jìn)行面試，可能存在以下兩種情況：（一）、當(dāng)P進(jìn)行完一個(gè)時(shí)期j的面試后，Q還未完成前一時(shí)期j-1的面試，因此j時(shí)期的考官必須等待Q完成j-1時(shí)期的面試后，才可對(duì)Q進(jìn)行j時(shí)期的面試，如此就出現(xiàn)了考官等待求職者的情況。這一段等待時(shí)刻必將延長最終的總時(shí)刻。（二）、當(dāng)Q完成j-1的面試后，P還未完成j時(shí)期的面試，因此，Q必須等待P完成j時(shí)期的面試后，才能進(jìn)入j時(shí)期的面試，如此就出現(xiàn)了求職者等待求職者的情況。同樣的，那個(gè)也會(huì)延長面試的總時(shí)刻。以上兩種情況，必定都會(huì)延長整個(gè)面試過程。因此要想使四個(gè)求職者能一起最早離開公司，即他們所用的面試時(shí)刻最短，只要使考官等候求職者的時(shí)刻和求職者等候求職者的時(shí)刻之和最短，如此就使求職者和考官的時(shí)刻利用率達(dá)到了最高。他們就能以最短的時(shí)刻完成面試一起離開公司。這也是我們想要的結(jié)果。從那個(gè)問題中我們能夠聯(lián)想到該問題涉及的面試時(shí)刻與人數(shù)有一定關(guān)系，若想節(jié)約時(shí)刻，專門值得推廣。發(fā)散地考慮，大多數(shù)工廠的流水線的裝配也有類似的思想，因此如此的一個(gè)模型專門有推廣的意義。三：模型假設(shè)：1.我們假設(shè)參加面試的求職者差不多上平等且獨(dú)立的，即他們面試的順序與考官無關(guān)；2.面試者由一個(gè)時(shí)期到下一個(gè)時(shí)期參加面試，其間必有時(shí)刻間隔，但我們?cè)谀莻€(gè)地點(diǎn)假定該時(shí)刻間隔為0；3.參加面試的求職者事先沒有約定他們面試的先后順序；4.假定中途任何一位參加面試者均能通過面試，進(jìn)入下一時(shí)期的面試。即：沒有中途退出面試者；5.面試者及各考官都能在8：00準(zhǔn)時(shí)到達(dá)面試地點(diǎn)。四：模型建立：決策變量：記tij為第i名同學(xué)參加第j時(shí)期面試需要的時(shí)刻（已知見表），令xij表示第i名同學(xué)參加第j時(shí)期面試的開始時(shí)刻（在那個(gè)地點(diǎn)我們不妨記早上8：00面試開始時(shí)刻為0時(shí)刻）（i=1，2，3，4；j=1，2，3）顯然它們都應(yīng)當(dāng)是非負(fù)整數(shù)。決策目標(biāo)：第三時(shí)期面試的開始時(shí)刻+第三時(shí)期面試的時(shí)刻T=Max{xij+tij}（j=3），求出T的最小值即是我們最終想要優(yōu)化的目標(biāo)。約束條件：時(shí)刻先后次序約束，即是講每個(gè)人只有參加完前一個(gè)時(shí)期的面試后才能進(jìn)入下一個(gè)時(shí)期；Xij+tij<=Xij+1（i=1，2，3，4；j=1，2，3）2）每個(gè)時(shí)期j同一時(shí)刻只能面試1名同學(xué)：用0-1變量yik表示第k名同學(xué)是否排在第i名同學(xué)前面（1表示是，0表示否）則有：Xij+tij-xkj<=T*yik(i,k=1,2,3,4;j=1,2,3;i<=k)Xkj+tkj-Xij<=T*(1-yik)(i,k=1,2,3,4;j=1,2,3;i<=k)因此我們的目標(biāo)函數(shù)為：MinT；T=Max{xij+tij}；連同約束條件，輸入LINGO求解：代碼如下：model:min=T;x41+8<x42;x42+10<x43;x31+20<x32;x32+16<x33;x21+10<x22;x22+20<x23;x11+13<x12;x12+15<x13;T>x43+15;T>x33+10;T>x23+18;T>x13+20;x31+20-x41<T*y34;x32+16-x42<T*y34;x33+10-x43<T*y34;x21+10-x31<T*y23;x22+20-x32<T*y23;x23+18-x33<T*y23;x21+10-x41<T*y24;x22+20-x42<T*y24;x23+18-x43<T*y24;x11+13-x21<T*y12;x12+15-x22<T*y12;x13+20-x23<T*y12;x11+13-x31<T*y13;x12+15-x32<T*y13;x13+20-x33<T*y13;x11+13-x41<T*y14;x12+15-x42<T*y14;x13+20-x43<T*y14;x41+8-x31<T*(1-y34);x42+10-x32<T*(1-y34);x43+15-x33<T*(1-y34);x41+8-x21<T*(1-y24);x42+10-x22<T*(1-y24);x43+15-x23<T*(1-y24);x31+20-x21<T*(1-y23);x32+16-x22<T*(1-y23);x33+10-x23<T*(1-y23);x21+10-x11<T*(1-y12);x22+20-x12<T*(1-y12);x23+18-x13<T*(1-y12);x31+20-x11<T*(1-y13);x32+16-x12<T*(1-y13);x33+10-x13<T*(1-y13);x41+8-x11<T*(1-y14);x42+10-x12<T*(1-y14);x43+15-x13<T*(1-y14);@bin(y34);@bin(y12);@bin(y13);@bin(y14);@bin(y23);@bin(y24);end得到：Localoptimalsolutionfoundatiteration:3104Objectivevalue:84.00000VariableValueReducedCostT84.000000.000000X410.0000000.9999970X429.5000000.000000X4321.000000.000000X3132.500000.000000X3258.000000.000000X3374.000000.000000X2122.500000.000000X2236.000000.000000X2356.000000.000000X118.0000000.000000X1221.000000.000000X1336.000000.000000Y341.0000000.000000Y230.000000-83.99950Y241.0000000.000000Y120.000000-83.99950Y130.0000000.000000Y141.00000083.99950RowSlackorSurplusDualPrice184.00000-1.00000021.5000000.00000031.5000000.00000045.5000000.00000050.0000000.00000063.5000000.00000070.0000000.999997080.0000000.999997090.0000000.0000001048.000000.000000110.000000-0.99999701210.000000.0000001328.000000.0000001431.500000.0000001519.500000.0000001621.000000.000000170.0000000.000000182.0000000.000000190.0000000.99999702051.500000.0000002137.500000.0000002231.000000.000000231.5000000.000000240.0000000.9999970250.0000000.0000002611.500000.0000002722.000000.0000002818.000000.0000002963.000000.0000003057.500000.0000003149.000000.0000003224.500000.0000003338.500000.0000003438.000000.0000003514.500000.0000003616.500000.0000003720.000000.0000003854.000000.0000003946.000000.0000004056.000000.0000004159.500000.