Allocating Dynamic and Finite Resources to a Set of Known Tasks | SpringerLink
Skip to main content

Allocating Dynamic and Finite Resources to a Set of Known Tasks

  • Conference paper
  • First Online:
Intelligent Systems (BRACIS 2023)

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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 8464
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 10581
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

References

  1. 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

  2. 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 

  3. 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 

  4. 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 

  5. 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 

  6. 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 

  7. 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 

  8. 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 

  9. Ekman, P., Bellevik, S., Dimitrakakis, C., Tossou, A.: Learning to match. In: 1st International Workshop on Value-Aware and Multistakeholder Recommendation (2017)

    Google Scholar 

  10. 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 

  11. 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 

  12. 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 

  13. 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

  14. 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 

  15. Kuhn, H.W.: The Hungarian method for the assignment problem. Nav. Res. Logist. (NRL) 2(1), 83–97 (1955)

    Article  MathSciNet  MATH  Google Scholar 

  16. 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 

  17. 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 

  18. 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 

  19. 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 

  20. 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 

  21. Mislevy, R.J.: Bayes modal estimation in item response models. Psychometric 51, 177–195 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  22. 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

  23. Munkres, J.: Algorithms for the assignment and transportation problems. J. Soc. Ind. Appl. Math. 5(1), 32–38 (1957)

    Article  MathSciNet  MATH  Google Scholar 

  24. 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 

  25. 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 

  26. 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

  27. 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 

  28. 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 

  29. 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 

  30. Veldkamp, B.P.: Bayesian item selection in constrained adaptive testing using shadow tests. Psicologica 31(1), 149–169 (2010)

    Google Scholar 

  31. 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

Authors

Corresponding author

Correspondence to João da Silva .

Editor information

Editors and Affiliations

Rights and permissions

Reprints and permissions

Copyright information

© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

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

  • DOI: https://doi.org/10.1007/978-3-031-45368-7_13

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-45367-0

  • Online ISBN: 978-3-031-45368-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics