技能和时间约束的在线团队形成问题的研究与实现

摘要

团队形成问题主要研究的是在一个候选专家集合中寻找一组专家，将他们聚集在一起以一种高效合作的方式完成某个给定项目或任务。经过近20年的研究，该问题已经得到了充分的演变，从基本的简单形式衍生出了多种更加贴合实际场景的变形问题，使得该问题的研究更加完善和丰富。随着实际场景中的业务需求不断精细化，一个项目对团队的需求已经不仅仅停留在满足项目所有技能这样的程度了，而是对项目的完成质量也提出了要求。目前，团队形成问题在一些在线劳动力市场平台、论文合著网络以及论文审稿分配（RAP）等领域都有着广阔的应用背景。因此该问题的研究在推进团队形成问题在科学领域进一步发展成熟的同时，还有着很大的应用价值。
　　在本文中，我们考虑了这样一种现实场景：给定一个具体项目P，它用一组需要的技能来描述，其中每个技能都有一个技能等级值和工作量，分别表示项目对该技能模块的最低等级要求和工作时间需求；同时，在为项目给定的候选专家集合中，每位候选专家都有一个最大可用工作时间和一组他拥有的技能，其中每项技能都给出了表示其专业程度的技能等级水平。在上述设定之下，本文提出一种项目技能等级和工作时间约束的团队形成问题。这种对项目和专家的技能进行等级刻画，同时对工作时间进行考量的研究之前是没有过的，因此，本文的工作具有较大的创新性。本文研究的目标是为上述项目P寻找一个团队和与之对应的任务分配方案，使得该团队对项目P的完成质量尽可能地高。我们把本文的这种高质量团队的形成（Quality-Team Formation）问题简称为QTF问题。为了对项目的完成质量进行具体描述，文中定义了一种团队得分函数Tscore(T)来评价所形成的团队对项目P的完成情况。此外，本文证明了该问题的计算复杂度是NP-hard，并给出了具体证明过程。为求解QTF问题，文中提出了两个启发式近似算法，分别为SkillFirst和ExpertAssign。这两个算法从问题的目标函数Tscore(T)出发，分为以技能和人员为中心，为项目各技能模块挑选专家加入团队。
　　本文在两个真实数据集上对文中提出的两个算法进行了大量实验来评价它们的性能。实验结果表明，两个算法均能为数据集中的各种项目自动形成高质量团队，并且各有所长。对比之下，算法SkillFirst形成的团队质量得分较高，并且在时间效率上比ExpertAssign显示出明显的优势；但是，算法ExpertAssign更容易形成精简而紧凑的小规模团队，更能够得到雇佣者的优先选择。

目录

声明

插图索引

表格索引

符号对照表

缩略语对照表

第一章 绪论

1.1研究背景和意义

1.2国内外研究现状

1.3本文主要工作及创新点

1.4论文章节安排

第二章 问题描述

2.1相关符号定义

2.2问题形式化定义

2.3 QTF问题的计算复杂度

2.4本章小结

第三章 技能分配优先算法SkillFirst的设计与实现

3.1技能优先级顺序的确定

3.2各项技能的内部分配

3.3 SkillFirst算法描述

3.4 Tie-breaker策略

3.5对SkillFirst算法的讨论

3.6本章小结

第四章 专家时间分配优先的算法ExpertAssign的设计与实现

4.1 ExpertAssign算法思想

4.2专家的最大可用价值

4.3 ExpertAssign算法描述

4.4算法的相关讨论

4.5本章小结

第五章 实验结果与分析

5.1实验数据集分析

5.2实验设置

5.3算法性能评估

5.4本章小结

第六章 总结与展望

6.1本文总结

6.2未来展望

参考文献

致谢

作者简介