面试时间优化安排

面试时间优化安排一：提出问题：问题是这样产生的：有4名同学到一家公司参加三个阶段的面试，公司要求每个同学都必须首先找公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且不允许插队（即：在任何一个阶段4名同学的顺序是一样的），由于4名同学的专业背景不同，所以每人在三个阶段的面试时间也不同，如下表所示：（单位：分钟）秘书初试主管复试经理面试同学甲131520同学乙102018同学丙201610同学丁81015这四名同学约定他们全部面试完成以后一起离开公司，假定现在时间食早晨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)于是我们的目标函数为：MinT；T=Max{xij+tij}；连同约束条件，输入LINGO求解：代码如下：model:min=T;x41+8x42;x42+10x43;x31+20x32;x32+16x33;x21+10x22;x22+20x23;x11+13x12;x12+15x13;Tx43+15;Tx33+10;Tx23+18;Tx13+20;x31+20-x41T*y34;x32+16-x42T*y34;x33+10-x43T*y34;x21+10-x31T*y23;x22+20-x32T*y23;x23+18-x33T*y23;x21+10-x41T*y24;x22+20-x42T*y24;x23+18-x43T*y24;x11+13-x21T*y12;x12+15-x22T*y12;x13+20-x23T*y12;x11+13-x31T*y13;x12+15-x32T*y13;x13+20-x33T*y13;x11+13-x41T*y14;x12+15-x42T*y14;x13+20-x43T*y14;x41+8-x31T*(1-y34);x42+10-x32T*(1-y34);x43+15-x33T*(1-y34);x41+8-x21T*(1-y24);x42+10-x22T*(1-y24);x43+15-x23T*(1-y24);x31+20-x21T*(1-y23);x32+16-x22T*(1-y23);x33+10-x23T*(1-y23);x21+10-x11T*(1-y12);x22+20-x12T*(1-y12);x23+18-x13T*(1-y12);x31+20-x11T*(1-y13);x32+16-x12T*(1-y13);x33+10-x13T*(1-y13);x41+8-x11T*(1-y14);x42+10-x12T*(1-y14);x43+15-x13T*(1-y14);@bin(y34);@bin(y12);@bin(y13);@bin(y14);@bin(y23);@bin(y24);end得到：Localoptimalsolutionfoundatiteration:3104Objectivevalue:84.00000VariableValueReducedCostT84.000000.000000X410.0000000.9999970X429.5000000.000000X4321.000000.000000X3132.500000.000000X3258.000000.000000X3374.000000.000000X2122.500000.000000X2236.000000.000000X2356.000000.000000X118.0000000.000000X1221.000000.000000X1336.000000.000000Y341.0000000.000000Y230.000000-83.99950Y241.0000000.000000Y120.000000-83.99950Y130.0000000.000000Y141.00000083.99950RowSlackorSurplusDualPrice184.00000-1.00000021.5000000.00000031.5000000.00000045.5000000.00000050.0000000.00000063.5000000.00000070.0000000.999997080.0000000.999997090.0000000.0000001048.000000.000000110.000000-0.99999701210.000000.0000001328.000000.0000001431.500000.0000001519.500000.0000001621.000000.000000170.0000000.000000182.0000000.000000190.0000000.99999702051.500000.0000002137.500000.0000002231.000000.000000231.5000000.000000240.0000000.9999970250.0000000.0000002611.500000.0000002722.000000.0000002818.000000.0000002963.000000.0000003057.500000.0000003149.000000.0000003224.500000.0000003338.500000.0000003438.000000.0000003514.500000.0000003616.500000.0000003720.000000.0000003854.000000.0000003946.000000.0000004056.000000.0000004159.500000.0000004249.000000.0000004346.000000.0000004439.500000.0000004531.000000.0000004636.000000.000000470.0000000.9999970481.5000000.000000490.0000000.000000即所有面试完成需要84分钟，最佳面试顺序安排为丁-甲-乙-丙。数学与计算机科学学院周芸聪