Dynamic Assignment Algorithm Of Crowdsourcing Task Based On Time Window

Crowdsourcing is a new way to solve problems,which combines the wisdom of the public on the Internet to handle computer-hard tasks,such as entity resolution,sentiment analysis,and image labeling.In recent years,crowdsourcing has been widely used in many fields such as machine learning,data cleaning and data integration.In crowdsourcing technology,quality control,cost control,and latency control are three major research problems.The effective task allocation is an important means to balance the three objectives.The goal of most existing task assignment methods is to maximize task's answer quality with a fixed required number of workers for every task.Such task assignment method does not consider the impact of task difficulty on the allocation algorithm,which might lead to waste of workers on easy tasks while allocation of inadequate workers for difficult tasks.Some task assignment algorithms'goal is minimizing cost under a task's answer quality constraint,which does not take into account the impact of the worker's arrival order on economic costs.In addition,the existing task completion time control method is mostly based on reward incentives,and is not applicable to task assignment scenarios based on push mode.Aiming at the above problems,this paper proposes a dynamic assignment algorithm for crowdsourcing tasks based on time window.The main research work is as follows:(1)For minimizing cost under quality restriction,this paper proposes a task assignment algorithm based on weighted bipartite graph in time window(TAWBG).Firstly,we define a continuous prediction algorithm for task answer confidence which is suitable for task assignment in a time window.TAWBG can continuously predict task answer confidence after multiple workers answer a task,and then construct a weighted bipartite graph for the available worker set and assignable task set in the time window.TAWBG uses the confidence gain of the prediction as weight,and assigns the task with the largest weight to the corresponding worker.We also propose an optimization algorithm(TAWBGO),which prunes the worker with low degree of proficiency and reduces the times of updating and reordering the graph,in order to improve time efficiency and reduce economic costs.The experimental results show that,compared with other task assignment methods,the TAWBG and TAWBGO not only ensure the quality of the task answer,but also reduce the economic cost.In addition,the TAWBGO reduces the time complexity of task assignment and accelerates the execution time of the TAWBG by 40 times.(2)For balancing quality,cost and time,this paper proposes task assignment algorithms for maximizing completion degree under quality restriction,including task priority assignment with early deadline(TPAED)and task assignment based on urgency(TAU).The two algorithms can not only effectively control the quality of task answer,but also speed up task completion and reduce economic costs.The experimental results show that TPAED and TAU algorithms can effectively help the task to be completed within the deadline.