Task Allocation Considering Individual Efficiency Affected By Load

Task allocation is an important problem in multi-agent system,in which individual efficiency is the key factor affecting the system performance.Previous researches mainly consider the influence of the resource environment(including individual resources and contextual resources)on individual efficiency.However,according to psychology researches,in situations where social individuals execute tasks,such as crowdsourcing systems,individual efficiency will be affected by the load.Previous researches usually ignore this relationship.Therefore,based on the relationship between individual loads and his efficiency,this paper studies how to allocate tasks among social individuals to improve the system performance.Based on theoretical analysis,the task allocation problem considering individual dynamic efficiency and minimizing the maximum task completion time is proven NP-hard.This paper adopts the research mode that is from the shallower to the deeper.Firstly,the task allocation method in the homogeneous task environment(all tasks are the same)is studied.A greedy method is proposed and its approximate ratio is analyzed.As the number of tasks rises up,overload phenomenon among individuals is very common when applying the one-time task allocation method,and individual efficiency is very low in this case.Thus,a multi-round task allocation method is proposed to adapt to the large-scale task environment.The experimental results verify the effectiveness of the greedy strategy in the small-scale task environment,and the superiority of the multi-round strategy in the large-scale task environment.Secondly,the task allocation method in the heterogeneous task environment,which is more realistic,is further studied.In the heterogeneous environment,tasks are different in the requirement of the workload and the skill,and individuals are different in skills.Therefore,tasks should be allocated to skill-matched individuals with appropriate loads.Based on the research in the homogeneous task environment,this paper studies the heterogeneous task allocation methods in both small-scale and large-scale task environments.Experimental results show that the modified homogeneous task allocation methods perform well in the heterogeneous task environment.This paper finds that different heterogeneous task allocation sequences and execution sequences will lead to different task execution results considering the impact of individual load on his efficiency Therefore,the sequence optimization methods of the heterogeneous task allocation sequence and execution sequence are studied.Experimental results show that the sequence optimization can effectively improve the system performance.