点击次数：

论文类型：会议论文

发表时间：2016-10-08

收录刊物：EI、CPCI-S、Scopus

页面范围：178-184

摘要：Many applications supported by the crowdsourcing are subject to delay constraints, and a real time result returned with a better partial fulfillment is preferable to the complement with delay latency. However, existing task assignment algorithms that only consider the case of full completion may not perform well. In this paper, we investigate the optimal online task assignment without knowledge about future task arrivals, which makes it tradeoff to assign high utility task with large deadline or less utility but more urgent task. The problem of computing optimal assignment for deadline aware tasks is formalized as an integer optimization problem. A dynamic programming based online algorithm for finding the optimal strategy for task assignment subject to delay constraints is proposed. And the time complexity of the algorithm is O(max(i is an element of){1,...,n}{r(i)}nT), where r(i) is the total number of subtasks of task T-i n is the number of total tasks, T is the deadline constraint. Experimental results show that the proposed algorithms have better performance in utility gain.