面試的時間最優(yōu)化問題

1、面試的時間最優(yōu)化問題摘要：首先我們對給出的面試時間表格進(jìn)行分析，用matlab編程算出任意兩個求職者按照不同的順序參加面試時，求職者等求職者的時間和考官等求職者的時間之和，然后用圖論法建模，將算出的時間表達(dá)有向賦權(quán)圖的權(quán)值，問題轉(zhuǎn)化成求有向賦權(quán)圖中連接四個頂點的路徑最短問題。我們利用matlab編程，按從小到大的順序依次找出n-1（n表示參加面試的人數(shù)）條權(quán)值最小邊，然后用人工參與的方式，將找出的n-1條邊排出最優(yōu)順序。最后，得出丁、甲、乙、丙的順序為最優(yōu)方案，共用84分鐘。即：三人可在9：24一起離開公司。模型假設(shè)：（1）、假設(shè)面試者從一個階段到下一個階段參加面試的時間間隔為0；（2）、假定

2、中途任何一位面試者均能通過面試，進(jìn)入下一階段的面試，即沒有中途退出的面試者；（3）、假定面試者都能在8：00準(zhǔn)時到達(dá)面試地點；（4）、參加面試的求職者沒有約定他們面試的先后順序，并且他們面試的順序與考官無關(guān)，即可以任意排列面試者的面試順序。符號說明：i(=1,2,3,4):分別表示甲、乙、丙、丁四位同學(xué)；j(=1,2,3)：分別表示秘書初試、主管復(fù)試和經(jīng)理面試的三個階段；aij(i=1,2,3;j=1,2,3)：為求職者i在j階段參加面試所用時間；tdk：表示在面試者中任取兩名d和k，并且按d在前k在后的順序參加面試，在該指定順序中，k等待d的時間與考官等待k的時間之和，將tdk賦給有向賦權(quán)圖

3、中由d到k的向量的權(quán)值xdk；cdk：表示在求職者中任取兩名d和k，按d在前k在后的順序參加面試，在該指定順序中，d完成面試到k完成面試的時間間隔；s：為最優(yōu)路徑的總時間。問題的分析：按照公司的要求，四名求職者的順序一旦確定，在以下各階段中面試的順序?qū)⒉辉俑淖?，由于每個求職者，在三個階段面試的時間不同且固定，所以對任意兩名求職者a、b，按a在前，b在后的順序進(jìn)行面試時，可能存在兩種情況：i、當(dāng)a進(jìn)行完一個階段j的面試后，b還未完成前一階段j-1的面試，所以j階段的考官必須等待b完成j-1階段的面試后，才可對b進(jìn)行j階段的面試，這樣就出現(xiàn)了考官等待求職者的情況。ii、當(dāng)b完成j-1階段的面試后，

4、a還未完成j階段的面試，所以，b必須等待a完成j階段的面試后，才能進(jìn)入j階段的面試，這樣就出現(xiàn)了求職者等待求職者(考官)的情況。以上兩種情況，必然延長了整個面試過程的時間。要想使四個求職者能一起最早離開公司，即他們所用的面試時間最短，只要是考官等候求職者的時間和求職者等候求職者(考官)的時間之和最短，這樣就使求職者和考官的時間利用率達(dá)到了最高，他們就能以最短的時間完成面試一起離開公司。模型的建立與求解：首先由題中所給條件可得原始時間矩陣： aij=a11a12a13a21a22a23a31a32a33a14a43a43為：13152010201820161081015下面我們來求有向賦權(quán)圖的權(quán)

5、值：由題意分析，求權(quán)值tdk可分為三種情況：1. 當(dāng)a22-a11=0，a23-a12=0，說明若按順序21（乙甲）則1（甲）想進(jìn)入第二階段參加面試，需等候2（乙）的時間為（a22-a11），想進(jìn)入第三階段面試需等候2（乙）的時間為（a23-a12）。則：t21=(a22-a11)+(a23-a12)。此時時間差c21=a13，因為1（甲）求職者是在等候2（乙）求職者完成第三階段的面試后才進(jìn)入第三階段進(jìn)行面試，而1（甲）求職者在第三階段面試共需時間a13，即是他倆完成各自面試的時間差值。2.當(dāng)a22-a110，a23-a121（乙甲）進(jìn)行面試，1（甲）想進(jìn)入第二階段參加面試，需等候2（乙）的時

6、間為（a22-a11），想進(jìn)入第三階段面試，第三階段的主考官需等候1（甲）求職者的時間為（a23-a12），則：t21=（a22-a11）+|a23-a12| 此時時間差c21=| a23-a12 |+a13，因為第3階段的主考官在給1（甲）進(jìn)行面試前已經(jīng)等候的時間為|a23-a12|，而1（甲）在進(jìn)行第三階段的面試時間是a13，故是兩時間之和。3. 當(dāng)a22-a111（乙甲）進(jìn)行面試，第二階段主考官需等候1（甲）求職者的時間為|a22-a11|，而這段時間的拖延，導(dǎo)致了第三階段的考官也等候1（甲）的時間為| a22-a11 |，不管a23-a120，還是a23-a12=0時1)tdk=| a

7、d2-ak1 |+| ad3-ak2 |2)當(dāng)ad3-ak2=0時，cdk=ak33)當(dāng)ad3-ak30時，cdk=| ad3-ak2 | + ak32.當(dāng)ad2-ak1=0; rst(count1,count2)=abs(col2(count1)-col1(count2)+abs(col3(count1)-col2(count2); elserst(count1,count2)=2*abs(col2(count1)-col1(count2)+abs(col3(count1)-col2(count2); end; if count1=count2 rst(count1,count2)=inf;

8、 end; end;end;crtpower(a)附錄二：function rst=findminparam(a,icount,diff)%*% this is help information about findminparam() function.% find the min number in defferent rows and cols the matrix.% verison:1.1.2 finish date:28/08/2004 % usage:% findminparam(a,icount,diff)% a is matrix .% icount is counter.%

9、 diff is the parame to find the mininum in different row. %*a=13,15,20;10,20,18;20,16,10;8,10,15;if nargout1 error(too many output arguments!);else if (nargin=0 | nargin3) error(too many input arguments!); else cols=length(a(1,:); rows=length(a(:,1); if nargin=1 icount=rows * cols; diff=0; end; if n

10、argin=2 | nargin=3 if icountrows * cols error(the search number is too big!); icount=rows * cols; elseif icount1 error(the mininum is 1); icount=1; else icount=icount; end; if nargin=3 if diff=1 diff=1; else diff=0; end; else diff=0; end; end; rst=zeros(icount,3); for count=1:icount succ=0; for rowcount=1:rows; for colcount=1:cols; if (min(min(a)=a(rowcount,colcount); tmpmin=min(min(a); tmprow=rowcount; tmpcol=colcount; if diff=1 a(rowcount,:)=inf; a(:,colcount)=inf; else a(rowcount,colcount)=inf; end; succ=1; break; end; en