面试的时间最优化问题
面试的时间最优化问题
摘要:首先我们对给出的面试时间表格进行分析,用MATLAB编程算出任意两个求职者按照不同的顺序参加面试时,求职者等求职者的时间和考官等求职者的时间之和,然后用图论法建模,将算出的时间表达有向赋权图的权值,问题转化成求有向赋权图中连接四个顶点的路径最短问题。我们利用MATLAB编程,按从小到大的顺序依次找出n-1(n表示参加面试的人数)条权值最小边,然后用人工参与的方式,将找出的n-1条边排出最优顺序。最后,得出丁、甲、乙、丙的顺序为最优方案,共用84分钟。即:三人可在9:24一起离开公司。 模型假设: (1)、假设面试者从一个阶段到下一个阶段参加面试的时间间隔为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的时间与考官等待K的时间之和,将tDK赋给有向赋权图中由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阶段的面试后,A还未完成j阶段的面试,所以,B必须等待A完成j阶段的面试后,才能进入j阶段的面试,这样就出现了求职者等待求职者(考官)的情况。以上两种情况,必然延长了整个面试过程的时间。要想使四个求职者能一起最早离开公司,即他们所用的面试时间最短,只要是考官等候求职者的时间和求职者等候求职者(考官)的时间之和最短,这样就使求职者
和考官的时间利用率达到了最高,他们就能以最短的时间完成面试一起离开公司。 模型的建立与求解:
首先由题中所给条件可得原始时间矩阵:
Aij=a11
a21
a31
a14 a12 a22 a32 a43
15
20
16
10 a13 a23 a33 a43 20 18 10 15 为:13 10 20 8
下面我们来求有向赋权图的权值:由题意分析,求权值tDK可分为三种情况:
1. 当a22-a11>=0,a23-a12>=0,说明若按顺序2—>1(乙—>甲)则1(甲)想进入第二阶段参加面试,需等候2(乙)的时间为(a22-a11),想进入第三阶段面试需等候2(乙)的时间为(a23-a12)。则:t21=(a22-a11)+(a23-a12)。
此时时间差c21=a13,因为1(甲)求职者是在等候2(乙)求职者完成第三阶段的面试后才进入第三阶段进行面试,而1(甲)求职者在第三阶段面试共需时间a13,即是他俩完成各自面试的时间差值。
2.当a22-a11>0,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(甲)求职者的时间为|a22-a11|,而这段时间的拖延,导致了第三阶段的考官也等候1(甲)的时间为| a22-a11 |,不管a23-a12>0,还是a23-a12
算法总结:
通过以上假设讨论,我们总结出计算权值tDK及时间差cDK的方法:
1.当aD2-aK1>=0时
1)tDK=| aD2-aK1 |+| aD3-aK2 |
2)当aD3-aK2>=0时,cDK=aK3
3)当aD3-aK3
2.当aD2-aK1
tDK=| 2*(aD2-aK1)+(aD3-aK2) |
cDK=| 2*(aD2-aK1)+(aD3-aK2) |+aK3
以上算法可以通过MatLab编程实现(见附一)。由运行结果可得: TDK= 0 5 6 17
10 0 2 20
8 16 0 8
6 5 21 0
然后我们用MatLab找出TDK中的最短路径(见附二)。经程序运行得出权值最小的边为:t41,t12,t23。即顺序为丁甲、甲乙、乙丙。可得出最优的顺序为:丁甲乙丙。
所以最优路径的总时间为:S=丁所用总时间+c41+c12+c23=84min
综上所述,完成所有面试至少需要84分钟,即9点24分为他们的最早离开时间。面试顺序为:4-1-2-3(丁-甲-乙-丙)。
附录
附录一:
function rst=CrtPower(a) %Find the Power of the matrix. %**********************************************************
% This is Help Information About Power() Function.
% Find the min number in the matrix.
% Verison:1.0.0 Finish Date:27/08/2004
% Usage:
% Power(a) %a is matrix .
% return a rst.
%***********************************************************
a=[13,15,20;10,20,18;20,16,10;8,10,15;];
Rows=length(a(:,1)); %Get the Rows of the matrix.
Col1=a(:,1);
Col2=a(:,2);
Col3=a(:,3);
rst=zeros(Rows);
for Count1=1:Rows;
for Count2=1:Rows;
if Col2(Count1)-Col1(Count2)>=0;
rst(Count1,Count2)=abs(Col2(Count1)-Col1(Count2))+abs(Col3(Count1)-Col2(Count2));
else
rst(Count1,Count2)=2*abs(Col2(Count1)-Col1(Count2))+abs(Col3(Count1)-Col2(Count2));
end;
if Count1==Count2
rst(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:
% FindMinParam(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;];
if nargout>1
error('Too many output arguments!');
else
if (nargin==0 | nargin>3)
error('Too many input arguments!');
else
Cols=length(a(1,:));
Rows=length(a(:,1));
if nargin==1
iCount=Rows * Cols;
Diff=0;
end;
if nargin==2 | nargin==3
if iCount>Rows * Cols
error('The search number is too big!'); iCount=Rows * Cols;
elseif iCount
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;
end %End For
if 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)