基于任务间优先关系约束的众包任务分配机制研究.docx

苏州大学本科生毕业设计（论文）III目录第1章绪论1第2章准备工作6第2.1节系统模型6第2.2节问题描述7第2.3节NP难特性分析9第3章算法设计11第3.1节解决STAP的近似算法11第3.1.1节确定各任务层次的部分12第3.1.2节构造最终任务集合的部分14第3.1.3节构造任务的优先分配序列的部分15第3.1.4节任务分配的部分18第3.2节解决PTAP的近似算法19第3.2.1节对任务执行时间的预估部分19第3.2.2节构造优先分配序列的部分20第3.2.3节任务分配的部分20第4章仿真模拟22第4.1节仿真环境参数设置22第4.2节仿真模拟结果23第5章结论28参考文献29致谢31摘要众包作为一个新兴的研究领域，通过极大地利用外部的、非确定的参与人群，旨在寻求一个更快捷且低成本的途径完成系统面临的各项任务。在众包的实际应用中，一个任务通常能够被划分成许多个步骤。不同步骤对任务执行者的技能存在不同的需求，同时，步骤间会有先后顺序的约束。根据每个步骤各自的需求，任务发布者将任务划分，再将划分后的多个子任务发布到众包系统中，由系统将这些子任务分配给参与其中的任务执行者。在经过大量的文献阅读后，我们发现对于被划分的子任务间存在先后顺序约束的众包机制研究，现阶段是不足的。另外，如果一个公司将一项完整的任务交由众包平台分配完成，那么该任务往往是公司的一个项目，因此，发布任务的公司通常会要求众包系统能够尽快地完成发布的任务。然而，现有的机制研究中并不存在与我们所提及的相关的设计，即一个针对任务之间的先后顺序约束，以完成所有任务花费的时间最小为优化目标的众包任务分配机制的设计。为弥补这方面存在的不足，我们对任务间存在的先后顺序约束加以考虑，并针对提出的众包系统设计了一个有性能保证的任务分配机制。由于证明了我们所提出的问题是一个NP难问题，为提高问题求解的效率，这需要我们对应地提出一个近似最优的算法。在仿真模拟阶段最终的结果表明，我们提出的算法在不同参数设置情形下算法结果始终能够获得很好的近似最优比。关键词：众包；任务分配；执行时间最小化；先后顺序约束。AbstractCrowdsourcingcanbeusedtoleverageexternalcrowdstoperformspecializedtasksquicklyandinexpensively.Intheapplicationofcrowdsourcing,onetaskmayoftenincludemanysteps.Differentstepsmayrequiredifferentskillsandhaveprecedenceconstraintsamongthem.Basedonthedifferentrequirementsofsteps,thetaskrequestermaydividethetaskintomanysub-tasks,andpublishthesub-tasksinthecrowdsourcingsystem.However,onlyfewexistingstudiesconsidertheprecedenceconstraintsamongthedividedsub-tasks.Moreover,onecompletetaskfromacompanymaybeaproject,andcompaniesusuallywanttofinishtheirprojectsasfastastheycan.Unfortunately,therehavebeennoallocationmechanismwithconsiderationofcrowdsourcingtaskswithprecedenceconstraintsandminimizationofthetotalexecutiontimesimultaneously.Totacklethischallenge,weconsidertheprecedenceconstraintsamongtasksanddesignanefficienttaskallocationmechanismforthecrowdsourcingsystem.WeprovethatthestudiedproblemisNP-hard,andproposeanapproximationalgorithm.Thesimulationresultsshowthattheproposedalgorithmhasgoodapproximateoptimalratiosunderdifferentparametersettings.Keywords:crowdsourcing;taskallocation;executiontime