面试时间优化安排
一：提出问题：
问题是这样产生的：
有4名同学到一家公司参加三个阶段的面试，公司要求每个同学都必须首先找公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且不允许插队〔即：在任何一个阶段4名同学的顺序是一样的〕，由于4名同学的专业背景不同，所以每人在三个阶段的面试时间也不同，如下表所示：〔单位：分钟〕
秘书初试
主管复试
经理面试
同学甲
同学乙
同学丙
同学丁
这四名同学约定他们全部面试完成以后一起离开公司，假定现在时间食早晨8：00，问他们最早何时能离开公司？
可以看到，这个例子是日常生活中常见的，尤其是还有一年就要毕业的我们，面试是找工作时必不可少的一个环节，几个好朋友相约一同面试这样的问题是极有可能发生的，所以提出了这样的一个问题：好朋友约定全部面试完毕后一同离开公司，那么，如何来安排面试的顺序呢？
在当今这个节约型社会，一切都提倡绿色，节约，重复利用；那么如何来最大限度地缩短总面试的时间来到达我们节约型社会所提出的要求呢？我们从安排面试时间这个小小的问题来看吧，从表中的数据，我们随手算算便可以看到面试顺序的不同，最终造成的面试总时间也是有长有短的。这个问题有点类似于小时候遇到的烧开水的问题，是时间统筹的一种简单应用。
二：问题的分析：
按照公司给出的要求，四名求职者的顺序一旦确定以后，在秘书初试、主管复试、经理面试各阶段中面试的顺序将不再改变，由于每个求职者在三个阶段面试的时间不同〔且固定〕，我们考虑对任意两名求职者P、Q，不妨设按P在前，Q在后的顺序进行面试，可能存在以下两种情况：
〔一〕、当P进行完一个阶段j的面试后，Q还未完成前一阶段j-1的面试，所以j阶段的考官必须等待Q完成j-1阶段的面试后，才可对Q进行j阶段的面试，这样就出现了考官等待求职者的情况。这一段等待时间必将延长最终的总时间。
〔二〕、当Q完成j-1的面试后，P还未完成j阶段的面试，所以，Q必须等待P完成j阶段的面试后，才能进入j阶段的面试，这样就出现了求职者等待求职者的情况。同样的，这个也会延长面试的总时间。
以上两种情况，必然都会延长整个面试过程。所以要想使四个求职者能一起最早离开公司，即他们所用的面试时间最短，只要使考官等候求职者的时间和求职者等候求职者的时间之和最短，这样就使求职者和考官的时间利用率到达了最高。他们就能以最短的时间完成面试一起离开公司。这也是我们想要的结果。
从这个问题中我们可以联想到该问题涉及的面试时间与人数有一定关系，假设想节省时间，很值得推广。发散地考虑，大多数工厂的流水线的装配也有类似的思想，所以这样的一个模型很有推广的意义。
三：模型假设：
1.我们假设参加面试的求职者都是平等且独立的，即他们面试的顺序与考官无关；
2.面试者由一个阶段到下一个阶段参加面试，其间必有时间间隔，但我们在这里假定该时间间隔为0；
3.参加面试的求职者事先没有约定他们面试的先后顺序；
4.假定中途任何一位参加面试者均能通过面试，进入下一阶段的面试。即：没有中途退出面试者；
5.面试者及各考官都能在8：00准时到达面试地点。
四：模型建立：
决策变量：
记tij
为第i名同学参加第j阶段面试需要的时间〔见表〕，令xij
表示第i名同学参加第j阶段面试的开始时刻〔在这里我们不妨记早上8：00面试开始时间为0时刻〕〔i=1，2，3，4；j=1，2，3〕显然它们都应当是非负整数。
决策目标：
第三阶段面试的开始时间+第三阶段面试的时间T=Max{
xij
+tij}〔j=3〕，求出T的最小值即是我们最终想要优化的目标。
约束条件：
1）
时间先后次序约束，即是说每个人只有参加完前一个阶段的面试后才能进入下一个阶段；
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求解：
代码如下：
model:
min=T;
x41+8 x42+10 x31+20 x32+16 x21+10 x22+20 x11+13 x12+15 T>x43+15; T>x33+10; T>x23+18; T>x13+20; x31+20-x41 x32+16-x42 x33+10-x43 x21+10-x31 x22+20-x32 x23+18-x33 x21+10-x41 x22+20-x42 x23+18-x43 x11+13-x21 x12+15-x22 x13+20-x23 x11+13-x31 x12+15-x32 x13+20-x33 x11+13-x41 x12+15-x42 x13+20-x43 x41+8-x31 x42+10-x32 x43+15-x33 x41+8-x21 x42+10-x22 x43+15-x23 x31+20-x21 x32+16-x22 x33+10-x23 x21+10-x11 x22+20-x12 x23+18-x13 x31+20-x11 x32+16-x12 x33+10-x13 x41+8-x11 x42+10-x12 x43+15-x13 @bin(y34);@bin(y12);@bin(y13);@bin(y14); @bin(y23);@bin(y24); end 得到： Local optimal solution found at iteration: 3104 Objective value: 84.00000 Variable Value Reduced Cost T 84.00000 0.000000 X41 0.000000 0.9999970 X42 9.500000 0.000000 X43 21.00000 0.000000 X31 32.50000 0.000000 X32 58.00000 0.000000 X33 74.00000 0.000000 X21 22.50000 0.000000 X22 36.00000 0.000000 X23 56.00000 0.000000 X11 8.000000 0.000000 X12 21.00000 0.000000 X13 36.00000 0.000000 Y34 1.000000 0.000000 Y23 0.000000 -83.99950 Y24 1.000000 0.000000 Y12 0.000000 -83.99950 Y13 0.000000 0.000000 Y14 1.000000 83.99950 Row Slack or Surplus Dual Price 84.00000 -1.000000 1.500000 0.000000 1.500000 0.000000 5.500000 0.000000 0.000000 0.000000 3.500000 0.000000 0.000000 0.9999970 0.000000 0.9999970 0.000000 0.000000 48.00000 0.000000 0.000000 -0.9999970 10.00000 0.000000 28.00000 0.000000 31.50000 0.000000 19.50000 0.000000 21.00000 0.000000 0.000000 0.000000 2.000000 0.000000 0.000000 0.9999970 51.50000 0.000000 37.50000 0.000000 31.00000 0.000000 1.500000 0.000000 0.000000 0.9999970 0.000000 0.000000 11.50000 0.000000 22.00000 0.000000 18.00000 0.000000 63.00000 0.000000 57.50000 0.000000 49.00000 0.000000 24.50000 0.000000 38.50000 0.000000 38.00000 0.000000 14.50000 0.000000 16.50000 0.000000 20.00000 0.000000 54.00000 0.000000 46.00000 0.000000 56.00000 0.000000 59.50000 0.000000 49.00000 0.000000 46.00000 0.000000 39.50000 0.000000 31.00000 0.000000 36.00000 0.000000 0.000000 0.9999970 1.500000 0.000000 0.000000 0.000000 即所有面试完成需要84分钟，最正确面试顺序安排为丁-甲-乙-丙。 数学与计算机科学学院 周芸聪
点击咨询