多阶段面试排队决策模型

目 录

摘要................................................................ 3 一、问题重述........................................................ 4 二、问题分析........................................................ 4 三、模型假设........................................................ 4 四、符号说明........................................................ 5 五、模型建立........................................................ 5 六、模型求解........................................................ 6 七、模型评价........................................................ 7 八、模型推广........................................................ 7 参考文献............................................................ 7 附录................................................................ 8

多阶段面试排队决策模型

摘要

本文建立了多阶段面试排队决策的优化模型，研究在不同阶段怎样安排同学参加面试才能使得所花费的总时间最少（即本文中的最早何时能离开公司）问题。首先，本文的问题概述如下：有4名同学到一家公司参加三个阶段的面试：公司要求每个同学都必须首先找公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且不允许插队（即在任何一个阶段4名同学的顺序是一样的）。 已知每个同学在各个阶段面试所需时间（详见附2表一）。

各同学约定他们全部面试完以后一起离开公司。假定现在时间是早晨8:00，问他们最早何时能离开公司。本问题是一个排列排序问题。对于阶段数不小于3的问题没有有效算法，也就是说对于学生数稍多一点儿（比如20）的情况是无法精确求解的，为此人们找到了很多近似算法。

然而，针对这一问题，本文建立了一个全部同学面试完时间最短的规划模型，可以实现该问题的精确求解，但它的变量和约束是学生数的平方。而在建立此模型的过程中，本文一开始将目标函数建立成一个线性规划模型，即求所有同学排序情况下，被排在最后的一个同学面试完时所用总时间T（也即排序后，从第一个同学参加第一阶段面试时开始计时，到最后一个同学面试完最后一阶段的这段时间）中最小的一个。然后，又建立了一个0—1变量表示其约束条件。 对该模型的求解，本文用LINGO的集合程序求解(程序及运行结果见附录).得到的结果分析可得，所有面试完成至少需要84分钟，同时也得出面试的顺序为4-1-2-3（即丁-甲-乙-丙）.该模型具有简便、易懂，又有比较好的实用性和技巧性，因为它用几个简单的约束条件将所有情况都考虑在内了。

关键词：多阶段面试，排队问题，0-1线性规划

1

一、问题重述

在对同学进行排序时，人们常常就会想到底怎样将这四名同学排序，才能够使得四名同学全部面试完所用的时间最短。为了能够做到这一点，我们在排序之前必须对各种影响面试总时间的因素约束条件和题目中的一些要求进行分析。 由于4名同学的专业背景不同，所以要去了解这四名同学的一些相关信息，并得到如下表所示的每一个同学在每一个阶段面试所需时间：

同学甲 同学乙 同学丙 同学丁 秘书初试 13 10 20 8 主管复试 15 20 16 10 经理面试 20 18 10 15 而且公司要求每个同学都必须首先找公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且不允许插队（即在任何一个阶段4名同学的顺序是一样的）。 本题需要我们设计一种排序方案，使得四位同学面试的总时间最短，这样他们才能最早地离开公司。

二、问题分析

这是一个优化问题，要决策的是将甲乙丙丁进行排序，即所谓的排列排序，要达到的目标只有一个，就是要使得四名同学面试后能最早离开公司，也就是他们面试的总时间最少。但是将四名同学进行排序时，得到的排序结果蛮多，所以我们要找到一个合适和简便的方法来求解每一种情况下，面试时间最短的那种排序。 建立优化问题的模型最主要的是用数学符号和式子表述决策变量、构造目标函数和确定约束条件。对于本题决策变量是明确的，即第i个同学开始面试第三个阶段时的时刻xi3 ，及第i个同学面试第三个阶段所用时间ti3 。目标函数为所有同学排序情况下，被排在最后的一个同学面试完时所用总时间T（也即排序后，从第一个同学参加第一阶段面试时开始计时，到最后一个同学面试完最后一阶段的这段时间）中最小的一个，即Min TMax{xi3+ti3}。约束条件为每个同学都必须首先找公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且不允许插队（即在任何一个阶段4名同学的顺序是一样的），及由于4名同学的专业背景不同，使得每人在三个阶段的面试时间也不同。

三、模型假设

2

1、面试时间是连续的，即在面试期间中间没有休息，也没有因为其他原因而使得面试时间有间断；

2、每个同学在三个阶段面试的时间是确定不变的，就如表格中所给的； 3、从0时刻开始面试； 4、各个面试地点尽可能的接近（即人们从一个面试地点到另外一个面试地点的步行时间忽略）；

5、每个同学被排序后的结果是等可能发生的；

四、符号说明及名词定义

xij：第i名同学参加第j阶段面试的开始时刻（记从0时刻开始面试）; tij：第i名同学参加第j阶段面试需要的时间;

yik：第k名同学是否排在i名同学前面（1表示是，0表示否）； T ； 四个同学面试完后所用的总时间；

五、模型建立

（一）对于问题的0-1线性规划模型

记tij为第i名同学参加第j阶段面试需要的时间，令xij表示第i名同学参加第j阶段面试的开始时刻（记从0时刻开始面试）（i=1,2,3,4;j=1,2,3）. 优化目标为Min TMax{xi3+ti3}. 约束条件：

1）面试阶段次序约束（每人参加完前一个阶段才能继续参加下一个阶段） xij+tij ≤xi,j+1 (i=1,2,3,4;j=1,2) 2)每个阶段j在同一时间只能面试一名同学：用0-1变量yik表示第k名同学是否排在i名同学前面（1表示是，0表示否），则 当yik=0时，k同学在i同学后面，有

xij+tij-xkj ≤0 (i,k=1,2,3,4;j=1,2,3;i＜k) xkj+tkj-xij ≤T (i,k=1,2,3,4;j=1,2,3;i＜k) 当yik=1时，i同学在k同学后面，有

xij+tij-xkj ≤T (i,k=1,2,3,4;j=1,2,3;i＜k) xkj+tkj-xij ≤0 (i,k=1,2,3,4;j=1,2,3;i＜k) 故综合上述得

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) （二）对于问题的0-1线性规划模型进行改善 将目标函数改写为： Min T

满足面试完同时离开这一约束,则 T≥x13+t13 T≥x23+t23 T≥x33+t33 T≥x43+t43

3

加上约束条件1）、2）有 目标函数：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-xkj ≤T(1-yik) (i,k=1,2,3,4;j=1,2,3;i＜k) T≥x13+t13 T≥x23+t23 T≥x33+t33 T≥x43+t43

六、模型求解

根据模型，用LINGO软件编程求解(详细的程序说明及运行结果见附录)并对结果进行分析得各同学在各个阶段的面试情况。 甲, 阶段一 甲, 阶段二 甲, 阶段三 乙, 阶段一 乙, 阶段二 乙, 阶段三 丙, 阶段一 丙, 阶段二 丙, 阶段三 丁, 阶段一 丁, 阶段二 丁, 阶段三 各阶段开始时刻 各阶段所需时间 各阶段结束时时刻 8 13 21 21 15 36 36 20 56 26 10 36 36 20 56 56 18 74 36 20 56 56 16 72 74 10 84 0 8 8 8 10 18 21 15 36 由已知数据，进行图形描绘得：

4

百度搜索“70edu”或“70教育网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，70教育网，提供经典教育范文多阶段面试排队决策模型在线全文阅读。