面试顺序消防车调度问题.ppt

面试顺序与消防车调度问题
面试顺序问题
有4名同学到一家公司参加三个阶段的面试:公司要求每个同学都必须首先找公司秘书初试,然后到部门主管处复试,最后到经理处参加面试,并且不允许插队(即在任何一个阶段4名同学的顺序是一样的)。由于4名同学的专业背景不同,所以每人在三个阶段的面试时间也不同,如表5-5所示(单位:分钟)。这4名同学约定他们全部面试完以后一起离开公司。假定现在时间是早晨8:00,请问他们最早何时能离开公司?
表5-5 面试时间要求
秘书初试
主管复试
经理面试
同学甲
13
15
20
同学乙
10
20
18
同学丙
20
10
10
同学丁
8
10
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)
:用0-1变量yik表示第k名同学是否排在第i名同学前面(1表示是,0表示否),则
xij+ tij–xkjTyik (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  x13+ t13
T  x23+ t23
T  x33+ t33
T  x43+ t43
Min T
. xij+ tij xi, j+1 (i=1, 2, 3, 4;j=1, 2)
xij+ tij–xkjTyik (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)
xi3+ ti3T (i=1, 2, 3, 4)
这个问题的0-1非线性规划模型(当然所有变量还有非负约束,变量yik还有0-1约束) :
Model:
min =T;
T >= 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;
求解模型
这个模型可以如下输入LINGO:
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*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*(1-y24);