多阶段面试排队决策模型

《多阶段面试排队决策模型》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、摘要3一、问题重述4二、问题分析4三、模型假设4四、符号说明5五、模型建立5六、模型求解6七、模型评价7八、模型推广7参考文献7附录8多阶段面试排队决策模型摘要本文建立了多阶段面试排队决策的优化模型，研究在不同阶段怎样安排同学参加面试才能使得所花费的总时间最少（即木文中的最早何时能离开公司）问题。首先，本文的问题概述如下：有4名同学到一家公司参加三个阶段的面试：公司要求每个同学都必须首先找公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且不允许插队（即在任何一个阶段4名同学的顺序是一样的）。已知每个同学在各个阶段面试所

2、需时间（详见附2表一）。各同学约定他们全部面试完以后一起离开公司。假定现在时间是早晨8:00,问他们最早何时能离开公司。本问题是一个排列排序问题。对于阶段数不小于3的问题没有有效算法，也就是说对于学生数稍多一点儿（比如20）的情况是无法精确求解的,为此人们找到了很多近似算法。然而，针对这一问题，本文建立了一个全部同学面试完时间最短的规划模型，可以实现该问题的精确求解，但它的变量和约朿是学生数的平方。而在建立此模型的过程中，本文一开始将目标函数建立成一个线性规划模型，即求所有同学排序情况下，被排在最后的一个同学而试完时所用总时间T（

3、也即排序后，从第一个同学参加第一阶段面试时开始计时，到最后-•个同学面试完最后一阶段的这段时间）'P最小的-•个。然后，又建立了-•个0—1变量表示其约束条件。对该模型的求解，本文用LINGO的集合程序求解（程序及运行结果见附录）.得到的结果分析可得，所有面试完成至少需要84分钟，同时也得出面试的顺序为4-1-2-3（即丁-甲-乙-丙）•该模型具有简便、易懂，乂有比较好的实用性和技巧性，因为它用儿个简单的约束条件将所有情况都考虑在内了。关键词：多阶段而试，排队问题，0-1线性规划一、问题重述在对同学进行排序时，人们常常就会想到底怎

4、样将这四名同学排序，才能够使得四名同学全部面试完所用的时间最短。为了能够做到这一点，我们在排序之前必须对各种影响面试总时间的因素约束条件和题口屮的一些要求进行分析。由于4名同学的专业背景不同，所以要去了解这四名同学的一些相关信息，并得到如下表所示的每一个同学在每一个阶段面试所需时间：秘书初试主管复试经理面试同学甲131520同学乙102018同学丙201610同学丁81015而且公司要求每个同学都必须首先找公司秘书初试，然后到部门主管处复试，最后到经理处参加而试，并且不允许插队（即在任何一个阶段4名同学的顺序是一样的）。木题需要我

5、们设计种排序方案，使得四位同学面试的总时间最短，这样他们才能最早地离开公司。二、问题分析这是一个优化问题，要决策的是将甲乙内丁进行排序，即所谓的排列排序，要达到的目标只有一个，就是要使得四名同学面试后能最早离开公司，也就是他们面试的总时间最少。但是将四名同学进行排序时，得到的排序结杲蛮多，所以我们耍找到一个合适和简便的方法来求解每一种情况下，面试时间最短的那种排序。建立优化问题的模型最主要的是用数学符号和式子表述决策变量、构造目标两数和确定约朿条件。对于木题决策变量是明确的，即第i个同学开始面试第三个阶段时的时刻x13,及第i个同

6、学面试第三个阶段所用时间ti3o口标函数为所有同学排序情况下，被排在最后的一个同学面试完时所用总时间T（也即排序后，从第一个同学参加第一阶段而试时开始计时，到最后一个同学而试完最后一阶段的这段时间）中最小的一个，即MinTMax{xi3+ti3}o约朿条件为每个同学都必须首先找公司秘书初试，然后到部门主管处复试，最后到经理处参加而试，并且不允许插队（即在任何一个阶段4名同学的顺序是一样的），及由于4名同学的专业背景不同，使得每人在三个阶段的面试时间也不同。三、模型假设1、血试时间是连续的，即在面试期间中间没有休息，也没有因为其他原

7、因而使得面试时间有间断；2、每个同学在三个阶段面试的时间是确定不变的，就如表格中所给的；3、从0时刻开始面试；4、各个面试地点尽可能的接近（即人们从一个面试地点到另外一个面试地点的步行时间忽略）:5、每个同学被排序后的结果是等可能发生的；四、符号说明及名词定义x“第i名同学参加第j阶段面试的开始时刻（记从0时刻开始面试）tij:第i名同学参加第j阶段面试需要的时间；yik：第k名同学是否排在i名同学前面（1表示是，0表示否）；T:四个同学面试完后所用的总时间；五、模型建立（-）对于问题的0-1线性规划模型记切为第i名同学参加第j阶

8、段面试需耍的时间，令X"表示第i名同学参加第j阶段面试的开始时刻（记从0时刻开始面试）（1=1,2,3,4;j=l,2,3）・优化目标为MinTMax{xi3+ti3}.约束条件：1）面试阶段次序约束（每人参加完前一个阶段才能继续参加下一个阶段）X