摘要
团队形成问题，旨在为一个或者多个任务找到一个指定的团队来完成，这项研
究已经成为当前的一个热点研究领域。该问题的主要研究目的是如何为已知项目找
到一组合适的团队成员，使得项目的实施能够更加高效且项目负责人能够更均衡的
进行任务分配。近年对团队形成的研究主要分为以下几个方面：怎样使团队成员之
间通信开销最小，怎样使团队成本最低，怎样使得项目收益最大等。求解该类型的
问题对于各类众包服务平台，在线招聘和其他各个领域都具有非常广泛的实践意义

目前，针对该问题的研究存在着明显的缺点，专家在参与项目任务的分配是均被假
设能够参与所有的项目，然而，每个专家的专业程度和工作时间是完全不同的，以
前的研究往往将专家所能承受的工作量忽略，这会使得各个专家之间的任务分配不
均匀，导致团队合作不顺利以及项目完成受阻

在这篇论文中，我们针对以往问题的不足和缺点，提出了一个新的团队形成问
题，将专家的工作时间和能承受的最大工作量考虑在内。我们首先对提出的新问题
进行形式化的定义，给定一个项目集P和一个专家集X，每个项目有需要被完成的
技能且每个专家拥有自己的专业技能，薪资成本和参与约束（规定每个专家能够同
时参加的项目个数），问题的最优化目标是寻找到一个带参与约束的团队使其不仅能
够满足项目所有技能的要求而且成本最低。我们把这个问题叫做：参与约束的团队
形成问题。据研究表明，本文是第一个提出类似问题的论文。在此基础上，本文针
对参与约束的团队形成问题提出了一个特例问题，该特例致力于研究当专家的参与
约束大于项目个数的情况。我们证明提出的两个问题均为
NP-hard
问题且难近似。我
们针对特例问题提出了一个精确解算法，该算法依据提出的剪枝定理设计了两个剪
枝规则。同时我们针对参与约束的团队形成问题提出了三个近似算法，且每个算法
均有其自身的优势

在人工数据集和真实数据集上的实验结果表明：本文对精确解算法提出的两个
剪枝规则，大大降低了算法过程中的迭代次数，提高算法效率，相对暴力搜索算法
有明显的优势，同时，三个近似算法在寻找出符合要求的团队的同时能够满足寻找
不同侧重点团队的需求，在不同的方面表现出不同的优势

关关键键词词：：团队形成
,
任务分配
,
参与约束
,
低成本
,
最优化
。。。。。。以上无文本格式，具体下载查看