《面试的时间最优化问题》由会员分享,可在线阅读,更多相关《面试的时间最优化问题(9页珍藏版)》请在金锄头文库上搜索。
1、1面试的时间最优化问题摘要:首先我们对给出的面试时间表格进行分析,用 MATLAB编程算出任意两个求职者按照不同的顺序参加面试时,求职者等求职者的时间和考官等求职者的时间之和,然后用图论法建模,将算出的时间表达有向赋权图的权值,问题转化成求有向赋权图中连接四个顶点的路径最短问题。我们利用 MATLAB编程,按从小到大的顺序依次找出 n-1(n 表示参加面试的人数)条权值最小边,然后用人工参与的方式,将找出的 n-1条边排出最优顺序。最后,得出丁、甲、乙、丙的顺序为最优方案,共用 84分钟。即:三人可在 9:24 一起离开公司。模型假设:(1) 、假设面试者从一个阶段到下一个阶段参加面试的时间间
2、隔为 0;(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的时
3、间与考官等待 K的时间之和,将 tDK赋给有向赋权图中由 D到 K的向量的权值 xDK;2cDK:表示在求职者中任取两名 D和 K,按 D在前 K在后的顺序参加面试,在该指定顺序中,D完成面试到 K完成面试的时间间隔;S:为最优路径的总时间。问题的分析:按照公司的要求,四名求职者的顺序一旦确定,在以下各阶段中面试的顺序将不再改变,由于每个求职者,在三个阶段面试的时间不同且固定,所以对任意两名求职者 A、B,按 A在前,B 在后的顺序进行面试时,可能存在两种情况:I、当 A进行完一个阶段 j的面试后,B 还未完成前一阶段 j-1的面试,所以 j阶段的考官必须等待 B完成 j-1阶段的面试后,才可
4、对 B进行 j阶段的面试,这样就出现了考官等待求职者的情况。II、当 B完成j-1阶段的面试后,A 还未完成 j阶段的面试,所以,B 必须等待 A完成 j阶段的面试后,才能进入 j阶段的面试,这样就出现了求职者等待求职者(考官)的情况。以上两种情况,必然延长了整个面试过程的时间。要想使四个求职者能一起最早离开公司,即他们所用的面试时间最短,只要是考官等候求职者的时间和求职者等候求职者(考官)的时间之和最短,这样就使求职者和考官的时间利用率达到了最高,他们就能以最短的时间完成面试一起离开公司。模型的建立与求解:首先由题中所给条件可得原始时间矩阵: Aij=a11 a12 a13a21 a22 a
5、23a31 a32 a33a14 a43 a43为:13 15 20310 20 1820 16 108 10 15下面我们来求有向赋权图的权值:由题意分析,求权值 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(甲)求职者在第三
6、阶段面试共需时间 a13,即是他俩完成各自面试的时间差值。2.当 a22-a110,a23-a121(乙甲)进行面试,1(甲)想进入第二阶段参加面试,需等候 2(乙)的时间为(a22-a11) ,想进入第三阶段面试,第三阶段的主考官需等候 1(甲)求职者的时间为(a23-a12) ,则:t21=(a22-a11)+|a23-a12|此时时间差 c21=| a23-a12 |+a13,因为第 3阶段的主考官在给 1(甲)进行面试前已经等候的时间为|a23-a12|,而 1(甲)在进行第三阶段的面试时间是 a13,故是两时间之和。3. 当 a22-a111(乙甲)进行面试,第二阶段主考官需等候 1
7、(甲)求职者的时间为|a22-a11|,而这段时间的拖延,导致了第三阶段的考官也等候 1(甲)的时间为| a22-a11 |,不管 a23-a120,还是 a23-a12=0时1)tDK=| aD2-aK1 |+| aD3-aK2 |2)当 aD3-aK2=0时,cDK=aK33)当 aD3-aK3=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(Coun
8、t1)-6Col2(Count2);end;if Count1=Count2rst(Count1,Count2)=inf;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:% Find
9、MinParam(a,iCount,Diff)% a is matrix .% iCount is Counter.% Diff is the parame to Find the mininum in Different Row. %*a=13,15,20;10,20,18;20,16,10;8,10,15;7if nargout1 error(Too many output arguments!);elseif (nargin=0 | nargin3)error(Too many input arguments!);elseCols=length(a(1,:);Rows=length(a(
10、:,1);if nargin=1iCount=Rows * Cols;Diff=0;end;if nargin=2 | nargin=3 if iCountRows * Colserror(The search number is too big!);iCount=Rows * Cols;elseif iCount1error(The mininum is 1);iCount=1;elseiCount=iCount;end;8if nargin=3if Diff=1Diff=1;elseDiff=0;end;elseDiff=0;end;end;rst=zeros(iCount,3);for
11、Count=1:iCountSucc=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=1a(RowCount,:)=inf; 9a(:,ColCount)=inf;elsea(RowCount,ColCount)=inf;end;Succ=1; break; end;end %End Forif Succ=1 break;end;end;if Succ=1 rst(Count,1)=tmpMin;rst(Count,2)=tmpRow;rst(Count,3)=tmpCol;end;end; disp(rst);end;end;FindMinParam(CrtPower(a),3,1)