空间众包中多类型任务的分配与调度方法

来源：计算机应用杂志2018年第1期北京时间：

作者：毛莺池, 穆超, 包威, 李晓芳

单位：1. 河海大学 计算机与信息学院, 南京 211100;2. 常州工学院 计算机信息工程学院, 江苏 常州 213032

摘要：针对空间众包多类型任务完成的质量与数量问题，提出多类型任务的分配与调度方法。首先，在任务分配过程中，结合空间众包中多类型任务和用户的特点，对贪婪分配算法改进，提出基于距离ε值分配（ε-DA）算法；然后，将任务分配给附近的用户，以提高任务完成质量；其次，利用分支定界思想（BBS），根据专业匹配分数的大小，对任务序列进行调度；最后，找到最佳的任务序列。针对分支定界思想的调度算法运行速度较慢的问题，提出最有前途分支启发式（MPBH）算法。通过MPBH算法，使得在每次任务分配过程中实现局部最优化，与分支定界思想的调度算法相比，在运行速度上提高了30%。实验结果表明，所提方法能够提高任务完成的质量以及数量，有效地提高了运行速度与精确性。

关键词：空间众包,任务分配,任务调度,分支定界,局部最优

基金资助：国家自然科学基金资助项目（U1301252）；国家科技支撑计划项目（2013BAB06B04）；国家重点研发计划项目（2016YFC0400910）；国家科技重大专项（2017ZX07104-001）；中央高校基本科研业务费专项（2015B22214）。