, 黄敏1, 靳萌萌31. 东北大学 信息科学与工程学院, 辽宁 沈阳 110819;
2. 东北大学秦皇岛分校 管理学院, 河北 秦皇岛 066004;
3. 武汉大学 信息管理学院, 湖北 武汉 430000
收稿日期：2017-02-15
基金项目：国家杰出青年基金资助项目(71325002)；国家自然科学基金资助项目(71401027, 61402088, 71701037)；河北省自然科学基金资助项目(G2016501086, F2017501041)；河北省高等学校科学技术研究重点项目(ZD2016202)；中央高校基本科研业务费专项资金资助项目(N172304016)；国家自然科学基金重点国际合作研究项目(71620107003)。
作者简介：卢福强(1980-)，男，辽宁阜新人，东北大学副教授;
黄敏(1968-)，女，福建长乐人，东北大学教授，博士生导师。
摘要：随着近年来IT服务外包的迅猛发展, 对于项目的进度风险控制也成为了亟待解决的问题之一.针对IT服务外包项目进度风险控制问题, 建立了两层的数学模型.考虑到该优化问题是一个NP难问题且具有层次结构, 设计了改进的禁忌搜索算法进行求解.主要改进包括初始解的启发式方法产生, 禁忌表动态构造等方面.在仿真实验的基础上, 对算法稳定性、算法收敛性和有效性等进行了分析, 并与传统禁忌搜索算法的仿真结果进行比较, 验证所设计算法的有效性.
关键词：禁忌搜索IT服务外包进度风险风险管理
Extended Tabu Search Algorithm for Schedule Risk Control of IT Outsourcing Project
LU Fu-qiang1,2, BI Hua-ling1,2
, HUANG Min1, JIN Meng-meng31. School of Information Science & Engineering, Northeastern University, Shenyang 110819, China;
2. Academy of Management, Northeastern University at Qinhuangdao, Qinhuangdao 066004, China;
3. School of Information Management, Wuhan University, Wuhan 430000, China
Corresponding author: BI Hua-ling, E-mail: bihualing@neuq.edu.cn
Abstract: With the rapid development of IT outsourcing projects in recent years, the schedule risk control has also become one of the urgent issues to be solved. Based on the optimization problems of schedule risk control in IT outsourcing projects, a two-level mathematical model was built. For the NP hard and hierarchical structure of the optimization problem, the basic tabu search algorithm was improved in generating initial solution with heuristic methods and constructing dynamic tabu list. According to the result of simulation experiment, the improved algorithm was analyzed in reliability, convergence and effectiveness. In addition, the simulation results were also compared with traditional tabu search algorithm, and the value of the improved tabu search is verified.
Key Words: tabu searchIT outsourcing projectschedule riskrisk management
随着IT技术和管理思想的不断成熟和发展, IT外包的概念逐渐在企业的视野占据一席之地.尽管IT外包具有诸多优点, 但风险和收益并存, 使得IT外包居高不下的失败率成为了该领域一直以来亟待解决的问题[1].软件项目拖期是业界的一个普遍现象, 进度延期可能直接导致项目质量下降、费用超支甚至失败, 因此项目执行过程中对于进度的风险控制至关重要.
近年来, 关于项目进度风险的相关研究逐渐增多.已有学者[2-4]设计了多种群粒子群算法求解考虑软件外包特性的进度风险控制问题, 构建了基于进度的软件项目风险优化控制决策模型, 提出开发者收益最大化的思路.
本文针对IT外包项目进度风险管理的分布式决策特点建立了两层的数学模型, 两层的结构导致问题比较复杂.传统的禁忌搜索算法难以求解[5], 于是, 设计了改进的禁忌搜索算法, 主要包括初始解的启发式方法产生, 禁忌表动态构造等方面.在仿真实验中, 从算法稳定性、算法效率以及各参数对算法性能的影响等方面进行了算法的性能分析, 表明了改进的禁忌搜索算法的有效性和稳定性.
1 IT服务外包进度风险控制问题IT服务外包项目的风险控制问题由两层分布式决策模型[6]描述, 上层和下层分别描述了委托方和承包商的决策过程.
上层模型:
 | (1) |
 | (2) |
 | (3) |
 | (4) |
在下层模型中, 各活动间的紧前关系用网络计划图来表示, 节点表示活动, 每条有向弧表示两个活动间的优先权, 项目工期可根据关键路径上活动的实际执行时间之和得到.下层决策者为承包商i, 承包商i在其分配到的资金下选择最优的资金分配方案yij使其工期最小.
下层模型:
 | (5) |
 | (6) |
 | (7) |
 | (8) |
 | (9) |
 | (10) |
 | (11) |
2 改进禁忌搜索算法禁忌搜索(TS)是一种元启发式优化算法[5].当本优化问题中承包商数量和关键路径上活动数量较大时, 该问题搜索空间的规模将迅速增大, 并带来两个问题:①在大规模的搜索空间中随机产生初始解, 易导致初始解的质量低, 从而大大降低算法的寻优[7-8], 根据问题中约束的特点设计启发式方法来产生初始解, 以期提高算法的效率和可靠性；②由于问题中不同承包商负责项目的活动数量是不同的, 若采用定长的禁忌表, 则只能以最大数量作为禁忌表的长度.当时活动的数量小于最大数量时, 就带来禁忌表长度过长的问题, 导致搜索的效率和速度降低.根据不同子项目中活动数量的变化, 设计了动态禁忌表, 以期提高算法的寻优效率.
2.1 适应值函数分别将上层模型和下层模型的目标函数作为相应的适应值函数.
2.2 启发式方法生成初始解为了提高算法的效率, 采用启发式方法来寻找一个可行解作为初始解[7].观察模型可以得知, 下层模型中的约束(7)属于较复杂的约束, [tijL, tijU]表示活动j执行时间范围, 而活动j的实际执行时间tij(yij)是一个关于资金yij的单调减函数, 所以可以从执行时间范围的上限tijU出发, 利用tij(yij)与yij的关系找出预测的资金下限, 该下限比较接近于实际资金下限.从该预测资金下限向上的邻域内随机寻找可行解.若一定次数内找不到, 则扩大邻域范围继续寻找, 直到找到一个可行解作为初始解.
2.3 移动与邻域下层解的编码, {y1, y2, …, yNi}中每个变量均采用10位长的二进制数表示, 长度为10Ni.在下层中, 对串联的10Ni位长的二进制解采用2-opt[9]的移动方式产生邻域解, 邻域规模为50Ni2－5Ni.当Ni较大时, 问题规模较大.为了提高算法的执行效率, 考虑随机抽取一部分的邻域作为(50Ni2－5Ni)S候选解集, S为邻域的抽取比例.
2.4 动态禁忌表禁忌表的大小在很大程度上影响搜索速度和解的质量[8], 因此, 将产生邻域的2-opt操作时的移动作为禁忌对象, 构造了动态禁忌表, 使算法具有更好的搜索性能.禁忌表长度[7]与问题规模的关系表示为
2.5 渴望水平渴望水平采用基于适应值的准则[8].如果某个候选解的适应值优于历史最优值, 那么无论这个候选解是否在禁忌表中, 都会被选择接受作为新的当前解.
2.6 停止准则同时采用两种停止准则[8-9]:①给定最大迭代步数NG作为停止准则; ②设定某对象的最大禁忌频率, 当目标历史最优值连续10次迭代得不到改善, 则算法停止.
2.7 算法流程改进禁忌搜索算法流程图如图 1所示.
图 1(Fig. 1)
 | 图 1 改进禁忌搜索算法的流程Fig.1 Procedures of extended tabu search |
3 仿真实验3.1 算例设计通过两个算例对IT外包项目进度风险控制模型的改进禁忌搜索算法进行仿真实验, 来验证模型与算法的合理性和有效性.
3.1.1 算例一IT外包项目中只有1个子项目, 承包给1个承包商, m=1.该项目有7个活动, Ni=7, 项目的网络计划图, 如图 2所示.每一个活动的执行时间与风险控制资金投入之间的关系, 由单调减函数表示为
 | (12) |
 | 图 2 算例一的网络计划图Fig.2 Network plan for example 1 |
这里i=1, j=1, 2, …, 7.μij的不同取值表示相同风险控制投入对于不同活动的风险控制效果的区别.委托方为IT外包项目的进度风险进行管理资金投入为1000, Bmax=1000.承包商的最大拖期水平为5%, r=0.05.各活动未进行风险控制时的执行时间tij、委托方需要的执行时间范围[tijL, tijU], μij的不同取值见表 1.
表 1(Table 1)
 表 1 参数的取值Table 1 Value of parameters
| 表 1 参数的取值 Table 1 Value of parameters |
在风险控制资金的作用下, 各活动的工期会相应的缩减, 随着风险控制资金的增加, 活动的工期缩减量也随之增大.
3.1.2 算例二算例二中有1个委托方和5个承包商, m=5.每个承包商负责一个子项目, 且各子项目之间是并行关系.各子项目中的活动数分别为:Ni={9 9 9 8 8}, μij的取值为:{0.001 0.0015 0.0015 0.0015 0.0015 0.0015 0.001 0.001 0.001}.各自项目的其他参数与例一中相同.
3.2 仿真结果以算例一为例, 对仿真结果进行说明.仿真结果列于表 2中, 进行进度风险控制之前项目的工期是50d, 控制之后的工期是44 d, 实际拖期水平为0.046, 达到了委托方对工期的要求, 有效地实现了按时完工并且所用资金最小化的目的, 成功地进行了进度风险的控制.算例一中算法参数设置为NG=100, S=0.05, V=10000.
表 2(Table 2)
表 2 算例一的仿真结果Table 2 Simulation results for example 1
| 表 2 算例一的仿真结果 Table 2 Simulation results for example 1 |
3.3 算法性能分析3.3.1 算法稳定性分析将下式作为算法稳定性评价标准:Stability=Xmin/
图 3(Fig. 3)
 | 图 3 算法的稳定性分析Fig.3 Reliability analysis |
3.3.2 算法收敛性分析图 4和图 5表示算例二中邻域长度控制变量S和禁忌长度控制变量V对迭代次数的影响.由图 4可知, 算例二各子项目的最大迭代次数分别为13，14，13，16，18次.
图 4(Fig. 4)
 | 图 4 邻域长度对各子项目迭代次数的影响Fig.4 Impact of neighbourhood size on iteration of subprojects |
图 5(Fig. 5)
 | 图 5 禁忌长度对子项目迭代次数的影响Fig.5 Impact of tabu table length on iteration of subprojects |
由图 5可知, 算例二各子项目的最大迭代次数各为14，16，15，16，19次, 综上所述, 可以将算例二的迭代次数设为14，16，15，16，19次, 以减少计算冗余.最大迭代次数不超过20, 说明算法的收敛速度快.
3.3.3 与传统禁忌搜索算法的比较采用传统禁忌搜索算法(TS)求解本问题.实验结果与改进的禁忌搜索算法(ETS)结果进行比较.由表 3可以看出, ETS在寻优能力、稳定性和运行时间上较TS都有较明显优势.
表 3(Table 3)
表 3 两种算法结果的比较Table 3 Compare of the two algorithms
| 表 3 两种算法结果的比较 Table 3 Compare of the two algorithms |
4 结语本文针对IT服务外包项目进度风险控制问题, 设计了改进的禁忌搜索算法.使用启发式方法产生初始解, 构造了动态禁忌表和邻域表.通过二个算例对问题进行仿真实验, 实验结果表明所设计的风险控制模型和改进的禁忌搜索算法, 对于定量化的描述此类决策问题并求解是有效的, 起到了为IT外包进度风险控制提供辅助决策的作用.
参考文献
| [1] | Lacity M C, Khan S A, Willcocks L P. A review of the IT outsourcing literature:insights for practice[J].Journal of Strategic Information Systems, 2009, 18(3): 130–146.DOI:10.1016/j.jsis.2009.06.002 |
| [2] | 曹萍, 陈福集, 张剑. 基于进度的软件外包项目风险优化控制决策[J].武汉大学学报(工学版), 2012, 45(3): 385–388. ( Cao Ping, Chen Fu-ji, Zhang Jian. Risk optimization control decision-making of software outsourcing project based on schedule[J].Journal of Wuhan University(Engineering Science Edition), 2012, 45(3): 385–388.) |
| [3] | Fan Z P, Suo W L, Feng B, et al. Identifying risk factors of IT outsourcing using interdependent information:an extended DEMATEL method[J].Expert Systems with Applications, 2012, 39(3): 3832–3840.DOI:10.1016/j.eswa.2011.09.092 |
| [4] | Huang K. Research on risk early-warning of information technology outsourcing project based on neural network[J].Applied Mechanics and Materials, 2013, 411: 2400–2405. |
| [5] | Abyazi-Sani R, Ghanbari R. An efficient tabu search for solving the uncapacitated single allocation hub location problem[J].Computers & Industrial Engineering, 2016, 93: 99–109. |
| [6] | Christoph S. Distributed decision making[M]. Berlin: Springer-Verlag, 2003: 125-156. |
| [7] | Xhafa F, Sánchez C, Barolli A, et al. Solving mesh router nodes placement problem in wireless mesh networks by tabu search algorithm[J].Journal of Computer and System Sciences, 2015, 81(8): 1417–1428.DOI:10.1016/j.jcss.2014.12.018 |
| [8] | Li X, Gao L. An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem[J].International Journal of Production Economics, 2016, 174: 93–110.DOI:10.1016/j.ijpe.2016.01.016 |
| [9] | Zeng Z, Yu X, He K, et al. Iterated tabu search and variable neighborhood descent for packing unequal circles into a circular container[J].European Journal of Operational Research, 2016, 250(2): 615–627.DOI:10.1016/j.ejor.2015.09.001 |
