面试的时间最优化问题

1、面试的时间最优化问题摘要：首先我们对给出的面试时间表格进行分析，用matlab编程算出任意两个求职者按照不同的顺序参加面试时，求职者等求职者的时间和考官等求职者的时间之和，然后用图论法建模，将算出的时间表达有向赋权图的权值，问题转化成求有向赋权图中连接四个顶点的路径最短问题。我们利用matlab编程，按从小到大的顺序依次找出n-1（n表示参加面试的人数）条权值最小边，然后用人工参与的方式，将找出的n-1条边排出最优顺序。最后，得出丁、甲、乙、丙的顺序为最优方案，共用84分钟。即：三人可在9：24一起离开公司。模型假设：（1）、假设面试者从一个阶段到下一个阶段参加面试的时间间隔为0；（2）、假定

2、中途任何一位面试者均能通过面试，进入下一阶段的面试，即没有中途退出的面试者；（3）、假定面试者都能在8：00准时到达面试地点；（4）、参加面试的求职者没有约定他们面试的先后顺序，并且他们面试的顺序与考官无关，即可以任意排列面试者的面试顺序。符号说明：i(=1,2,3,4):分别表示甲、乙、丙、丁四位同学；j(=1,2,3)：分别表示秘书初试、主管复试和经理面试的三个阶段；aij(i=1,2,3;j=1,2,3)：为求职者i在j阶段参加面试所用时间；tdk：表示在面试者中任取两名d和k，并且按d在前k在后的顺序参加面试，在该指定顺序中，k等待d的时间与考官等待k的时间之和，将tdk赋给有向赋权图

3、中由d到k的向量的权值xdk；cdk：表示在求职者中任取两名d和k，按d在前k在后的顺序参加面试，在该指定顺序中，d完成面试到k完成面试的时间间隔；s：为最优路径的总时间。问题的分析：按照公司的要求，四名求职者的顺序一旦确定，在以下各阶段中面试的顺序将不再改变，由于每个求职者，在三个阶段面试的时间不同且固定，所以对任意两名求职者a、b，按a在前，b在后的顺序进行面试时，可能存在两种情况：i、当a进行完一个阶段j的面试后，b还未完成前一阶段j-1的面试，所以j阶段的考官必须等待b完成j-1阶段的面试后，才可对b进行j阶段的面试，这样就出现了考官等待求职者的情况。ii、当b完成j-1阶段的面试后，

4、a还未完成j阶段的面试，所以，b必须等待a完成j阶段的面试后，才能进入j阶段的面试，这样就出现了求职者等待求职者(考官)的情况。以上两种情况，必然延长了整个面试过程的时间。要想使四个求职者能一起最早离开公司，即他们所用的面试时间最短，只要是考官等候求职者的时间和求职者等候求职者(考官)的时间之和最短，这样就使求职者和考官的时间利用率达到了最高，他们就能以最短的时间完成面试一起离开公司。模型的建立与求解：首先由题中所给条件可得原始时间矩阵： aij=a11a12a13a21a22a23a31a32a33a14a43a43为：13152010201820161081015下面我们来求有向赋权图的权

5、值：由题意分析，求权值tdk可分为三种情况：1. 当a22-a11=0，a23-a12=0，说明若按顺序21（乙甲）则1（甲）想进入第二阶段参加面试，需等候2（乙）的时间为（a22-a11），想进入第三阶段面试需等候2（乙）的时间为（a23-a12）。则：t21=(a22-a11)+(a23-a12)。此时时间差c21=a13，因为1（甲）求职者是在等候2（乙）求职者完成第三阶段的面试后才进入第三阶段进行面试，而1（甲）求职者在第三阶段面试共需时间a13，即是他俩完成各自面试的时间差值。2.当a22-a110，a23-a121（乙甲）进行面试，1（甲）想进入第二阶段参加面试，需等候2（乙）的时

6、间为（a22-a11），想进入第三阶段面试，第三阶段的主考官需等候1（甲）求职者的时间为（a23-a12），则：t21=（a22-a11）+|a23-a12| 此时时间差c21=| a23-a12 |+a13，因为第3阶段的主考官在给1（甲）进行面试前已经等候的时间为|a23-a12|，而1（甲）在进行第三阶段的面试时间是a13，故是两时间之和。3. 当a22-a111（乙甲）进行面试，第二阶段主考官需等候1（甲）求职者的时间为|a22-a11|，而这段时间的拖延，导致了第三阶段的考官也等候1（甲）的时间为| a22-a11 |，不管a23-a120，还是a23-a12=0时1)tdk=| a

7、d2-ak1 |+| ad3-ak2 |2)当ad3-ak2=0时，cdk=ak33)当ad3-ak30时，cdk=| ad3-ak2 | + ak32.当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