Allocating Dynamic and Finite Resources to a Set of Known Tasks | Springer Nature Link (formerly SpringerLink) Skip to main content Advertisement Log in Menu Find a journal Publish with us Track your research Search Cart Home Intelligent Systems Conference paper Allocating Dynamic and Finite Resources to a Set of Known Tasks Conference paper First Online: 12 October 2023 pp 193–208 Cite this conference paper Access provided by University of Notre Dame Hesburgh Library Download book PDF Download book EPUB Intelligent Systems (BRACIS 2023) Allocating Dynamic and Finite Resources to a Set of Known Tasks Download book PDF Download book EPUB João da Silva  ORCID: orcid.org/0009-0003-0101-87049, Sarajane Peres  ORCID: orcid.org/0000-0003-3551-64809, Daniel Cordeiro  ORCID: orcid.org/0000-0003-4971-73559 & … Valdinei Freire  ORCID: orcid.org/0000-0003-0330-39319  Show authors Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 14195)) Included in the following conference series: Brazilian Conference on Intelligent Systems 521 Accesses Abstract We consider a generalization of the task allocation problem. A finite number of human resources are dynamically available to try to accomplish tasks. For each assigned task, the resource can fail or complete it correctly. Each task must be completed a number of times, and each resource is available for an independent number of tasks. Resources, tasks, and the probability of a correct response are modeled using Item Response Theory. The task parameters are known, while the ability of the resources must be learned through the interaction between resources and tasks. We formalize such a problem and propose an algorithm combining shadow test replanning to plan under uncertain knowledge, aiming to allocate resources optimally to tasks while maximizing the number of completed tasks. In our simulations, we consider three scenarios that depend on knowledge of the ability of the resources to solve the tasks. Results are presented using real data from the Mathematics and its Technologies test of the Brazilian Baccalaureate Examination (ENEM). This study was partially supported by the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) - Finance Code 001, by the São Paulo Research Foundation (FAPESP) grant #2021/06867-2 and the Center for Artificial Intelligence (C4AI-USP), with support by FAPESP (grant #2019/07665-4) and by the IBM Corporation. Access provided by University of Notre Dame Hesburgh Library. Download conference paper PDF Similar content being viewed by others An Adaptive Resource Allocation Protocol for Dynamic Environments Chapter © 2022 Research on Task Allocation and Resource Scheduling Method in Cloud Environment Chapter © 2020 Dynamic task scheduling with advance reservation of resources to minimize turnaround time for computational grid Article 12 March 2020 Explore related subjects Discover the latest articles, books and news in related subjects, suggested using machine learning. Dynamic Networks Human Resource Management Mental Training Operations Research and Decision Theory Theory and Algorithms for Application Domains Working Memory 1 Introduction The allocation of human resources to solve tasks is part of the daily routine of the most diverse institutions. Going from the allocation of employees in a company to the fulfillment of complex tasks [23], to the assignment of public lawyers to defendants by a court [1]. In the previous examples, if the decision-maker, which allocates resources to perform each set of tasks, is well aware of the abilities of each resource to solve the tasks, one can use the Hungarian Algorithm to obtain the optimal solution [15]. However, this is not always the case. There are numerous scenarios where the abilities of the resources are not known beforehand, for example, in a non-governmental organization allocating tasks to sporadic volunteers [5, 14]. Another example is crowdsourcing, the recent tendency in certain companies to allocate some tasks to non-specialized outsource workers [26, 28]. Some works use previous information about the resource to estimate their ability to solve the tasks [8, 11]. To guarantee the quality of the solutions given by unknown resources, it is necessary to estimate their ability to accomplish such tasks. The ability estimation can be done by the conduction of a test before the allocation of the tasks [25]; or by dynamically estimating the abilities during the allocation process, depending on the results of previous assignments [31]. Here, the resources’ abilities are dynamically estimated during the process, being updated after each response. Many works consider a threshold so that weaker resources do not receive any task [9, 25, 31]; instead, we consider the resources scarce and try to use the maximum of their availability. We allocate the dynamic and finite resources that arrive sequentially to try to solve a set of known tasks. We consider a finite number of human resources arriving sequentially; tasks are assigned to resources dynamically, and the resources can either complete them correctly or fail. Each task must be completed a number of times, and each resource can receive an independent number of tasks. No task is submitted twice to the same resource; each task can be submitted as many times as needed to different resources. Resources, tasks, and the probability of a correct response are modeled using Item Response Theory [6]. The task parameters are known, while the ability of the resources must be learned through the interaction between resources and tasks. We propose an algorithm that combines shadow test replanning [17] to replan under uncertain knowledge, with the goal of optimally allocating resources to tasks while maximizing the number of completed tasks. Each replanning consists in solving an optimization problem through linear programming. The results are compared with two baselines, the random selection and the easier-first selection that selects the easier task available as the resources arrive sequentially. In summary, the contributions of this paper are: (i) a novel allocation of dynamic finite resources to a set of finite binary tasks problem is formalized; and (ii) algorithms are proposed to solve the problem in different scenarios by using most of the resources’ availability. The rest of this paper is structured as follows: the proposed allocation problem is defined in Sect. 2. The proposed framework, with the definition of three algorithms, is presented in Sect. 3. Section 4 gives an overview of related works on the state of the art of task allocation. We present and discuss the results in Sect. 5, before concluding in Sect. 6. 2 The Allocation of Dynamic and Finite Resources to a Set of Binary Tasks Problem We consider the problem of repeatedly allocating resources to fulfill one of a set of tasks when finite resources are available dynamically. First, the decision-maker knows a set of tasks, in which each task must be solved an arbitrary number of times. Second, resources are available dynamically to receive a number of tasks to try to solve. Third, the decision-maker allocates the current resource to tasks, one after the other, until the resource’s availability ends. Fourth, for each allocated task, the resource may fail or may fulfill it. Finally, the decision-maker must allocate tasks to fulfill the largest number of tasks. We consider the following process: 1. while there is time, wait for resource: (a) a resource arrives. While the resource is available: i chooses and presents a task to the resource under two constraints: (i) the task was solved successfully less than a desired level; and (ii) the task has not been presented to the current resource; ii the resource tries to solve the task; and it is observed whether the task was solved or not. This process is formalized mathematically by the following definition: Definition 1 (Dynamic Allocation of Resources to solve Tasks Multiple Times - DART-MT). Let \(\mathcal {T}\) be a set of tasks and \(\mathcal {R}\) a set of human resources. Consider the function \(n: \mathcal {T} \rightarrow \mathbb {N}\), n(t) indicates the number of times the task t must be solved. Also, consider the function \(m: \mathcal {R} \rightarrow \mathbb {N}\), m(r) indicates the number of tasks that can be assigned to resource r. \(\zeta _{t}\) is a vector of parameters for task \(t \in \mathcal {T}\). \(\theta _{r}\) is a vector of parameters for resource \(r \in \mathcal {R}\). \(f(\zeta _{t}, \theta _{r})\) is a function that represents the probability of the task t be fulfilled by the resource r. There is an order of resources arriving \(Q = (r_{1}, r_{2}, \ldots , r_{|\mathcal {R}|})\), where \(r_{i} \in \mathcal {R}\) and \(r_{j} \ne r_{i}\) for all \(i \ne j\). The problem of dynamic resource allocation to solve tasks multiple times is defined by the tuple \((\mathcal {T}, \mathcal {R}, n, m, \{\mathbf {\zeta }_{t}\}, \{\mathbf {\theta }_{r}\}, f, Q)\) and the objective is to maximize the expected number of solved tasks. Because the result of a resource r trying to solve a task t is stochastic, an optimal solution is clearly contingent on past results; in the Markov Decision Process jargon, policies. Here, we considered different scenarios of knowledge about the problem DART-MT, where optimal solutions are contingent on information collected during the process. We consider three different scenarios. In every scenario probability function (f), tasks parameters and demands (\(\mathcal {T}\), n, and \(\{\mathbf {\zeta }_{t}\}\)) are known beforehand; they may be obtained from calibration in another set of resources. Information about the resources (\(\mathcal {R}, m, \{\mathbf {\theta }_{r}\}\) and Q) may be revealed directly or indirectly during the process. We differentiate knowledge of the current resource and future resources to define the following scenarios: (KK) known-known: fully-revealed, i.e., resources \(\mathcal {R}\), availability function m, parameters \(\{\mathbf {\theta }_{r}\}\) and arrival order Q are known before hand; (KU) known-unknown: the number of resources \(|\mathcal {R}|\) and the current resource r is fully-revealed (availability m(r) and parameter \(\mathbf {\theta }_{r}\)); while future resources are known to be drawn from an a priori distribution on parameters \(\varTheta \) and availability M; and (UU) unknown-unknown: the number of resources \(|\mathcal {R}|\) and the a priori distribution on parameters \(\varTheta \) and availability M are revealed; the current resource r reveals its availability m(r), while its parameters must be learnt from results after submitting tasks to the resource. We note that the objective of managing to solve a task gets more difficult when knowledge is hidden from the decision maker, i.e., a decision maker should solve the largest number of tasks in scenario KK while solving the smallest number of tasks in scenario UU. To obtain an upper bound to the DART-MT problem, we relax the problem regarding the allocation and results of submitting a task to a resource. First, we allow a resource r to be partially allocated to a task t (decision \(s_{r,t}\)). Second, a resource r solves a task deterministic and partially, given by \(P_{r, t} = f(\zeta _{t},\theta _{r})\). Third, \(x_{r,t}=s_{r, t} P_{r, t}\) indicates the amount of task t to be solved by resource r. Then, the following Linear Programming obtains an upper bound to the DART-MT problem: $$\begin{aligned} \max \quad & \sum _{t \in \mathcal {T}} \sum _{r \in \mathcal {R}} x_{r, t} & \end{aligned}$$ (1) $$\begin{aligned} \text {subject to} \quad & s_{r, t} \in [0,1] & \forall r \in \mathcal {R}, t \in \mathcal {T} \end{aligned}$$ (2) $$\begin{aligned} & x_{r, t} = s_{r, t} P_{r, t} & \forall r \in \mathcal {\text {subject to} R}, t \in \mathcal {T} \end{aligned}$$ (3) $$\begin{aligned} & \sum _{t \in \mathcal {T}} s_{r, t} \le m(r) & \forall r \in \mathcal {R} \end{aligned}$$ (4) $$\begin{aligned} & \sum _{r \in \mathcal {R}} x_{r, t} \le n(t) & \forall t \in \mathcal {T} \end{aligned}$$ (5) 3 \(\mathbf {[STA]^2O}\): A Shadow Test Approach to Skill-Based Task Allocation Optimization To solve the DART-MT problem in each of the three scenarios (KK, KU, and UU), we consider three levels of time abstractions: episodes, rounds, and steps. An episode comprehends the whole process of DART-MT problems when each resource \(r\in \mathcal {R}\) tries to solve m(r) tasks. A round comprehends the whole interaction with a resource r when the resource r tries to solve m(r) tasks. A step comprehends the interaction of a resource r and a task t. For each of the three scenarios, we define three different algorithms; all of them are based on the solution of an LP similar to LP in Eqs. 1–5. Then, at any step j of a round i consider: the current resource \(r_{i}\) and the set of tasks \(T_{i,j}\) that was presented to resource \(r_{i}\) before the step j or has already been completely solved as demanded by the function n(j); then, at step j a task t is drawn with probability: $$\begin{aligned} P_{t} = \frac{s_{r_{i},t}}{\sum _{t'\in \mathcal {T}\setminus T_{i,j}}s_{r_{i},t'}}, \end{aligned}$$ (6) where \(s_{r,t}\) for any \(r\in \mathcal {R},t\in \mathcal {T}\) is the solution of the LP. To solve the DART-MT problem in scenario KK, an LP is solved for each episode. To solve the DART-MT problem in scenario KU, an LP is solved for each round. To solve the DART-MT problem in scenario UU, an LP is solved for each step. In scenarios KU and UU, where knowledge is not full-revealed a priori, LPs are defined based on population information, and when new information is revealed, per round or per step, a new LP is solved. This strategy of fully planning based on population information and replanning when information is renewed is used in the Shadow Test Approach (STA) [18, 19, 30]. The Algorithm 1 shows a general solution to DART-MT problems conditioned in one of the three scenarios. Algorithm 1 The General Solution to DART-MT conditioned for any scenario Full size image KK Scenario and per Episode Algorithm - LPPE. Because the scenario KK knowledge is fully revealed a priori, the LP to be solved is the one described in Eqs. 1–5. The solution to the LP problem provides us with a set of (partial) tasks to be presented for each resource. Note that tasks are selected stochastically, but guarantee that a task t cannot be submitted repeatedly to the same resource and cannot be submitted beyond its demand n(t). Since planning occurs only once, the only adaptation occurs through set \(T_{i,j}\) to avoid violating the constraints of the DART-MT problem. KU Scenario and the per Round Algorithm - LPPR. Let \(\hat{\mathcal {R}}\) be the set of resources that have already been selected from \(\mathcal {R}\), \(\tilde{\mathcal {R}}\) be the set of \(|\mathcal {R}| - |\hat{\mathcal {R}}| - 1\) resources drawn from distributions \(\varTheta \) and M, and \(r_{i}\) be the current resource. An adaptation of the previous LP problem is modeled as follows: $$\begin{aligned} \max \quad & \sum _{t\in \mathcal {T}} \sum _{r \in \tilde{\mathcal {R}} \cup \{r_{i}\}} x_{r, t} & \end{aligned}$$ (7) $$\begin{aligned} \text {subject to}\quad & s_{r, t} \in [0,1] & \forall r \in \tilde{\mathcal {R}} \cup \{r_{i}\}, t \in \mathcal {T} \end{aligned}$$ (8) $$\begin{aligned} & x_{r, t} = s_{r, t} P_{r,t} & \forall r \in \tilde{\mathcal {R}} \cup \{r_{i}\}, t \in \mathcal {T } \end{aligned}$$ (9) $$\begin{aligned} & \sum _{t \in \mathcal {T}} s_{r, t} \le m(r) & \forall r \in \tilde{\mathcal {R}} \cup \{r_{i}\} \end{aligned}$$ (10) $$\begin{aligned} & \sum _{r \in \tilde{\mathcal {R}} \cup \{r_{i}\}} x_{r, t} + \sum _{r \in \hat{\mathcal {R}}} \hat{ x}_{r,t} \le n(t) & \forall t \in \mathcal {T} \end{aligned}$$ (11) with \(\hat{x}_{r, t} = 1\) if the resource r succeeded on the already presented task t and 0 otherwise. Instead of just solving an LP problem once for the episode, the LPPR algorithm solves an LP problem after arriving and being revealed the next resource. Replanning is done considering previous results on tasks submitted to previous resources and the knowledge regarding the current resource, whereas future resources are drawn from a priori distributions. UU Scenario and the Per Step Algorithm - LPPS. Let \(\hat{\mathcal {R}}\) be the set of resources that have already been selected from \(\mathcal {R}\), \(\tilde{\mathcal {R}}\) be the set of \(|\mathcal {R}| - |\hat{\mathcal {R}}| - 1\) resources drawn from distributions \(\varTheta \) and M, \(r_{i}\) be the current resource, \(T_{i}\) the set of tasks already submitted to resource \(r_{i}\), and \(\hat{P}_{r_{i},t}\) be the estimation probability of success given current resource \(r_{i}\) and task t. An adaptation of the previous LP problem is modeled as follows: $$\begin{aligned} \max \quad & \sum _{t\in \mathcal {T}} \sum _{r \in \tilde{\mathcal {R}}} x_{r, t} + \sum _{t\in \mathcal {T}\setminus T_{i}} x_{r_{i}, t} & \end{aligned}$$ (12) $$\begin{aligned} \text {subject to}\quad & s_{r, t} \in [0,1] & \forall r \in \tilde{\mathcal {R}}, t \in \mathcal {T} \end{aligned}$$ (13) $$\begin{aligned} & s_{r_{i}, t} \in [0,1] & \forall t \in \mathcal {T}\setminus T_{i} \end{aligned}$$ (14) $$\begin{aligned} & x_{r, t} = s_{r, t} P_{r,t} & \forall r \in \tilde{\mathcal {R}}, t \in \mathcal {T } \end{aligned}$$ (15) $$\begin{aligned} & x_{r_{i}, t} = s_{r_{i}, t} \hat{P}_{r_{i},t} & \forall t \in \mathcal {T}\setminus T_{i} \end{aligned}$$ (16) $$\begin{aligned} & \sum _{t \in \mathcal {T}} s_{r, t} \le m(r) & \forall r \in \tilde{\mathcal {R}} \end{aligned}$$ (17) $$\begin{aligned} & |T_{i}| + \sum _{t \in \mathcal {T} \setminus T_{i}} s_{r_{i}, t}\le m(r_{i})& \end{aligned}$$ (18) $$\begin{aligned} & x_{r_{i},t} + \sum _{r \in \tilde{\mathcal {R}}} x_{r, t} + \sum _{r \in \hat{\mathcal {R}}} \hat{ x}_{r,t} \le n(t) & \forall t \in \mathcal {T}\setminus T_{i} \end{aligned}$$ (19) $$\begin{aligned} & \hat{x}_{r_{i},t} + \sum _{r \in \tilde{\mathcal {R}}} x_{r, t} + \sum _{r \in \hat{\mathcal {R}}} \hat{ x}_{r,t} \le n(t) & \forall t \in T_{i} \end{aligned}$$ (20) with \(\hat{x}_{r, t} = 1\) if the resource r succeeded on the already presented task t and 0 otherwise. Here, the LPPS algorithm solves an LP problem on every step (after each task submission). Again, replanning is done considering previous results on tasks submitted to previous resources and the knowledge regarding the current resource, whereas future resources are drawn from a priori distributions. However, knowledge regarding the current resource is updated after every trial of solving a task, depending on the parameters of the task already submitted and the given results, success or failure. We postpone the discussion of estimating parameters of the current resource to Sect. 5. 4 Related Work In this work, a new problem (DART-MT) is defined with specific settings. Therefore, there is not an obvious state-of-the art method to be compared to ours. We used as baselines a random selection and the heuristic easier first, even though methods applicable to similar problems are briefly compared to our approach in the following paragraphs. Many works make use of resource skills to improve the task allocation problem [4, 10, 14, 20, 27, 29]. Some of them use this approach to improve allocation in project management or in crowdsourcing context, where the tasks are allocated to more than one resource to receive a number of solutions. However, these works assume the ability of the resources are given or can be estimated from a content-based approach, which is not always the case. Our work stands on a cold start, i.e., we do not have any previous information about the resources. In recent works, social search engines have become very useful as it uses information about the resources so as to improve task allocation [2, 3, 8, 11]. These studies use techniques like ranking function and information retrieval in the context of crowdsourcing or the Q &A Problem. Although similar to our work in the sense of optimizing task allocation, we do not use previous information about the resources and estimate their skills from the interaction with the tasks. Also, we do not use a threshold to reject weaker resources. The STA is largely discussed in the context of adaptive tests [18, 19, 30]. In this context, many works address the problem of task allocation by learning information about the resources [12, 24]. They repeatedly administer tasks to resources; however, the objective of these works is restricted to better estimating the resources’ abilities. We use the same approach in a different context and with a different purpose since we use resource characterization to optimize the allocation of tasks by maximizing the number of solutions, not having resource characterization as an end in itself. In some works [9, 25, 31], resources and tasks are dynamically characterized. The tasks are allocated to a resource if the probability of a correct answer is above a threshold. Our study does not limit the allocation of tasks by a threshold. Also, the purpose is different, in their case, each resource receives only one task, and each task needs only one solution. 5 Experiments and Results To evaluate the proposed algorithms, we adapt real data from an exam of mathematics to emulate tasks (questions) and resources (students). Within this data, we construct different DART-MT problems to identify the difference in the performance of our algorithms in the three scenarios KK, KU, and UU. Finally, we present the improvement of our algorithms against two baselines: uniformly random and easier first. 5.1 Real World Database Evaluating in Real World Data. Real data can be obtained, basically, in two ways: online or offline. The online test consists of presenting tasks to human resources while the process is running, whereas the offline test consists of using a database that was previously collected. The advantage of the online test is to apply the method in the real world with resources interacting directly with the allocation process. The downside is that access to such resources is very costly, so getting a reasonable amount of human resources available to receive tasks is very complicated. The advantage of the offline test is precisely that it can take advantage of a database, but the interaction of the process with the real world is lost. To use an offline test, the database need to meet certain criteria: (i) the independence of task solution conditioned on the resource, and (ii) all tasks have been submitted to all resources. The success or failure of each task submission is obtained from the history taken from the database. We can choose any task for a resource and check in the history if he has solved the task correctly or not. One can arbitrarily choose resources, their arrival order, and their availability without loss of generality. Availability must always be at most equal to the total amount of existing tasks in the database. It is equally possible to choose tasks and the number of solutions for them arbitrarily. The number of solutions demanded by each task must be equal to or less than the total amount of resources in the database. With historical data in hand, it remains to model the parameters \(\zeta \), \(\theta \), and the success probability function f. ENEM Database. A database of the 2012 Brazilian baccalaureate examination (ENEM) containing responses from ten thousand people (resources) and 185 questions (tasks) was used. The data are public and can be downloaded from the transparency portal [13]. ENEM uses Item Response Theory to model tasks (\(\zeta \)), resources (\(\theta \)), and the success probability function (f). This exam is used to assess the level of knowledge (skills) of students in four areas of knowledge: human sciences; natural sciences; languages; and mathematics. In this work, only the exam of mathematics was considered. We calibrate task parameters on data from 10,000 students and make use of the three-parameter logistic model, where parameter b indicates the difficulty of a question. We make use of such parameters to construct a baseline policy where the current resource always receives the easiest allowed task, the heuristic easier first. 5.2 Defining DART-MT Problems From the database with the answers of ten thousand ENEM students, the average chance of the task t to be correctly solved is estimated by: $$\begin{aligned} k(t) = \frac{\text {number of resources that solved the task } t \text { correctly}}{\text {number of resources that tried to solve the task } t} \end{aligned}$$ (21) The responses of all students in the database were used to calculate k(t) and \(k_{mean} = \frac{\sum _{t\in \mathcal {T}}k(t)}{|\mathcal {T}|}\). However only one hundred of them are sampled to evaluate the method at each episode. So, from now on we consider \(|\mathcal {R}| = 100\) and the 45 math items from the ENEM’s mathematics test as the tasks, so \(|\mathcal {T}| = 45\). Depending on the number of solutions for each task, n(t), and the availability of each resource, m(r), solving all the required tasks can be more or less difficult. In this way, we define the following difficulty levels: Level 1: $$\begin{aligned} n(t) = \lceil {|\mathcal {R}| \times k_{mean}}\rceil \quad \forall t \in {\mathcal {T}}\end{aligned}$$ (22) $$\begin{aligned} m(r) = \lceil |\mathcal {T}| \times k_{mean} \rceil \quad \forall r \in \mathcal {R} \end{aligned}$$ (23) Level 2: $$\begin{aligned} n(t) = \lceil {|\mathcal {R}| \times k(t)}\rceil \quad \forall t \in \mathcal {T}\end{aligned}$$ (24) $$\begin{aligned} m(r) = \lceil |\mathcal {T}| \times k_{mean} \rceil \quad \forall r \in \mathcal {R} \end{aligned}$$ (25) Level 3: n(t) is defined as the number of correct solutions for the task t and m(r) as the number of tasks the resource r solved correctly. In levels 1, 2, and 3, we have that \(\sum _{t\in \mathcal {T}} n(t) \approx \sum _{r\in \mathcal {R}} m(r)\). Note that we can only get all the desired solutions for difficulty levels 1 and 2 if all resources have the same ability or/and if all tasks have the same difficulty. To obtain all the solutions for level 3, we have to present for each resource exactly the tasks that user can solve correctly. One way to relax the levels is to decrease the number of solutions desired for each task, for example, \(n'(t) = n(t) \times 0.5\). We apply such relaxed version to level 3 to obtain the Level 4. Another more-relaxed level, let’s call Level 0, is: given \(k_{mean}\), we compute n(t) and m(r) as constant values such that $$\begin{aligned} |\mathcal {R}| \times m(r) \times k_{mean} = |\mathcal {T}| \times n(t) \end{aligned}$$ (26) For this level, we choose \(m(r) = 16 \approx \sum _{t \in \mathcal {T}} k(t)\) and we get \(n(t) = 12\) from the Eq. 26 with \(k_{mean} = 0.34\). Empirical Experiment. For each difficulty level and algorithm, we run 100 episodes. For each episode, one hundred resources are used from a previous random sample among the ten thousand available students. All simulations were performed in a Google Colaboratory environment. All codes were written in Python 3 language. To solve LP problems, we used the Pulp module and the open-source solver Coin-or Branch and Cut (CBC) [22]. 5.3 Results Using Real World Data We use the five levels defined before to evaluate our proposed algorithms. The results obtained for each level and in each scenario are shown in the Table 1. The proposed approaches are compared against two baselines: the uniform random selection and the heuristic easier first. The comparison is by the number of tasks solved correctly. Besides solving each scenario with the corresponding time abstraction, we also apply per round algorithm to the scenario KK to be contingent on trial results. Table 1. Results for all scenarios and algorithms.Full size table Discussion. Regardless of the knowledge of the resource’s ability to solve the tasks, the algorithms LPPE, LPPR, and LPPS obtained quantities of solutions greater than the baselines (random and easier first) for all levels. In the case resources’ abilities are well known, the algorithms LPPE and LPPR are better than the baselines and can be computed in a feasible time (less than three minutes per episode). If we do not know the ability of the resources to whom the tasks should be submitted, we use the algorithm LPPS, which furnished a better allocation than the baselines for all five levels. The algorithm LPPS takes about forty minutes per episode, and the resources need to wait no more than 1.7 s to receive a task to try to solve (it was the case of the level 0, with the results shown on Table 1). Note that the algorithms only make sense to be applied in certain scenarios. For example, in scenario UU, it doesn’t make sense to use the per episode algorithm since we will allocate the tasks based on the solution of an LP problem whose resources’ abilities were unknown. Also, if we are in the scenario KK, it is not necessary to solve an LP problem at each step if the resources’ abilities are well known from the beginning. To better visualize the results, box plot graphics are shown for all scenarios, levels, and algorithms in Fig. 1. The name of the algorithms are abbreviated: random (rand), easier first (E-F), per episode (Ep), per round (Res), and per step (Sub). Fig. 1. Box plots results for all scenarios and levels Full size image To better analyze the results, we used statistical tests to verify which algorithm produced the higher number of solutions. The first step was to use the Shapiro-Wilk test to determine the data normality. With \(95\%\) of significance, the data do not deviate from a normal distribution, except for the results for some algorithms of level 0. As we have a lot of samples (100 per episode), we used the Analysis of Variance (ANOVA) test to compare the algorithms for each scenario in all levels, including level 0. The results of the ANOVA tests determined that for all scenarios in all levels, there are statistically significant differences, with \(95\%\) of significance. From the ANOVA test results, the number of solutions is not statistically equivalent between the algorithms used in each scenario and level. Then, we used the Tukey pairwise multiple comparisons (post hoc) test to verify which means differ, with \(95\%\) of significance. Specific algorithms are used in each scenario: KK: random; easier first; per episode; and per round. KU: random; easier first; and per round. UU: random; easier first; and per step. From the results of the Tukey post hoc test, the proposed algorithms per episode, per round and per step are better than the baselines (random and easier first) for all scenarios in all levels, except for the algorithm LPPS and the baseline easier first in the scenario UU at level 3. In this comparison, the Tukey test resulted in no statistical difference in the number of solutions. Figure 2 shows (for the first episode) the number of submissions and solutions, the mean of the difficulties of allocated tasks, and the ability of the resources for these two algorithms for scenario UU at level 3. From this figure, resources with higher abilities are available to receive more tasks at level 3. This is a very appropriate case for the easier first algorithm since the more tasks the resources receive following the easier first heuristic, the more difficult tasks received. Fig. 2. Algorithms at level 3, on the first episode. Full size image The algorithms per episode and per round in the scenario KK are statistically equivalent. It is expected since in the scenario KK, all the resources’ abilities are well known beforehand, then the gain in doing replannings after each round is not significantly better than planning once at the beginning of the episode. The heuristic easier first is better than the random selection at most levels, except at level 0. Figure 3 shows (for the mean of all episodes) the number of submissions and solutions, the mean of the difficulties of allocated tasks, and the ability of the resources for these two algorithms at level 0. The mean of all episodes is used so that the influence of the ability of the resources is diminished. We can see that the mean of the abilities goes to zero. In the easier first allocation, it is clear the difficulty of tasks increases over the steps, whereas the number of solutions decreases. While in the random allocation, the difficulty of the tasks is approximately uniform. The last resources receive tasks slightly more difficult because the easier already received the needed number of solutions. These characteristics from both algorithms explain why the random made more allocations (approximately \(4\%\)) than the easier first, which led to receiving more solutions (approximately \(1\%\)). Fig. 3. Algorithms at level 0, mean of all episodes. Full size image 6 Conclusion and Future Work We can compare how far is the algorithm LPPS from the baselines and from the optimal case, that is, when we have the most information: scenario KK and the solution of the LP problems is updated per round. We have an increase in the number of solutions compared with the baselines on all levels. Compared with the baseline easier first, we have up to almost \(9\%\) more solutions; compared with the random, we have up to \(49\%\) more solutions. When we compare with the optimal case, the UU scenario using the LPPS algorithm reached up to \(96\%\) of the number of solutions of the optimal case. These processes could be used to submit fewer tasks to resources without losing important information. For example, when asking people to answer polls or to generate databases to be used in important applications such as Q &A, intelligent tutoring systems, or natural language processing. In addition to the abilities of the resources being unknown, there is also the case in which the complexity of solving the tasks is unknown. Therefore, estimating parameters that characterize such tasks become necessary [7, 21]. The task parameters can be obtained from the solutions of the tasks or from a description of them [16]. We plan on considering scenarios where the resource is not continuously available to receive tasks, but he arrives and goes. Also, we plan on developing a real experiment with human resources receiving tasks and not only using real data from other applications. References Abrams, D.S., Yoon, A.H.: The luck of the draw: using random case assignment to investigate attorney ability. Univ. Chic. Law Rev. 74(4), 1145–1177 (2007). http://www.jstor.org/stable/20141859 Ali, I., Chang, R.Y., Hsu, C.H.: SOQAS: distributively finding high-quality answerers in dynamic social networks. IEEE Access 6, 55074–55089 (2018) Article  Google Scholar  Aydin, B.I., Yilmaz, Y.S., Demirbas, M.: A crowdsourced “who wants to be a millionaire?’’ player. Concurr. Comput. Pract. Exp. 33(8), e4168 (2017) Article  Google Scholar  Ben Rjab, A., Kharoune, M., Miklos, Z., Martin, A.: Characterization of experts in crowdsourcing platforms. In: Vejnarová, J., Kratochvíl, V. (eds.) BELIEF 2016. LNCS (LNAI), vol. 9861, pp. 97–104. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-45559-4_10 Chapter  Google Scholar  Bezerra, C.M., Araújo, D.R., Macario, V.: Allocation of volunteers in non-governmental organizations aided by non-supervised learning. In: 2016 5th Brazilian Conference on Intelligent Systems (BRACIS), pp. 223–228 (2016) Google Scholar  Birnbaum, A.: Some latent trait models and their use in inferring an examinee’s ability. In: Lord, F.M., Novick, M.R. (eds.) Statistical Theories of Mental Test Scores, Reading, Charlotte, NC, pp. 397–479. Addison-Wesley (1968) Google Scholar  Bock, R.D., Aitkin, M.: Marginal maximum likelihood estimation of item parameters: application of an EM algorithm. Psychometrika 46(4), 443–459 (1981) Article  MathSciNet  Google Scholar  Difallah, D.E., Demartini, G., Cudré-Mauroux, P.: Pick-a-crowd: tell me what you like, and i’ll tell you what to do: A crowdsourcing platform for personalized human intelligence task assignment based on social networks. In: WWW 2013 - Proceedings of the 22nd International Conference on World Wide Web, pp. 367–377 (2013) Google Scholar  Ekman, P., Bellevik, S., Dimitrakakis, C., Tossou, A.: Learning to match. In: 1st International Workshop on Value-Aware and Multistakeholder Recommendation (2017) Google Scholar  Fan, J., Li, G., Ooi, B.C., Tan, K.l., Feng, J.: iCrowd: an adaptive crowdsourcing framework. In: Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, pp. 1015–1030. Association for Computing Machinery (2015) Google Scholar  Horowitz, D., Kamvar, S.D.: The anatomy of a large-scale social search engine. In: Proceedings of the 19th International Conference on World Wide Web - WWW 2010, Raleigh, North Carolina, USA, p. 431. ACM Press (2010) Google Scholar  Huang, Y.M., Lin, Y.T., Cheng, S.C.: An adaptive testing system for supporting versatile educational assessment. Comput. Educ. 52(1), 53–67 (2009) Article  Google Scholar  INEP: Instituto nacional de educação e pesquisas educacionais anísio teixeira - entenda sua nota no enem (2012). http://download.inep.gov.br/educacao_basica/enem/guia_participante/2013/guia_do_participante_notas.pdf. Accessed 19 June 2021 Krstikj, A., Esparza, C.R.M.G., Mora-Vargas, J., Escobar, H.L.: Volunteers in lockdowns: decision support tool for allocation of volunteers during a lockdown. In: Regis-Hernández, F., Mora-Vargas, J., Sánchez-Partida, D., Ruiz, A. (eds.) Humanitarian Logistics from the Disaster Risk Reduction Perspective: Theory and Applications, pp. 429–446. Springer, Cham (2022). https://doi.org/10.1007/978-3-030-90877-5_15 Chapter  Google Scholar  Kuhn, H.W.: The Hungarian method for the assignment problem. Nav. Res. Logist. (NRL) 2(1), 83–97 (1955) Article  MathSciNet  MATH  Google Scholar  Benedetto, L., Cappelli, A., Turrin, R., Cremonesi, P.: R2DE: a NLP approach to estimating IRT parameters of newly generated questions. In: Proceedings of the 10th International Conference on Learning Analytics and Knowledge (2020) Google Scholar  van der Linden, W.J.: Constrained adaptive testing with shadow tests. In: van der Linden, W.J., Glas, G.A. (eds.) Computerized Adaptive Testing: Theory and Practice, New York, Boston, Dordrecht, London, Moscow, pp. 27–52. Kluwer Academic Publishers (2000) Google Scholar  van der Linden, W.J., Jiang, B.: A shadow-test approach to adaptive item calibration. Psychometrika Soc. 85(2), 301–321 (2020) Article  MathSciNet  MATH  Google Scholar  van der Linden, W.J., Veldkamp, B.P.: Constraining item exposure in computerized adaptive testing with shadow tests. J. Educ. Behav. Stat. 29(3), 273–291 (2004) Article  Google Scholar  Liu, C., Gao, X., Wu, F., Chen, G.: QITA: quality inference based task assignment in mobile crowdsensing. In: Pahl, C., Vukovic, M., Yin, J., Yu, Q. (eds.) ICSOC 2018. LNCS, vol. 11236, pp. 363–370. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03596-9_26 Chapter  Google Scholar  Mislevy, R.J.: Bayes modal estimation in item response models. Psychometric 51, 177–195 (1986) Article  MathSciNet  MATH  Google Scholar  Mitchell, S., Kean, A., Mason, A., O’Sullivan, M., Phillips, A., Peschiera, F.: Optimization with pulp (2009). https://coin-or.github.io/pulp/index.html. Accessed 20 June 2021 Munkres, J.: Algorithms for the assignment and transportation problems. J. Soc. Ind. Appl. Math. 5(1), 32–38 (1957) Article  MathSciNet  MATH  Google Scholar  Mwamikazi, E., Fournier-Viger, P., Moghrabi, C., Barhoumi, A., Baudouin, R.: An adaptive questionnaire for automatic identification of learning styles. In: Ali, M., Pan, J.-S., Chen, S.-M., Horng, M.-F. (eds.) IEA/AIE 2014. LNCS (LNAI), vol. 8481, pp. 399–409. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-07455-9_42 Chapter  Google Scholar  Negishi, K., Ito, H., Matsubara, M., Morishima, A.: A skill-based worksharing approach for microtask assignment. In: 2021 IEEE International Conference on Big Data (Big Data), pp. 3544–3547 (2021) Google Scholar  Paschoal, A.F.A., et al.: Pirá: A bilingual portuguese-english dataset for question-answering about the ocean. In: Demartini, G., Zuccon, G., Culpepper, J.S., Huang, Z., Tong, H. (eds.) CIKM 2021: The 30th ACM International Conference on Information and Knowledge Management, Virtual Event, Queensland, Australia, 1–5 November 2021, pp. 4544–4553. ACM (2021). https://doi.org/10.1145/3459637.3482012 Shekhar, G., Bodkhe, S., Fernandes, K.: On-demand intelligent resource assessment and allocation system using NLP for project management. In: AMCIS 2020 Proceedings, vol. 8 (2020) Google Scholar  Tran-Thanh, L., Stein, S., Rogers, A., Jennings, N.: Efficient crowdsourcing of unknown experts using bounded multi-armed bandits. Artif. Intell. 214, 89–111 (2014) Article  MathSciNet  MATH  Google Scholar  Tu, J., Cheng, P., Chen, L.: Quality-assured synchronized task assignment in crowdsourcing. IEEE Trans. Knowl. Data Eng. 33(3), 1156–1168 (2021) Google Scholar  Veldkamp, B.P.: Bayesian item selection in constrained adaptive testing using shadow tests. Psicologica 31(1), 149–169 (2010) Google Scholar  Yu, D., Wang, Y., Zhou, Z.: Software crowdsourcing task allocation algorithm based on dynamic utility. IEEE Access 7, 33094–33106 (2019) Article  Google Scholar  Download references Author information Authors and Affiliations School of Arts, Sciences and Humanities, University of São Paulo, São Paulo, Brazil João da Silva, Sarajane Peres, Daniel Cordeiro & Valdinei Freire Authors João da SilvaView author publications Search author on:PubMed Google Scholar Sarajane PeresView author publications Search author on:PubMed Google Scholar Daniel CordeiroView author publications Search author on:PubMed Google Scholar Valdinei FreireView author publications Search author on:PubMed Google Scholar Corresponding author Correspondence to João da Silva . Editor information Editors and Affiliations Federal University of São Carlos, São Carlos, Brazil Murilo C. Naldi Centro Universitario da FEI, São Bernardo do Campo, Brazil Reinaldo A. C. Bianchi Rights and permissions Reprints and permissions Copyright information © 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG About this paper Cite this paper da Silva, J., Peres, S., Cordeiro, D., Freire, V. (2023). Allocating Dynamic and Finite Resources to a Set of Known Tasks. In: Naldi, M.C., Bianchi, R.A.C. (eds) Intelligent Systems. BRACIS 2023. Lecture Notes in Computer Science(), vol 14195. Springer, Cham. https://doi.org/10.1007/978-3-031-45368-7_13 Download citation .RIS .ENW .BIB DOI: https://doi.org/10.1007/978-3-031-45368-7_13 Published: 12 October 2023 Publisher Name: Springer, Cham Print ISBN: 978-3-031-45367-0 Online ISBN: 978-3-031-45368-7 eBook Packages: Computer ScienceComputer Science (R0) Share this paper Anyone you share the following link with will be able to read this content: Get shareable linkSorry, a shareable link is not currently available for this article. Copy shareable link to clipboard Provided by the Springer Nature SharedIt content-sharing initiative Keywords Dynamic resource allocation Adaptive allocation Shadow test Publish with us Policies and ethics Search Search by keyword or author Search Navigation Find a journal Publish with us Track your research Discover content Journals A-Z Books A-Z Publish with us Journal finder Publish your research Language editing Open access publishing Products and services Our products Librarians Societies Partners and advertisers Our brands Springer Nature Portfolio BMC Palgrave Macmillan Apress Discover Your privacy choices/Manage cookies Your US state privacy rights Accessibility statement Terms and conditions Privacy policy Help and support Legal notice Cancel contracts here 129.74.145.123 Hesburgh Library ER Unit (3005732405) - NorthEast Research Libraries (NERL) (8200828607) - NERL - TA Account (3006206169) - University of Notre Dame Hesburgh Library (3000184373) © 2025 Springer Nature