1、面試時間優化安排一：提出問題：問題是這樣產生的：有4名同學到一家公司參加三個階段的面試，公司要求每個同學都必須首先找公司秘書初試，然后到部門主管處復試，最后到經理處參加面試，并且不允許插隊（即：在任何一個 階段4名同學的順序是一樣的），由于4名同學的專業背景不同，所以每人在三個階段的面 試時間也不同，如下表所示：（單位：分鐘）秘書初試主管復試經理面試同學甲-三-一五20同學乙1020一八同學丙201610同學丁810一五這四名同學約定他們全部面試完成以后一起離開公司，假定現在時間食早晨& 00,問他們最早何時能離開公司?可以看到，這個例子是日常生活中常見的，尤其是還有一年就要畢業的我們，面試是

2、找提出了這樣的一個問題： 好朋友約定全部面試完畢后一同離開公司，那么， 如何來安排面試的順序呢？在當今這個節約型社會， 一切都提倡綠色，節約， 重復利用； 那么如何來最大限度地縮 短總面試的時間來達到我們節約型社會所提出的要求呢？我們從安排面試時間這個小小的 問題來看吧， 從表中的數據， 我們隨手算算便可以看到面試順序的不同，最終造成的面試總時間也是有長有短的。 這個問題有點類似于小時候遇到的燒開水的問題，是時間統籌的一種簡單應用。二：問題的分析：按照公司給出的要求，四名求職者的順序一旦確定以后， 在秘書初試、 主管復試、 經理 面試各階段中面試的順序將不再改變，由于每個求職者在三個階段面試的

3、時間不同（且固 定），我們考慮對任意兩名求職者P、Q,不妨設按P在前，Q在后的順序進行面試，可能存在以下兩種情況：（一）、當P進行完一個階段j的面試后，Q還未完成前一階段j-1的面試，所以j階段 的考官必須等待 Q完成j-1階段的面試后，才可對Q進行j階段的面試，這樣就出現了考官 等待求職者的情況。這一段等待時間必將延長最終的總時間。（二）、當Q完成j-1的面試后，P還未完成j階段的面試，所以，Q必須等待P完成j 階段的面試后，才能進入 j 階段的面試，這樣就出現了求職者等待求職者的情況。同樣的， 這個也會延長面試的總時間。以上兩種情況， 必然都會延長整個面試過程。 所以要想使四個求職者能一起

4、最早離開公 司，即他們所用的面試時間最短， 只要使考官等候求職者的時間和求職者等候求職者的時間 之和最短， 這樣就使求職者和考官的時間利用率達到了最高。 他們就能以最短的時間完成面 試一起離開公司。這也是我們想要的結果。從這個問題中我們可以聯想到該問題涉及的面試時間與人數有一定關系，若想節省時 間，很值得推廣。發散地考慮， 大多數工廠的流水線的裝配也有類似的思想，所以這樣的一 個模型很有推廣的意義。三：模型假設：我們假設參加面試的求職者都是平等且獨立的，即他們面試的順序與考官無關；面試者由一個階段到下一個階段參加面試，其間必有時間間隔，但我們在這里假定該時間間隔為 0；參加面試的求職者事先沒有

5、約定他們面試的先后順序；假定中途任何一位參加面試者均能通過面試，進入下一階段的面試。即：沒有中途退出面面試者及各考官都能在8：00 準時到達面試地點。四：模型建立：決策變量：記 tij 為第 i 名同學參加第 j 階段面試需要的時間（已知見表） ，令 xij 表示第 i 名同學參加 第j階段面試的開始時刻（在這里我們不妨記早上& 00面試開始時間為0時刻）（i=1 , 2,3， 4； j=1 ， 2， 3）顯然它們都應當是非負整數。決策目標：第三階段面試的開始時間+第三階段面試的時間T=Max Xij +tj （j=3），求出T的最小值即是我們最終想要優化的目標。約束條件：1）時間先后次序約束

6、，即是說每個人只有參加完前一個階段的面試后才能進入下一個階段；Xij+tij=Xij+1 （ i=1 ， 2， 3， 4；j=1 ， 2， 3）2）每個階段 j 同一時間只能面試 1 名同學：用 0-1 變量 yik 表示第 k 名同學是否排在第 i 名 同學前面（ 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）于是我們的目標函數為：Min T；T=Max xij +tij；連同約束條件，輸入 LINGO 求解：代碼如下：mode

7、l: min=T;x41+8x42;x42+10 x43;x31+20 x32;x32+16x33;x21+10 x22;x22+20 x23;x11 + 一三 x12; x12+ 一五 x43+ 一五 ;Tx33+10;Tx23+ 一八 ; Tx 一三 +20; x31+20-x41T*y34; x32+16-x42T*y34; x33+10-x43T*y34; x21+10-x31T*y23;x22+20-x32T*y23; x23+ 一八-x33T*y23;x21+10-x41T*y24; x22+20-x42T*y24;x23+ 一八-x43T*y24; x11+ 一三 -x21T*y

8、12; x12+ 一五 -x22T*y12;x 一三 +20-x23T*y12; x11+ 一三 -x31T*y 一 x12+ 一五 -x32T*y 一 x 一三 +20-x33T*y 一 x11+ 一三 -x41T*y14; x12+ 一五 -x42T*y14;x 一三 +20-x43T*y14;x41+8-x31T*(1-y34); x42+10-x32T*(1-y34);x43+ 一五-x33T*(1-y34); x41+8-x21T*(1-y24); x42+10-x22T*(1-y24);x43+ 一五-x23T*(1-y24);x31+20-x21T*(1-y23);x32+16-

9、x22T*(1-y23);x33+10-x23T*(1-y23);x21+10-x11T*(1-y12);x22+20-x12T*(1-y12);x23+ 一八-x 一三 T*(1-y12);x31+20-x11T*(1-y 一三 );x32+16-x12T*(1-y 一三); x33+10-x 一三 T*(1-y 一三); x41+8-x11T*(1-y14); x42+10-x12T*(1-y14);x43+ 一五-x 一三 T*(1-y14);xbin(y34);xbin(y12);xbin(y三);xbin(y14);xbin(y23);xbin(y24);end得到：Local op

10、timal solution found at iteration: Objective value:310484.00000VariableValueReduced CostT84.000000.000000X410.0000000.9999970X429.5000000.000000X4321.000000.000000X3132.500000.000000X3258.000000.000000X3374.000000.000000X2122.500000.000000X2236.000000.000000X2356.000000.000000X118.0000000.000000X122

11、1.000000.000000X 一三36.000000.000000Y341.0000000.000000Y230.000000-83.99950Y241.0000000.000000Y120.000000-83.99950Y 一三0.0000000.000000Y141.00000083.99950RowSlack or SurplusDual Price184.00000-1.00000021.5000000.00000031.5000000.00000045.5000000.00000050.0000000.00000063.5000000.00000070.0000000.99999

12、7080.0000000.999997090.0000000.0000001048.000000.000000110.000000-0.99999701210.000000.000000一三28.000000.0000001431.500000.000000一五19.500000.0000001621.000000.000000170.0000000.000000一八2.0000000.000000190.0000000.99999702051.500000.0000002137.500000.0000002231.000000.000000231.5000000.000000240.0000

13、000.9999970250.0000000.0000002611.500000.0000002722.000000.00000028一八 .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.00