基于混合蛙跳算法的异地分布式协同开发的任务分配优化

周 聪，姜继娇*，殷 茗

基于混合蛙跳算法的异地分布式协同开发的任务分配优化

周 聪1，姜继娇1*，殷 茗2

（1.西北工业大学管理学院，陕西 西安 710072；2.西北工业大学软件与微电子学院，陕西 西安 710072）

异地分布式协同开发已经成为大型复杂产品开发策略的一部分，复杂产品在动态环境下，针对不同团队的技术水平、专业方向、所在的地理位置等外部条件进行实时任务分配这一问题，本文采用无约束化的编码方式并结合变异、交叉的遗传操作，建立基于混合蛙跳算法的异地分布式多团队开发环境中的任务分配模型。该模型，参考Scrum产品的开发框架对任务进行分解，以协同生产企业的敏捷性与其地理位置为优化目标，实现在异地分布式环境中的任务智能分配。通过模拟我国某飞机发动机任务分配的过程，验证算法的性能。结果表明，与原始的混合蛙跳算法相比，本文所提的改进混合蛙跳算法具有较好的全局搜索能力与求解的精度。

复杂产品；异地分布式协同开发；混合蛙跳算法；敏捷性

0 引言

目前，异地分布式协同开发(Geographically Distributed Collaborative Development，GDCD)已经成为大型复杂产品开发策略的主流趋势[1]。大型复杂产品的客户需求、产品组成、产品设计、产品制造及项目管理复杂，涉及机械、控制、电子、液压、气动和软件等多学科领域，每个子系统都由多学科领域的零部件组成，与外界存在复杂的交互关系。GDCD 可以帮助企业进行大型复杂产品开发时达到更好的灵活性及成本控制，现有研究主要集中于异地分布式团队之间的协作和沟通问题[2][3][4][5]。

异地分布式开发需要敏捷性[6]，以快速适应不稳定的市场环境与需求变动。大型复杂产品 GDCD 过程中需要充分利用分散企业的资源，进行产品开发过程，参与者复杂，信息交换内容广泛。人们建立敏捷开发团队往往是受到利益驱动，例如生产率提高、创新及员工满意等。随着产品复杂性和技术环境正以不可预测的速率进行变化，多个企业进行复杂航空产品异地分布式协同开发的敏捷性已经成为了提升产品开发绩效的关键。敏捷过程更加强调感官与反应、自组织、跨职能团队及持续适应力[7]，而且组织所具有的敏捷性可以快速适应这种迅速变化的外部环境[8]。但异地分布式敏捷开发相对于集中式开发会存在更多阻力[9]。现有研究主要集中在应用实践[10]、协作与沟通[11]、方法工具[12]、知识管理[13]、大规模项目[14]、团队[15]及风险[16]等方面。近年的研究表明，任务分配被认为是异地分布式开发过程中的关键环节。项目中不同的人员从事相同的任务，其生产效率差距可达 10-40 倍[17]。Lin 等[18]认为任务分配可减少异地团队间的沟通成本，使成员把精力投入到开发中。Paasivaara等[19]指出了 GDCD 团队进行的开发必然受制于团队之间的协同关系，异地分布式团队间高效的协同控制，直接影响到合作伙伴的核心能力的充分发挥及有效地实现优势互补，进而影响到项目的整体获益。任务分配问题的研究大部分主要集中在人工智能领域，例如多 Agent系统[20]、机器人[21]等。异地分布式开发环境下的任务分配是在不同地理、时区和文化的团队之间进行，团队相互之间并不熟悉，如何在动态环境下，根据不同团队的技术水平、专业方向、所在地理位置等内外部条件进行实时任务分配，这对大型复杂产品进行异地分布式敏捷协同开发具有重要意义。因此，异地分布式开发的任务分配，是本研究要考虑的重要问题，任务分配有助于合理优化开发资源。针对异地分布式开发的任务分配问题，现有学者已经展开了初步的研究。例如，Ruano-Mayoral 等[22]提出了一个全球开发项目任务包二阶段分配框架，提出了任务分配的决策影响因子，实施结果表明了任务规划的准确性、效果和满意度；Almeida等[23]提出了一个异地分布式开发认知映射和 MACBETH 的多维决策模型；Lamersdorf 和 Münch[24]提出了全球开发的一个客户化多维需求任务分配模型，运用了改进 Bokhari 算法，该模型在多个典型假设场景和实际分布决策问题获得了应用效果；张立等[25]提出了一种将心智模型与扩展合同网机制结合的半自治多 Agent 任务分配方法，并扩展了合同网机制包括发标优选、竞标报价与多 Agent 任务分配过程。上述研究在分配过程框架、客户化需求驱动、心智模型等方面提供了很好的研究借鉴，但是，当异地分布式环境采用敏捷开发，如何在异地分布式敏捷开发环境中进行任务分配优化，还没有进行深入研究。本文尝试构建基于混合蛙跳算法与遗传算法的综合算法，求解异地分布式协同开发过程中的任务分配问题。蛙跳算法已经在图形分割[26]、车辆路径[27]、旅行商问题[28]、资源分配[29]等问题中得到应用。

本文在异地分布式敏捷团队任务分配的特点，采用了基于实数的编码方式，用一种粒子代表子任务-协同生产企业的决策方案，满足问题的约束条件，并基于混合蛙跳算法与遗传算法的融合算法求解大型复杂产品开发异地分布式任务分配问题，构建混合蛙跳和遗传算法融合的团队内部的任务分配模型。该融合算法将全局寻优能力强的混合蛙跳算法与局部寻优能力强的遗传算法融合在一个算法框架中，取长补短，而该融合算法的优势是先利用混合蛙跳算法对离散问题的强大解决能力，建立团队间任务分配的初始全局最优解群，对混合蛙跳算法中青蛙例子编码进行定义并改进算法的局部搜索机制，然后利用遗传算法进行全局最优解群中的局部最优细化搜索，期望最终能达到异地分布式多团队敏捷开发任务精细化分配的结果。该综合算法具有很好的全局收敛能力与运算精度，进一步为实际中的任务分配提供参考。

1 混合蛙跳算法任务分配优化模型

1.1 模型总体思路

混合蛙跳算法中，每种任务分配方案对应一只青蛙，每只青蛙是由选取的协同生产企业的基因序列组成，寻找最佳青蛙就是搜索最优的任务分配方案的过程，每只青蛙的优劣都是由本文优化模型的适应度函数决定的，青蛙的适应度函数对应于任务分配优化问题的目标函数。

图1 异地分布式协同开发的任务分配优化模型

Figure 1 Task allocation optimization model of geographically distributed collaborative

1.1.1青蛙个体的表达

1.1.2优化过程

1.2 关键技术

1.2.1个体更新策略

本文的青蛙个体更新策略借鉴John Holland所提的遗传算法，其计算原理是在解域中，以目标函数为基础，不断向最优解靠近，是一种以一定概论为基础的全局寻优的过程。遗传算法过程中主要包括了以下三个算子：选择；交叉；变异。本文主要借鉴了遗传算法中的交叉与变异这两个算子。

（1）学习策略

图2 交叉操作

Figure 2 Crossover operation

（2）变异策略

图3 变异方式

Figure 3 Mutation methods

1.2.2适应度函数

（1）协同企业敏捷性度量方式

图4 敏捷指标

Figure 4 Agile metrics

其次，计算14个敏捷指标的优劣度权重，具体的算法步骤如下：

1）初步权重。采用层次分析法计算出每个专家对虚拟企业敏捷的14个指标的权重、灰色优度与灰色劣度，即为初步权重；

计算各个可供选择的协同生产企业敏捷性中的成本(C)、时间(T)、鲁棒性(R)、可适应范围(T)的具体步骤如下：

Step0 准备工作。计算各个打分专家的权重，以及每个指标的优劣度权重（14个）。

Step1 专家打分。组织本次虚拟企业敏捷性评价的专家，为其提供虚拟企业的资料，对专家进行访谈和填表，评分表采用百分制。

表1 专家咨询表

（2）协同生产企业与核心企业间距离的度量方式

L为协同企业距离核心企业的距离。由协同企业所处位置与核心企业之间的直线位置直接测量得出。

2 优化步骤

任务分配空间优化模型，把每种可能的任务分配想象为一只青蛙，通过计算机的高速迭代，寻找青蛙在解空间中的最优，得到任务分配的最优方案，优化步骤如下：

（1）任务分解

当项目或产品开发过程中涉及多个团队时，Scrum 可以帮助敏捷团队与其他团队的协调与合作。因此本文结合敏捷理论将一个产品任务可分解为若干个子任务，每个子任务按照相似的特征及其之间的关系进行开发。生产子任务的团队都要完成特定的子任务，而子任务也是一个完整带有独立专家和产品经理角色的产品。

首先，核心企业确定其生产子任务。对总任务进行分解，由核心企业根据该产品完整的设计以及工艺，先对产品项目进行初步的拆分，确定核心企业的生产部分。其次，确定协同企业生产任务。子任务的分解方式，借鉴SCRUM迭代式的增量软件开发过程，把任务分解成多个具有优先权重的子任务，每个子任务都是一个“用户故事”，完成整个任务就是多个子任务的迭加，Scrum迭代任务分解方式使子任务之间具有灵活性，核心企业在生产过程中可以随时根据客户需求、技术变更等外界变化，及时调整后续子任务的分解及分配方式，且在变更过程中对已完成的子任务不会造成返工等影响，减少变更过程中不影响整体任务的生产时间或效率。

（2）确定优化模型参数。

（3）种群初始化

在本次研究中，子任务的生产企业构成青蛙的基因，每只青蛙对应一种解。初始种群决定了优化搜索的起点与范围，在很大程度上影响着优化结果的质量，为了避免人为的干扰，初始青蛙由子任务随机分配选择生产商，以青蛙基因中每个可供选择的子任务的企业为基础，随机选取只青蛙作为初始解。

（4）排序分组及组内局部优化。

图5 组内优化过程

Figure 5 Intra-group optimization process

（5）全局优化。

（6）解析成图并进行结果分析。

蛙群在满足终止条件后，对青蛙的空间分布进行解析，并将优化后的数字信息还原为任务分配策略。该模型在多目标控制下把任务分配优化的数量结构进行了空间布局，符合任务分配优化的应用需要。

3 案例分析

为了验证本文所提任务分配方法的有效性，本文以课题小组参与的航空基金项目案例为基础，通过Matlab语言在 Intel Core i5 CPU 2.20GHz,内存32GB的PC机上进行实验。假设航空某厂生产4中不同型号的发动机，记为M1、M2、M3、M4,每个型号发动机的订单结构为图6。这4中型号的发动机按照SCRUM敏捷开发框架分解为8个子任务，其余由协同企业提供，

为了说明本文所提算法的有效性，同时与原混合蛙跳算法（SFLA）进行对比分析。

图6 M1、M2、M3、M4型号发动机的订单结构

Figure 6 Order structure for M1,M2,M3,M4 engines

表2 协同生产企业敏捷性得分

Table 2 Agility score of collaborative development enterprises

表3 协同生产企业与核心企业间的距离

表4 M1、M2、M3、M4型号任务参数

3.1 参数设定

表5 子任务对应可选生产企业

混合蛙跳算法以协同企业敏捷性与其所处地理位置为优化目标，利用Matlab（2014a）进行仿真实验，设定全局迭代次数为100次，局部迭代次数为5次，初始种群为50组，每组青蛙25，即初始种群规模为1250。

3.2 运算结果分析

此次研究同时考虑了协同企业的敏捷性与其所处的地理位置，建立多目标的任务分配优化模型，从模型的优化结果看，分别用改进后的混合蛙跳算法与原始混合蛙跳算法对此问题进行20次的独立求解。

本文所提到的改进混合蛙跳算法在问题求解的平均第29次，就出现了回归，平均最优值为0.12，具体如表6所示。改进后的混合蛙跳算法优化结果比混合蛙跳算法优化结果相对减少0.06。改进后的混合蛙跳算法平均进化到32代就已经达到了最优，而原混合蛙跳算法在38代才达到了最优，由此可见，改进后的混合蛙跳算法在求解问题时收敛速度更快，比SFLA相对提高了17%。其中一次的优化结果如图6所示。

图6所示实验结果的收敛曲线中，在算法迭代第32次时所得到的任务分配方案是型号为M1发动机的子任务对应的生产企业为[0,0,21,24],型号为M2发动机的子任务对应的生产企业为[0,8,22],型号为M3发动机的子任务对应的生产企业为[2,0,13,26],型号为M4发动机的子任务对应的生产企业为[0,8,24,0],此时在满足型号需求的约束下，各协同企业与核心企业的距离最短，企业敏捷性最小。

图7 改进后混合蛙跳算法与混合蛙跳算法最优值随迭代次数变化的对比

Figure 7 Comparison of the optimal value of the improved Shuffled Frog Leading Algorithm and Shuffled Frog Leading Algorithm with the number of iterations

表6 改进后混合蛙跳算法与原混合蛙跳算法迭代100次对比

4 结论与讨论

本文针对异地分布式协同开发的任务分配问题，提出了一种改进的混合蛙跳算法，通过以无约束的编码方式使其适应任务分配问题的求解，针对算法中局部搜索的能力，结合交叉、变异的遗传操作特点，对混合蛙跳算法进行改进。以子任务个数为8，可供选择的协同生产企业个数为29的任务分配为例，通过Matlab进行仿真实验，验证了算法有效性。

经过案例研究表明，算法中的青蛙可以通过自主学习实现自主的更新，使其适应度值增加，青蛙通过局部与全局的信息交换与寻优，能尽快的找到解空间中的最优解。协同生产企业的敏捷性与其所处的地理位置紧凑度这两个方面对解的优劣进行评价，对空间结构与数量结构进行有效的耦合，使协同企业尽量集中。但本文是以Scrum的敏捷框架为基础进行任务的分解，产品的最终交付一次次叠加的成果，在此基础上为了进一步提高任务分配的效率，下一步研究方向可以使用并行的分布式计算方式。

[1] Long Q.An agent-based distributed computational experiment framework for virtual supply chain network development[J].Expert Systems with Applications, 2014, 41(9): 4094-4112.

[2] Estler H, Nordio M, Furia C A, Meyer B. Awareness and merge conflicts in distributed software development[C].Proceedings of the 9th International Conference on Global Software Engineering, August 18-21, 2014, Shanghai, China.

[3] Scharff C. Guiding global software development projects using ScrumandAgile with quality assurance[C]. Proceedings of the 24thIEEE-CSConference on Software Engineering Education and Training,May22-24,2011,Hawaii,USA.

[4] Sidhu J S, Volberda H W. Coordination of globally distributed teams: A co-evolution perspective on off shoring[J].International Business Review, 2011, 20(3): 278-290.

[5] Swigger K, Hoyt M, Serçe F C, Lopez V, Alpaslan F N. The temporal communication behaviors of global software development student teams[J]. Computers in Human Behavior, 2012, 28(2): 384-392.14

[6] Ågerfalk P J, Fitzgerald B, Slaughter S A. Introduction to the Special Issue--Flexible and distributed information systems development: State of the art and research challenges[J]. Information Systems Research, 2009, 20(3): 317-328.

[7] Jia Q, Seo Y. Solving resource-constrained project scheduling problems: Conceptual validation of FLP formulation and efficient permutation – based ABC computation[J]. Computers & Operations Research, 2013,40(8):2037-2050.

[8] 范玉顺. 企业信息化管理的战略框架与成熟度模型[J]. 计算机集成制造系统, 2008, 14(7): 1290-1296.

Fan Y S. Strategy framework and maturity model for enterprise information-oriented management[J]. Computer Integrated Manufacturing Systems, 2008, 14(7): 1290-1296.

[9] Vallon R, Austria V, Drager C, Zapletal A, Grechenig T. Adapting to changes in a project's DNA：A descriptive case study on the effects of transforming agile single-site to distributed software development[C]. Agile Conference, July Aug. 1, 2014, 52-60.

[10] Alzoubi Y I, Gill A Q, Al-Ani A. Empirical studies of geographically distributed agile development communication challenges: Asystematic review[J]. Information & Management, 2016, 53(1): 22-37.

[11] Lee J C, Judge T K, McCrickard D S. Evaluating eXtreme scenario-based design in a distributed agile team[C]. Proceeding of the International Conferenceon Computer Human Interaction, May7- 12, 2011,Vancouver, BC, Canada.

[12] Razzak M A, Smite D. Knowledge management in globally distributed agile projects-lesson learned[C]. Proceeding of the 10th International Conference on Global Software Engineering, July13-16, 2015,CiudadReal,Spain.

[13] Gupta M, Fernandez J. How globally distributed software teams can improve their collaboration effectiveness[C]. Proceedings of the 6th International Conference on Global Software Engineering, Aug 15-18, 2011, Helsinki, Finland.

[14] Bass J M. Agile method tailoring in distributed enterprises: Product owner teams[C]. Proceeding of the 8th International Conference on Digital Object, August 26-29, 2013, Bari, Italy.

[15] Shrivastava S V, Rathod U. Categorization of risk factors for distributed agile projects[J]. Information and Software Technology, 2015, 58: 373-387.

[16] Qurashi S A, Qureshi M R J Q. The proposal of scaling the roles in scrum of scrums for distributed large projects[J].International Journal of Information Technology and Computer Science, 2015, 8: 68-74.

[17] Jia Q, Seo Y. Solving resource-constrained project scheduling problems: Conceptual validation of FLP formulation and efficient permutation-based ABC computation[J]. Computers & Operations Research, 2013,40(8):2037-2050.

[18] Lin J, Yu H, Shen Z, Miao C. Studying task allocation decisions of novice agile teams with data from agile project management tools[C]. Proceedings of the 29th ACM/IEEE international conference on Automated software engineering,May, 2006, Ottawa, Canada.

[19] Paasivaara M, Lassenius C, Heikkila V T. Inter-team coordination in large-scale globally distributed scrum: Do Scrum-of-Scrums really work?[C]. Proceeding of the International Symposium on Empirical Software Engineering &Measurement, September 20-21, 2012, Lund, Sweden.

[20] Butler Z, HaysJ.Task allocation for reconfigurable teams[J]. Robotics andAutonomous Systems, 2015, 68: 59-71.

[21] Nedjah N, Mendonça R M, Mourelle L M. PSO-based distributed algorithm for dynamic task allocation in a robotic swarm[J]. Procedia Computer Science, 2015, 51: 326-335.

[22] Ruano-Mayoral M, Casado-Lumbreras C, Garbarino-Alberti H, Misra S. Methodological framework for the allocation of work package singlob l software development[J]. Journal of Software Evolution and Process, 2014,26(5):476-487.

[23] Almeida L H, Albuquerque A B, Pinheiro P R. A multi-criteria model for planning and Fine-Tuning distributed scrum projects[C]. Proceedings of the 6th IEEE International Conference on Global Software Engineering, August, 15-18, 2011, Helsinki, Finland.

[24] Lamersdorf A, Münch J. A multi-criteria distribution model for global software development projects[J]. Journal of the Brazilian Computer Society, 2010, 16(2): 97-115.

[25] 张立, 王茜竹, 赵春江, 等. 基于心智与扩展合同网的半自治多智能体任务分配[J], 计算机集成制造系统, 2015, 21(11): 2885-2892.

Zhang L, Wang Q Z, Zhao C J, et al. Semi-autonomous multi-Agent task allocation method based on extended contract net and mental model[J]. Computer Integrated Manufacturing Systems, 2015, 21(11): 2885-2892.

[26] Ladgham A，Hamdaoui F，Sakly A，et al.Fast MR brainimage segmentation based on modified shuffled frogleaping algorithm[J]. Signal Image & Video Processing, 2015,9(5):1113-1120.

[27] Luo J，Li X，Chen M R，et al.A novel hybrid shuffledfrog leaping algorithm for vehicle routing problem withtime windows[J]. Information Sciences, 2015, 316(C):266-292.

[28] Luo J, Li X, Chen M, Liu H. A novel hybrid shuffledfrog leaping algorithm for vehicle routing problem withtime windows[J]. Information Sciences, 2015,316:266-292．

[29] Kaur P, Mehta S.Resource provisioning and work flowscheduling in clouds using augmented shuffled frogleaping algorithm[J].Journal of Parallel & DistributedComputing,2016,101(C): 41-50.

[30] 王硕, 唐小我. 虚拟企业敏捷性度量的AFHW方法[J]. 中国工程科学, 2002, 4(7):29-32.

Wang S, Tang X W. AFHW Approach to Virtual Enterprise Agility Measurement[J]. Strategic Study of CAE, 2002, 4(7):29-32.

Task assignment optimization for distributed cooperative development based on shuffled frog leaping algorithms

ZHOUCong1,JIANG Jijiao1*, YIN Ming2

2. School of ManagementNorthwestern Polytechnical UniversityXi’an 710072，China; Software and Microelectronics Northwestern Polytechnical UniversityXi’an 710072，China)

Geographically distributed collaborative development has become part of the development strategy for large and complex products. Complex products are composed of multiple subsystems, and each subsystem involves multiple disciplines, which makes the complex interaction between large complex R&D product enterprises and the outside world. In different stages of complex product development, a single enterprise is often limited by technology and resources, and cannot complete the entire process of product development independently. This requires mutual cooperation between enterprises, resource sharing, and risk sharing. Geographically distributed collaborative development can integrate the resources of different geographies, enterprises, and teams to reduce risks, but it also brings about coordination and cooperation issues between geographically distributed teams. In response to this phenomenon, this paper studies the problem of task assignment for large and complex products in a geographically distributed agile development environment.

This paper mainly does the following work: First, it proposes a task allocation optimization model for geographically distributed agile development based on hybrid shuffled frog-leaping algorithm. This model uses the scrum of scrums agile development model as the basic framework for the development and production of large and complex products, and decomposes the R&D and production tasks of complex products then takes the maximum agility and minimum geographic compactness of the enterprise of complex aviation products as the objective function. Second, the unconstrained coding method is used to encode the model solution, which the "cross" and "mutation" operators are introduced in the learning strategy of the hybrid shuffled frog-leaping algorithm to optimize the local and global search mechanism of the hybrid shuffled frog-leaping algorithm and improve the efficiency and convergence accuracy of the algorithm. Third, taking an aircraft engine R&D enterprise as an example, MATLAB software is used to simulate the example, and the convergence between the improved hybrid shuffled frog-leaping algorithm and the original hybrid shuffled frog-leaping algorithm is compared under the same experimental background. The experimental results show that the improved hybrid shuffled frog-leaping algorithm in this study is better and has stronger convergence ability in the task allocation process. Through the research of this paper, the following conclusions can be drawn. Aiming the goal of the two aspects of agility of the collaborative production enterprise and the compactness of its geographical location, we assign the tasks. The spatial structure and the quantitative structure are effectively coupled to make the best of collaborative enterprise. Centralization, as far as possible, can avoid the decrease in product production efficiency caused by the change in the geographic location of the collaborative production enterprise and project tasks. It has certain practical significance; Secondly, the improved hybrid shuffled frog-leaping algorithm obtains a task allocation scheme that is more in line with the actual task allocation of large and complex aviation products than the traditional hybrid shuffled frog-leaping algorithm. The improved hybrid shuffled frog-leaping algorithm can achieve autonomous updates through self-learning to increase the degree of value fitness so that the optimal solution in the solution space can be found as quick as possible. Thus, it has certain theoretical significance.

Complex product; Geographically distributed collaborative development; Shuffled frog-leaping algorithm; Agility

C935

A

1004-6062(2020)06-0148-008

10.13587/j.cnki.jieem.2020.06.015

2018-07-16

2019-01-04

Supported by the Humanities and Social Sciences of Ministry of Education Fund Project (16YJA630068, 18YJA630043), the Aeronautical Science Fund of China (2016ZG53071), theNatural Science Basic Research Plan in Shaanxi Province of China (2018JM7008)and the Seed Foundation of Innovation and Creation for Graduate Students in Northwestern Polytechnical University (ZZ2018036)

2018-07-16

2019-01-04

教育部人文与社会科学基金项目（16YJA630068、18YJA630043）；航空科学基金资助项目（2016ZG53071）；陕西省自然科学基础研究计划项目（2018JM7008）；西北工业大学研究生创意创新种子基金资助（ZZ2018036）

姜继娇（1979—），男，山东巨野人；西北工业大学管理学院管理科学与工程系主任，副教授；研究方向：项目管理与人力资源管理。

中文编辑：杜 健；英文编辑：Boping Yan