面试顺序与消防车调度问题

《面试顺序与消防车调度问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、5.4面试顺序与消防车调度问题面试顺序问题例5.5有4名同学到一家公司参加三个阶段的面试：公司要求每个同学都必须首先找公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且不允许插队（即在任何一个阶段4名同学的顺序是一样的）。由于4名同学的专业背景不同，所以每人在三个阶段的面试时间也不同，如表5-5所示（单位：分钟）。这4名同学约定他们全部面试完以后一起离开公司。假定现在时间是早晨8：00，请问他们最早何时能离开公司？表5-5面试时间要求秘书初试主管复试经理面试同学甲131520同学乙102018同学丙201010同学丁810

2、15建立模型实际上，这个问题就是要安排4名同学的面试顺序，使完成全部面试所花费的时间最少。记tij为第i名同学参加第j阶段面试需要的时间(已知)，令xij表示第i名同学参加第j阶段面试的开始时刻(不妨记早上8：00面试开始为0时刻)(i=1,2,3,4；j=1,2,3)，T为完成全部面试所花费的最少时间。优化目标为a.时间先后次序约束(每人只有参加完前一个阶段的面试后才能进入下一个阶段)：xij+tijxi，j+1(i=1,2,3,4；j=1,2)b.每个阶段j同一时间只能面试1名同学：用0-1变量yik表示第k名同学是否排在第i名

3、同学前面(1表示是，0表示否)，则xij+tij–xkjTyik(i,k=1,2,3,4;j=1,2,3;i

4、–yik)(i,k=1,2,3,4;j=1,2,3;i=x13+t13;T>=x23+t23;T>=x33+t33;T>=x43+t43;x11+t11<=x12;x12+t12<=x13;x21+t21<=x22;x22+t22<=x23;x31+t31<=x32;x32+t32<=x33;x41+t41<=x42;x42+t42<=x43;求解模型这个模型可以如下输入LIN

5、GO：x11+t11-x21<=T*y12;x21+t21-x11<=T*(1-y12);x12+t12-x22<=T*y12;x22+t22-x12<=T*(1-y12);x13+t13-x23<=T*y12;x23+t23-x13<=T*(1-y12);x11+t11-x31<=T*y13;x31+t31-x11<=T*(1-y13);x12+t12-x32<=T*y12;x32+t32-x12<=T*(1-y13);x13+t13-x33<=T*y13;x33+t33-x13<=T*(1-y13);x11+t11-x41<=T*

6、y14;x41+t41-x11<=T*(1-y14);x12+t12-x42<=T*y14;x42+t42-x12<=T*(1-y14);x13+t13-x43<=T*y14;x43+t43-x13<=T*(1-y14);x21+t21-x31<=T*y23;x31+t31-x21<=T*(1-y23);x22+t22-x32<=T*y23;x32+t32-x32<=T*(1-y23);x23+t23-x33<=T*y23;x33+t33-x23<=T*(1-y23);x21+t21-x41<=T*y24;x41+t41-x21<=T

7、*(1-y24);x22+t22-x42<=T*y24;x42+t42-x22<=T*(1-y24);x23+t23-x43<=T*y24;x43+t43-x23<=T*(1-y24);x31+t31-x41<=T*y34;x41+t41-x31<=T*(1-y34);x32+t32-x42<=T*y34;x42+t42-x32<=T*(1-y34);x33+t33-x43<=T*y34;x43+t43-x33<=T*(1-y34);t11=13;t12=15;t13=20;t21=10;t22=20;t23=18;t31=20;t3

8、2=16;t33=10;t41=8;t42=10;t43=15;@bin(y12);@bin(y13);@bin(y14);@bin(y23);@bin(y24);@bin(y34);End用LINGO求解得到：Loca