基于活跃度的众包工作者信誉模型

针对现有众包系统不能有效地控制众包交互过程中工作者的活跃积极性和任务完成质量的问题,提出了一种基于活跃度的工作者信誉模型来实现众包平台的质量控制。该模型改进了平均信誉模型,从工作者活跃度和历史信誉值的角度提出了活跃因子和历史因子的概念。首先根据众包工作者最近30 d内参与众包活动的天数计算工作者的活跃因子;然后根据历史因子计算众包工作者的历史信誉值;最后根据计算出来的活跃因子和历史信誉值计算基于活跃度的工作者信誉值,以衡量众包工作者的工作能力。理论分析和测试实验结果表明：与平均信誉模型相比,根据基于活跃度的工作者信誉模型选取的众包工作者在任务完成质量上提高了4.95%,在任务完成时间上减少了25.33%;与基于证据理论信任模型相比,在任务完成质量上提高了6.63%,在任务完成时间上减少了25.11%。实验结果表明,基于活跃度的工作者信誉模型在实际众包项目中能够有效提高众包任务的完成质量,减少众包任务的完成时间。     

基于测试成本元素的众包测试缺陷数量估计模型

为实时监控众包测试任务过程从而对任务完成进行评估,针对分布式众包测试过程的不可预测性和测试成本的庞大性,从软件的可靠性出发,基于软件可靠性增长模型提出了一个同时考虑测试人力和测试报告两个测试成本元素的众包测试软件缺陷数量估计模型.首先分析两个成本元素的相关性,并依据成本元素相关性建立了一个分段式通用可靠性增长模型框架,并结合已有的3种测试工作量函数,以此估计出软件潜在缺陷数量和测试中的累积检测缺陷数量.在四组真实的众包测试数据集上的对比实验表明,模型的估计误差精度低于10％,优于传统可靠性增长模型.该模型能够利用较少实际数据进行缺陷预测,具有较强的实用性.     

基于众测操作记录的Web测试用例自动生成方法

众包测试是软件测试领域的一种新兴趋势,具有更加可靠、成本更低和效率更快的优点。但是由于众测工人专业水平不同,提交的测试用例报告缺乏规范性,为报告的审核、缺陷的复现都增加了困难。该文提出了一种通过众测工人的操作记录自动生成文本测试用例的新方法,并实现了该测试工具。首先,对测试工人的操作进行录制从而获取录制信息,录制信息可以划分为三大模块,包含静态页面信息、动态页面信息和交互信息;其次,通过深度优先遍历算法获取组件名称、组件类型、交互动作和交互数据,并按照众测工人的实际操作步骤生成测试序列;对于测试序列中存在组件名称匹配错误的问题,通过YOLOv5目标检测和OCR文字识别技术设计了n元组生成算法,用于生成组件名称与其选项的对应关系,并对匹配错误的组件名称进行自动修改;最后,通过自定义规则集将测试序列转换为文本测试用例。该方法自动生成统一规范的测试用例,降低了众测的门槛,提高了测试效率,并且有利于众测服务平台的质量评估工作。为了验证该方法的有效性,针对不同开发技术的Web系统进行了测试,并与目前最新版本的UFT,Selenium IDE和Katalon Recorder三款工具进行了对比。实...     

结合深度学习的缺陷报告优先级分类

在众包测试中,测试工人帮助软件管理者执行测试并提交测试报告。在这个过程中,软件管理者需要人工审查和评估提交的测试报告。许多测试工人试图快速完成工作来最大化利润,因此提交的缺陷报告质量不高。为了提高测试工人提交缺陷报告的质量同时合理评估测试工人的工作,研究基于众包测试平台绩效考核方法,取得一定的研究成果。为了分类测试工人提交的缺陷报告的优先级,文章提出基于深度学习的缺陷报告优先级分类模型,设计了基于卷积神经网络（ConvolutionalNeuralNetwork,CNN）和双向长短时记忆网络（BidirectionalLong Short-Term Memory Network,Bi-LSTM）结合的文本分类模型,并且在大规模的开源项目Eclipse缺陷库上进行实验,取得了不错的效果。     

众包质量控制策略及评估算法研究

随着Internet技术的快速发展,众包作为一种灵活有效的解决问题方式,开始受到人们越来越多的关注.由于众包的自由松散组织模式,使得如何有效地控制任务完成质量,并将欺骗类型工作者识别出来,成为目前众包研究中一个急需解决的问题.文中基于对众包工作者提交结果的评估与分析,提出了一种阶段式的动态质量控制策略,同时给出了一个组合式众包结果质量评估方法框架.经过实际数据的测试,文中提出的质量控制策略和众包结果质量评估方法具有较好的效果.     

基于社会关系的工作流任务分派策略研究

在工作流管理系统中,任务分派策略对工作流系统的性能影响较大,而人力资源社会属性的不稳定也给任务分派带来了挑战.一般的任务分派策略还存在以下问题:分派时只考虑候选资源的个体属性,忽略了流程中其他资源对候选资源的影响;需要为候选资源预先设置能力指标,但预设指标很难与候选资源的实际情况吻合,错误的能力指标会导致将任务分派给不合适的资源,降低工作流系统的性能.为克服上述问题,基于不同的状态转移视角和奖励函数,提出了4种基于Q学习的任务分派算法.通过对比实验,论证了基于Q学习的任务分派算法在未预设资源能力的情况下仍能取得较好效果,且支持在任务分派过程中考虑社会关系的影响,使得平均案例完成时间进一步降低.     

基于交叉熵方法的测试用例选择策略

基于交叉熵方法提出了一种启发式划分测试用例选择策略。该策略在待测软件参数已知的条件下,以总的测试费用最小为目的,利用交叉熵方法通过调整各个子域中测试用例选择的概率来选择测试用例。     

面向并发多任务的重叠联盟效用分配策略*

重叠联盟效用分配是多agent系统中的一个难点问题,文中提出面向并发多任务的重置联盟效用分配策略.首先基于能者多劳的思想采取按比例分配,对多个并发任务进行并行分派,并根据任务分派情况划分重叠联盟的效用.然后推演一个agent同时加入多个联盟时满足效用非减原则的充分必要条件.最后通过实例验证文中方法的有效性,并与串行效用分配进行对比分析.结果表明,在新agent申请加入联盟时,文中策略更易满足效用非减条件,具有更好的时效性.     

基于预测分析的时空众包在线任务分配

针对时空众包在线任务分配问题,提出任务范围调节算法DMRA与基于预测分析的在线任务分配算法PAMA。DMRA算法以任务位置为中心,根据工人密度动态调整任务的范围。PAMA算法基于历史统计概率,采用贝叶斯分类器预测下一时间戳的对象分布情况,在此基础上,执行带权二分图最优匹配算法以完成任务分配。实验结果表明,将DMRA算法与PAMA算法相结合,能够提升任务分配的总效用,降低工人的差旅成本,任务分配性能优于贪心算法与随机阈值算法。     

偏好匹配满意度最大化的众包任务分配

众包任务分配机制对众包任务完成质量起着至关重要的作用,然而现有的分配方法未在稳定性条件下考虑众包用户双边偏好,分配结果的准确性有待提高,并且存在众包用户因不满意当前分配对象而导致众包任务完成质量较低的问题.为此提出一种基于偏好匹配的众包任务分配方法,该方法首先考虑众包任务与工人的双边偏好,根据偏好序计算任务与工人的满意...     

Efficient task assignment for spatial crowdsourcing: A combinatorial fractional optimization approach with semi-bandit learning

Spatial crowdsourcing has emerged as a new paradigm for solving problems in the physical world with the help of human workers. A major challenge in spatial crowdsourcing is to assign reliable workers to nearby tasks. The goal of such task assignment process is to maximize the task completion in the face of uncertainty. This process is further complicated when tasks arrivals are dynamic and worker reliability is unknown. Recent research proposals have tried to address the challenge of dynamic task assignment. Yet the majority of the proposals do not consider the dynamism of tasks and workers. They also make the unrealistic assumptions of known deterministic or probabilistic workers’ reliabilities. In this paper, we propose a novel approach for dynamic task assignment in spatial crowdsourcing. The proposed approach combines bi-objective optimization with combinatorial multi-armed bandits. We formulate an online optimization problem to maximize task reliability and minimize travel costs in spatial crowdsourcing. We propose the distance-reliability ratio (DRR) algorithm based on a combinatorial fractional programming approach. The DRR algorithm reduces travel costs by 80% while maximizing reliability when compared to existing algorithms. We extend the DRR algorithm for the scenario when worker reliabilities are unknown. We propose a novel algorithm (DRR-UCB) that uses an interval estimation heuristic to approximate worker reliabilities. Experimental results demonstrate that the DRR-UCB achieves high reliability in the face of uncertainty. The proposed approach is particularly suited for real-life dynamic spatial crowdsourcing scenarios. This approach is generalizable to the similar problems in other areas in expert systems. First, it encompasses online assignment problems when the objective function is a ratio of two linear functions. Second, it considers situations when intelligent and repeated assignment decisions are needed under uncertainty.     

软件众包工人能力动态度量算法

针对现有软件众包平台对工人能力考虑不足，导致分配给工人的任务完成质量低下的问题，提出了一种软件众包工人能力动态度量算法（ADM），实现工人能力的动态度量。首先，基于静态技能覆盖率，实现工人初始能力的计算；其次，对于工人历史完成的单个任务，综合任务复杂度、任务完成质量及任务开发时效，实现开发能力的计算，并根据时间因子计算随时间衰减的开发能力；然后，根据所有历史完成任务的时间先后顺序，实现能力度量值的动态更新；最后，基于历史任务技能覆盖率，计算工人对于待分配任务的开发能力。实验结果表明，与用户可靠性度量算法相比，所提出的能力动态度量算法具有较好的合理性与有效性，使能力度量吻合度平均值最高达到90.5%，能有效指导任务分配。     

基于树分解的空间众包最优任务分配算法

随着配备高保真传感器的移动设备的普及以及无线网络资费的迅速下降,空间众包成为一种新型的问题解决框架,被用于将位置相关的任务（如路况报告,食品配送）分配给工人（配备智能设备并愿意完成任务的人）。本文研究空间众包中最优任务分配问题,关键在于设计出将每个任务分配给最合适的工人的任务分配策略,以使得完成的总任务数目最大化,而所有的工人可以在完成所分配的任务后,在预期最晚工作时间之前返回起点。找到全局最优分配是一个棘手的问题,因为该问题不等于单个工人的最佳分配的简单累加。本文注意到,仅有部分工人存在任务依赖,因此本文利用树分解技术将工人分割成独立的集合,并提出一种带启发式的深度优先搜索算法,该算法可以快速地更新启发函数界限,从而高效的对不可能成为最优解分配方案尽早地剪枝。实验表明,本文所提出的方法是非常有效的,可以很好地解决最优任务分配问题。     

时空众包环境下基于统计预测的自适应阈值算法

针对时空众包环境下任务分配随机性过高且效用值不理想的问题,提出一种基于统计预测的自适应阈值算法。首先,实时统计众包平台中空闲的任务、工人及工作地点的数量以设置阈值;其次,通过历史数据分析将任务与工人的分布分为均衡的两个部分,并用Min-max normalization方法为每个任务匹配一个确定的工人;最后,计算匹配到的工人出现的概率,以验证任务分配的有效性。使用相同真实数据的实验结果证实,与随机阈值算法相比,基于统计预测的自适应阈值算法的效用值提升了7%;与贪心算法相比,其效用值提升了10%。实验结果表明,基于统计预测的自适应阈值算法能够减少任务分配过程中的随机性并提高效用值。     

A heuristic and a branch-and-bound algorithm for the Assembly Line Worker Assignment and Balancing Problem

In traditional assembly lines, it is reasonable to assume that task execution times are the same for each worker. However, in Sheltered Work Centres for Disabled this assumption is not valid: some workers may execute some tasks considerably slower or even be incapable of executing them. Worker heterogeneity leads to a problem called the Assembly Line Worker Assignment and Balancing Problem (ALWABP). For a fixed number of workers the problem is to maximize the production rate of an assembly line by assigning workers to stations and tasks to workers, while satisfying precedence constraints between the tasks.This paper introduces new heuristic and exact methods to solve this problem. We present a new MIP model, propose a novel heuristic algorithm based on beam search, as well as a task-oriented branch-and-bound procedure which uses new reduction rules and lower bounds for solving the problem. Extensive computational tests on a large set of instances show that these methods are effective and improve over existing ones.     

基于动态阈值的时空众包在线分配算法

为提升时空众包动态现实场景中任务分配总效用,提出一种基于在线随机森林的动态阈值算法（DTRF）。首先,根据众包平台中工人和任务的历史匹配数据初始化在线随机森林;然后,通过在线随机森林预测每位工人期望的任务回报率作为阈值,按阈值为每个工人选取候选匹配集;最后,从候选匹配集中选取当前效用总和最高的匹配,同时用分配结果更新在线随机森林。实验结果表明,所提算法在提升总效用的同时有效地提高了工人的平均收益。与贪心算法相比,所提算法的任务分配率提升了4.1%,总效用提升了18.2%,工人平均收益提升了11.2%。与随机阈值算法相比,所提算法在任务分配率、总效用、工人平均收益等方面都有较好的提升,且稳定性更好。     

Robust assembly line balancing with heterogeneous workers

Assembly lines are manufacturing systems in which a product is assembled progressively in workstations by different workers or machines, each executing a subset of the needed assembly operations (or tasks). We consider the case in which task execution times are worker-dependent and uncertain, being expressed as intervals of possible values. Our goal is to find an assignment of tasks and workers to a minimal number of stations such that the resulting productivity level respects a desired robust measure. We propose two mixed-integer programming formulations for this problem and explain how these formulations can be adapted to handle the special case in which one must integrate a particular set of workers in the assembly line. We also present a fast construction heuristic that yields high quality solutions in just a fraction of the time needed to solve the problem to optimality. Computational results show the benefits of solving the robust optimization problem instead of its deterministic counterpart.     

附带翻转工位双边装配线蚁群算法优化设计

双边装配线应用广泛,翻转工位操作能有效降低部分零件装配难度与操作风险,但增加了设计难度。基于此,研究了附带翻转工位操作的挖掘机底盘双边装配线规划设计问题,针对该问题提出了一种改进蚁群算法求解。给出了问题求解的启发式任务分配规则,提出可采用启发式任务选择规则以提高算法收敛速率。进而分析某型挖掘机底盘装配线得出先后约束关系图,将问题抽象为双边装配线优化设计问题。随后,采用两种蚁群算法进行附带翻转工位的装配线优化,分析比较了两种算法因结构差异对优化结果所造成的影响。     

Hybrid Two-Phase Task Allocation for Mobile Crowd Sensing

As a result of the popularity of mobile devices,Mobile Crowd Sensing (MCS) has attracted a lot of attention. Task allocation is a significant problem in MCS. Most previous studies mainly focused on stationary spatial tasks while neglecting the changes of tasks and workers. In this paper,the proposed hybrid two-phase task allocation algorithm considers heterogeneous tasks and diverse workers.For heterogeneous tasks,there are different start times and deadlines. In each round,the tasks are divided into urgent and non-urgent tasks. The diverse workers are classified into opportunistic and participatory workers.The former complete tasks on their way,so they only receive a fixed payment as employment compensation,while the latter commute a certain distance that a distance fee is paid to complete the tasks in each round as needed apart from basic employment compensation. The task allocation stage is divided into multiple rounds consisting of the opportunistic worker phase and the participatory worker phase. At the start of each round,the hiring of opportunistic workers is considered because they cost less to complete each task. The Poisson distribution is used to predict the location that the workers are going to visit,and greedily choose the ones with high utility. For participatory workers,the urgent tasks are clustered by employing hierarchical clustering after selecting the tasks from the uncompleted task set.After completing the above steps,the tasks are assigned to participatory workers by extending the Kuhn-Munkres (KM) algorithm.The rest of the uncompleted tasks are non-urgent tasks which are added to the task set for the next round.Experiments are conducted based on a real dataset,Brightkite,and three typical baseline methods are selected for comparison. Experimental results show that the proposed algorithm has better performance in terms of total cost as well as efficiency under the constraint that all tasks are completed.