## 3 Problem Description  
This paper studies the dynamic task allocation method with deadline constraint in the volunteer computing platforms. The notations used in the paper are summarized in Table 1.  
Given a number of tasks in VC platforms, denoted by the set \(T=\{t_{1},\,t_{2},\,\ldots,\,t_{m}\}\). Suppose that each task \(t_{i}\) can be completed by any node \(n_{j}\) or several other nodes in the VC platforms. For easy expression, two unified concepts are first introduced in the VC platforms. The server hour means the unit time of the server. One unit means the number of tasks completed within one server hour. The concepts of task and node are given as follows:  
**Definition 1 (task)**. : _Task \(t_{i}\) is a double dimension array that is denoted by (\(t_{i}\).cost,\(t_{i}\).deadline). The unit of \(t_{i}\).cost is called server hour, meaning that \(t_{i}\) can be finished on the server for \(t_{i}\).cost hours; \(t_{i}\).deadline means the constraint of task \(t_{i}\), whose unit is hours. If the task \(t_{i}\) begins at time \(l_{1}\), the deadline constraint of task \(t_{i}\) means that task \(t_{i}\) must be completed before \(l_{1}+t_{i}\).deadline._  
For example, as shown in Figure 1(a), \(t_{3}\).cost = 5, which means that it will take five server hours to complete the task \(t_{3}\). If the deadline constraint of task \(t_{3}\) is three hours and begins at time \(l_{1}\), it means that task \(t_{3}\) must be finished before \(l_{1}+3\). **Definition 2 (node)**. : _Given a volunteer node set, denoted by the set \(N=\{n_{1},\,n,\,\ldots,\,n_{j}\}\), the computing power of each volunteer node \(n_{j}\) is denoted by \(n_{j}\).ablittility, it means that the number of tasks the node \(n_{j}\) can complete in an hour is \(n_{j}\). ability units._  
For example, as shown in Figure 1(b), \(n_{1}\). _ability_ = 1.3, which means that the volunteer node \(n_{1}\) can complete the number of tasks in an hour is 1.3 times unit. A dynamic task scheduling with deadline constraint at \(l_{1}\) moment can be denoted by \(t_{i}\). _assign_ = \(\{(n_{1},\,t_{1},\,l_{1}),\,(n_{2},\,t_{1},\,l_{1}),\,\ldots\,(n_{s},\,t_{1},\,l_{ 1})\}\). List of tasks at time \(l_{1}\) is shown in Figure 1(a), List of volunteer nodes at time \(l_{1}\) is shown in Figure 1(b) and the task allocation process is shown in Figure 1(c). Task \(t_{1}\) is taken as an example: The server starts to allocate computing resource to the task \(t_{1}\) at the initial time \(l_{1}\) and the task \(t_{1}\)'s allocation is denoted by \(t_{1}\).assign_ = \(\{(n_{1},\,t_{1},\,l_{1}),\,(n_{2},\,t_{1},\,l_{1}),\,(n_{3},\,t_{1},\,l_{1}),\,(n_{4},\,t_{1},\,l_{1}),\,(n_{5},\,t_{1},\,l_{1}),\,(n_{6},\,t_{1},\The calculation cost of \(t_{1}\) is seven units and \(n_{1}\) is scheduled to complete two-hour task \(t_{1}\) by the server. It is known that the number of tasks \(n_{1}\) can complete in an hour is 1.3 times unit. So, \(n_{1}\) can complete 2.6 units in two hours. By analogy, the total computing resources allocated to \(t_{1}\) can complete a total of eight units, which are more than seven units of \(t_{1}\). Furthermore, because the deadline constraint of \(t_{1}\) is two hours, so, \(t_{1}\) can be completed. Similarly, the computing resources allocated to \(t_{2}\) is \(t_{2}\)_assign_ = {(\(n_{3}\), \(t_{2}\), \(l_{1}+1\)), (\(n_{4}\), \(t_{2}\), \(l_{1}+1\)), (\(n_{5}\), \(t_{2}\), \(l_{1}+1\)), (\(n_{6}\), \(t_{2}\), \(l_{1}+1\)), (\(n_{1}\), \(t_{2}\), \(l_{1}+2\))}. The calculation cost of \(t_{2}\) is four units, and the deadline constraint of \(t_{2}\) is three hours, so \(t_{2}\) can be completed. The computing resources allocated to \(t_{3}\) is \(t_{3}\)_assign_ = {(\(n_{2}\), \(t_{3}\), \(l_{1}+2\)), (\(n_{3}\), \(t_{3}\), \(l_{1}+2\)), (\(n_{4}\), \(t_{3}\), \(l_{1}\) + 2), (\(n_{5}\), \(t_{3}\), \(l_{1}+2\)), (\(n_{6}\), \(t_{3}\), \(l_{1}+2\)), (\(n_{7}\), \(t_{3}\), \(l_{1}+3\))}. The calculation cost of \(t_{3}\) is five units and the deadline constraint of \(t_{3}\) is three hours.