In this work we perform preliminary identification by formulations of resource-aware problems across various disciplines considered in scientific literature. Formulations considered are: integer linear programming (ILP), greedy algorithms, dynamic programming and genetic algorithms (GA). We outline scientific disciplines (associated with profiles of journals the works appear in) and practical applications. We were able to identify selected more universal resources considered in many problems, such as ifnancial cost, time, energy, ecological value, security, apart from problem specific resources. We also identified to what degree certain resources appear in various problem formulations, as well as which problem formulations are prevalent in various disciplines.
In computer science, resources typically considered include: execution time (performance),
energy, memory/storage, ease of programming/development time. Problem formulations in
these cases are typically associated with trade-ofs, for example: performance vs energy [
Problem domains considered in this analysis include, among others: allocating resources for
ifghting forest fires [ 8], emission minimization, fossil resource usage minimization,
employment maximization [9], allocation of health care resources [10], reconfiguration and resource
optimization in power distribution networks [11], site selection of a wind power plant [12],
operation of a hospital emergency department, studying the impact stafing policies have on
such key quality measures as patient length of stay (LoS), number of handofs, staf utilization
levels, and cost [13], decision-CPM network in order to obtain an overall optimum including
time, cost, quality and safety in a road building project [14], resource allocation in
communication [15, 16], clouds [17, 18], high performance computing systems [
In terms of resources considered in this cross-discipline preliminary review, these can be divided into two groups: problem specific resources – we consider resources specific to the given domain, e.g. water in water research, natural resources in environmental protection, computing resources in cloud computing etc. general resources applicable to many domains and applications, specifically optimization i.e. mainly: time (determined by system/process performance) – execution time, cost – monetary, energy (used within an optimization process), ecological/environmental value (respected by a society which it concerns), security – prevention of a crime, break-in.
Outcome of this analysis allows to further outline problem formulations from the identified works and link analogous synthetic formulations and approaches used to solve the latter from the algorithmic point of view. This potentially allows to reuse approaches to take up problems already used in other disciplines and correspondingly identify base algorithms that form algorithmic foundations for resource-aware computing. 2. Resource-aware problems across disciplines by formulations Works considered in this analysis include selection (scientific papers) out of approximately 100 results returned by the Google search engine for queries involving particular problem formulations and resource, resource-aware problems. The search had been extended by selected results obtained from the Bing search engine, queried about resource aware computing an resource aware computing problems. Classification of these is included in Tables 1,2,3,4, versus: resources: both problem specific as well as more general ones like time, financial cost, security, formulation: ILP, dynamic programming, greedy approach, GA as an example of evolutionary approaches, discipline – a broader category of applications considered in the given work.
Table 1 – continued from previous page problem description resources formulation total electricity cost min- energy resources multiimization, CO2 emission (solar, wind, coal, objective minimization, energy im- natural gas, hydro- mixed port minimization, fossil electric, nuclear integer resource usage minimiza- etc.) linear protion, employment max- gramming imization, social accep- (MOMILP) tance maximization allocation of health care health care re- ILP resources (treatments, sources , financial population, healthcare cost programs) ifnding the minimum power distribution ILP power loss configuration network resources of the network, definition of the most eficient operating condition of voltage control apparatus and reactive power resources site selection of a wind power plant single and multiple-type wind turbine models for a selected site decision-CPM network in order to obtain an overall optimum including time, cost, quality and safety in a road building project operation of a hospital emergency department, studying the impact stafing policies have on such key quality measures as patient length of stay (LoS), number of handofs, staf utilization levels, and cost energy
ILP time; cost; quality; ILP safety staf; time; resources assigned by staf
ILP, simulation hospital resource management
discipline energy sector problem description data assignment for par- time allel processing in a hybrid heterogeneous environment considering communication costs cloudlet selection in computing, stor- ILP the multi-cloudlet en- age and network vironment, selection of resources cloudlet(s), selection of VMs for cloudlets Data-center power-aware data-center re- ILP management, eficient uti- sources, power, lization of available re- time sources scheduling of satellite ob- observation capa- ILP servations bilities of satellites, mission time constraints resource management datacenter provisioning distributed computing power network monitoring computational dynamic propower, bandwidth, gramming responsiveness Edge computing, integra- energy, bandwidth, dynamic protion of low cost wearable processing power, gramming sensors, processing of sen- measurement qualsors’ data at the cloud ity edge Seamless image manipula- still images tion Task scheduling and allocation of resources in distributed systems dynamic programming distributed com- dynamic proputing resources, gramming incl. grids, cloud, supercomputers, cost credits solving resource con- problem specific restrained multi-project sources; time scheduling problem (many projects, time dependencies, constrained resources) solving resource con- problem specific restrained project schedul- sources; time ing problem (RCPSP) construction schedul- problem specific reing/resource scheduling sources; time problem troops-to-tasks problem military resources, genetic algo(generalized RCPSP, addi- time rithm tional constraints) genetic algorithm, transfer times for activities at various locations considered genetic algorithm genetic algorithm, comparison of GA algorithms GA parameter tuning decomposition based GA quantum inspired GA Elitist GA genetic algorithm cross disci- [50] pline applicable problem formulation cross discipline applicable problem formulation
Table 4 – continued from previous page problem description resources formulation grid resource allocation grid resources: genetic algocomputational rithm systems, storage servers, and network servers; time regional drinking water water resources; fi- genetic algosupply nancial cost (pump- rithm ing, purification, transport); ecological/environment value (vs potential damage, groundwater drawdown); energy groundwater manage- water resources; genetic algoment ifnancial cost; en- rithm vironmental value (risk of drawdown); time (pumping rate) surgery scheduling, max- hospital resources; genetic algoimizing the use of operat- time (runtime of al- rithm ing rooms gorithm and indirectly because of resource usage) scheduling problems on resource types: genetic lfexible manufacturing machines (M), stor- algorithm, systems (FMS) age bufers (SB), also other material handling approaches devices (HD), tool- like PSO, changing devices (TD), fixtures (FX) and pallets (PL); time protection of marine envi- cost; time; environ- genetic algoronment and allocation of mental burden rithm response vessels to minimize costs of oil spill at sea discipline bib grid comput- [61] ing [62] [63] water resource research water resource research healthcare sec- [64] tor manufacturing system
[65] environmental [66] protection
virtual network embed- problem specific reding onto underlying sources physical infrastructure
discipline bib cloud comput- [67] ing mobile edge [68] computing
Additionally, during research we have encountered works that consider various formulations. Selected examples of these are shown in Table 5, described in terms of the same features as works in the previous tables. approximate dynamic programming approach to resource management in multi-cloud environments, multi-cloud resource allocation algorithm to manage requests to the cloud with maximization of a cloud broker revenue
Preliminary identification of resource-aware problems by querying of Google and Bing search engines allows us to identify: 1. to what degree certain resources appear in various problem formulations, 2. which problem formulations are prevalent in various disciplines.
Resources typically considered in various domains can be domain specific or more universal, such as time and financial cost. The aforementioned factors can be, based on the aforementioned analysis, summarized as follows. Resources often considered in various problem formulations are shown in Table 6.
Additionally, we can identify common resources used in various applications/disciplines, apart from problem specific resources. The former can be identified as shown in Table 8.
resource
Finalizing this research, we can say that, apart from details shown in the aforementioned tables, we can generalize links between resources and problem formulations, resources and applications as well as applications and formulations among a relatively small number of these entities, which hints that some applications/disciplines can be linked by selected problem formulations. This, however, needs further analysis and identification of concrete variables and formulation mappings between these disciplines. Additionally, we can see that formulations such as dynamic programming and GA appear in research works in general problem formulations that are abstracted from particular applications but can be potentially mapped onto several application areas.
Future work, extending the results presented in this paper, will involve the following: 1. involving other problem formulations such as other evolutionary approaches etc. 2. extending research in-depth by querying scientific databases, including Web of Science,
Scopus and publisher’s like IEEE, Springer, Elsevier etc., 3. identifying other possible papers giving a broader-scope generalized approach to the subject, 4. finding actual links and generalizations between problem formulations that describe particular use cases. Some of the works, as noted above, refer to generalized problem formulations, while others have introduced problem specific constraints and specifics. It is possible to build an inheritance tree of resource-aware problem formulations by prior ifnding core problem descriptions.
This work is partially supported by CERCIRAS COST Action CA19135 funded by COST. [7] K. Karimi, The feasibility of using opencl instead of openmp for parallel cpu programming, 2015. arXiv:1503.06532. [8] J. Rodríguez-Veiga, M. J. Ginzo-Villamayor, B. Casas-Méndez, An integer linear programming model to select and temporally allocate resources for fighting forest fires, Forests 9 (2018). URL: https://www.mdpi.com/1999-4907/9/10/583. doi:10.3390/f9100583. [9] E. Özcan, S. Erol, A multi-objective mixed integer linear programming model for energy resource allocation problem: The case of turkey, Gazi University Journal of Science 27 (2014) 1157 – 1168. [10] D. Epstein, Z. Chalabi, K. Claxton, M. Sculpher, Mathematical programming for the optimal allocation of health care resources, 2005. [11] A. Borghetti, Mixed Integer Linear Programming Models for Network Reconfiguration and Resource Optimization in Power Distribution Networks, John Wiley & Sons, Ltd, ????, pp. 43–88. doi:https://doi.org/10.1002/9781119116080.ch2. [12] E. S. Ari, C. Gencer, Proposal of a novel mixed integer linear programming model for site selection of a wind power plant based on power maximization with use of mixed type wind turbines, Energy & Environment 31 (2020) 825– 841. URL: https://doi.org/10.1177/0958305X19882394. doi:10.1177/0958305X19882394. arXiv:https://doi.org/10.1177/0958305X19882394. [13] S. Y. Shin, Y. Brun, H. Balasubramanian, P. L. Henneman, L. J. Osterweil, Discrete-event simulation and integer linear programming for constraint-aware resource scheduling, IEEE Transactions on Systems, Man, and Cybernetics: Systems 48 (2018) 1578–1593. doi:10.1109/TSMC.2017.2681623. [14] J. R. San Cristóbal Mateo, An integer linear programming model including time, cost, quality, and safety, IEEE Access 7 (2019) 168307–168315. doi:10.1109/ACCESS.2019. 2953185. [15] S. Najeh, H. Besbes, A. Bouallegue, Greedy algorithm for dynamic resource allocation in downlink of ofdma system, in: 2005 2nd International Symposium on Wireless Communication Systems, 2005, pp. 475–479. doi:10.1109/ISWCS.2005.1547746. [16] N. Ferdosian, M. Othman, B. M. Ali, K. Y. Lun, Greedy–knapsack algorithm for optimal downlink resource allocation in lte networks, Wireless Networks 22 (2015) 1427–1440.
URL: http://dx.doi.org/10.1007/s11276-015-1042-9. doi:10.1007/s11276-015-1042-9. [17] M. C. Calzarossa, L. Massari, G. Nebbione, M. L. Della Vedova, D. Tessera, Tuning genetic algorithms for resource provisioning and scheduling in uncertain cloud environments: Challenges and findings, in: 2019 27th Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP), 2019, pp. 174–180. doi:10.1109/EMPDP. 2019.8671564. [18] L. Liu, Q. Fan, Resource allocation optimization based on mixed integer linear programming in the multi-cloudlet environment, IEEE Access 6 (2018) 24533–24542. doi:10.1109/ ACCESS.2018.2830639. [19] T. Boiński, P. Czarnul, Optimization of Data Assignment for Parallel Processing in a Hybrid Heterogeneous Environment Using Integer Linear Programming, The Computer Journal (2021). doi:10.1093/comjnl/bxaa187. [20] J. O. Kennedy, Dynamic programming applications to agriculture and natural resources (1986). URL: https://www.osti.gov/biblio/7151445. [21] A. A. Popov, O. N. Lopateeva, A. K. Ovsyankin, M. M. Satsuk, Application of greedy algorithms for the formation of the educational schedule in the higher education, Journal of Physics: Conference Series 1691 (2020) 012066. URL: https://doi.org/10.1088/1742-6596/ 1691/1/012066. doi:10.1088/1742-6596/1691/1/012066. [22] J. A. S. Araujo, Mixed-Integer Linear Programming Based Approaches for the Resource Constrained Project Scheduling Problem, Ph.D. thesis, Universidade Federal de Ouro Preto, 2019. [23] J. L. B. García, R. G. Mestre, J. T. Viñals, An integer linear programming representation for data-center power-aware management, 2010. [24] S. Shin, Y. Brun, H. Balasubramanian, P. Henneman, L. Osterweil, Discrete-event simulation and integer linear programming for constraint-aware resource scheduling, IEEE Transactions on Systems, Man, and Cybernetics: Systems PP (2017) 1–16. doi:10.1109/ TSMC.2017.2681623. [25] X. Chen, G. Reinelt, G. Dai, A. Spitz, A mixed integer linear programming model for multi-satellite scheduling, 2018. arXiv:1811.12114. [26] S. Bousnina, M. Cesana, J. Ortín, C. Delgado, J. R. Gállego, M. Canales, A greedy approach for resource allocation in virtual sensor networks, in: 2017 Wireless Days, 2017, pp. 15–20. doi:10.1109/WD.2017.7918108. [27] H. Singh, Performance Evaluation of Weighted Greedy Algorithm in Resource Management, Master’s thesis, University of Windsor, Windsor, Ontario, Canada, 2018.
Https://scholar.uwindsor.ca/etd/7397. [28] S. Rampersaud, D. Grosu, A sharing-aware greedy algorithm for virtual machine maximization, in: 2014 IEEE 13th International Symposium on Network Computing and Applications, NCA 2014, Cambridge, MA, USA, 21-23 August, 2014, 2014, pp. 113–120.
URL: https://doi.org/10.1109/NCA.2014.24. doi:10.1109/NCA.2014.24. [29] S. Rampersaud, D. Grosu, An approximation algorithm for sharing-aware virtual machine revenue maximization, IEEE Trans. Serv. Comput. 14 (2021) 1–15. URL: https://doi.org/10. 1109/TSC.2017.2786728. doi:10.1109/TSC.2017.2786728. [30] A resource-aware scheduling algorithm with reduced task duplication on heterogeneous computing systems, J Supercomput 68 (2014) 1347––1377. [31] H. Liao, Z. Zhou, X. Zhao, Y. Wang, Learning-based queue-aware task ofloading and resource allocation for space–air–ground-integrated power iot, IEEE Internet of Things Journal 8 (2021) 5250–5263. doi:10.1109/JIOT.2021.3058236. [32] A. Yin, Y. Guo, D. Tang, Resource-aware fluid scheduling with time constraints for clustered many-core architectures, Journal of Physics: Conference Series 1971 (2021) 012090. URL: https://doi.org/10.1088/1742-6596/1971/1/012090. doi:10.1088/1742-6596/1971/ 1/012090. [33] P. Venuthurumilli, S. Mandapati, An energy and deadline aware scheduling using greedy algorithm for cloud computing, Ingénierie des systèmes d information 24 (2019) 583–590. doi:10.18280/isi.240604. [34] A. Castellano, C. Martínez, P. Monzón, J. A. Bazerque, A. Ferragut, F. Paganini, Quadratic approximate dynamic programming for scheduling water resources: a case study, 2020. arXiv:2010.02122. [35] A. Forootani, R. Iervolino, M. Tipaldi, J. Neilson, Approximate dynamic programming for stochastic resource allocation problems, IEEE/CAA Journal of Automatica Sinica 7 (2020) 975–990. doi:10.1109/JAS.2020.1003231. [36] P. Plamondon, B. Chaib-draa, A. R. Benaskeur, A real-time dynamic programming decomposition approach to resource allocation, in: 2007 Information, Decision and Control, 2007, pp. 308–313. doi:10.1109/IDC.2007.374568. [37] M. Braun, S. Buchwald, M. Mohr, A. Zwinkau, Dynamic X10: Resource-Aware Programming for Higher Eficiency, Technical Report 8, Karlsruhe Institute of Technology, 2014.
URL: http://digbib.ubka.uni-karlsruhe.de/volltexte/1000041061, x10 ’14. [38] L. Moreau, C. Queinnec, Resource aware programming, ACM Trans. Program. Lang. Syst.
27 (2005) 441–476. [39] J. Paul, W. Stechele, M. Kröhnert, T. Asfour, Resource-aware programming for robotic vision, CoRR abs/1405.2908 (2014). URL: http://arxiv.org/abs/1405.2908. arXiv:1405.2908. [40] D. Amiri, A. Anzanpour, I. Azimi, M. Levorato, P. Liljeberg, N. Dutt, A. M. Rahmani, Context-aware sensing via dynamic programming for edge-assisted wearable systems 1 (2020). doi:10.1145/3351286. [41] S. Avidan, A. Shamir, Seam carving for content-aware image resizing, in: ACM Trans.
Graph, SIGGRAPH, 2007, p. 10. [42] R. Gianni M., H. Soon-Wook, Cost-aware dynamic resource allocation in distributed computing infrastructures, International Journal of Contents 2 (2011). URL: http://dx.doi. org/10.5392/IJoC.2011.7.2.001. doi:10.5392/IJoC.2011.7.2.001. [43] G. Ricciardi, S.-W. Hwang, Cost-aware dynamic resource allocation in distributed computing infrastructures, International Journal of Contents 7 (2011) 1–5. doi:10.5392/IJoC. 2011.7.2.001. [44] J. G. D. S. M. Poladian, Vahe; Sousa, Dynamic configuration of resource-aware services.
carnegie mellon university. journal contribution (2018). doi:10.1184/R1/6622013.v1. [45] Z. Liu, Y. Zhou, G. Huang, B. Luo, Risk aversion based inexact stochastic dynamic programming approach for water resources management planning under uncertainty, Sustainability 11 (2019). URL: https://www.mdpi.com/2071-1050/11/24/6926. doi:10.3390/ su11246926. [46] R. Mansouri, H. T. Pudeh, H. A. Yonesi, A. H. Haghiabi, Dynamic programming model for hydraulics and water resources simulating and optimizing water transfer system (a case study in Iran), Journal of Water Supply: Research and Technology-Aqua 66 (2017) 684–700. URL: https://doi.org/10.2166/aqua.2017.110. doi:10.2166/aqua.2017. 110. arXiv:https://iwaponline.com/aqua/article-pdf/66/8/684/223306/ jws0660684.pdf. [47] R. Johansson, C. Mårtenson, R. Suzić, P. Svenson, Stochastic dynamic programming for resource allocation, Technical Report, FOI – Swedish Defence Research Agency FOI-R– 1666–SE, Command and Control Systems, 2005. FOI-R–1666–SE. [48] X. Li, L. Nie, S. Chen, Approximate dynamic programming based data center resource dynamic scheduling for energy optimization, in: 2014 IEEE International Conference on Internet of Things(iThings), and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber, Physical and Social Computing(CPSCom), IEEE Computer Society, Los Alamitos, CA, USA, 2014, pp. 494–501. URL: https://doi.ieeecomputersociety. org/10.1109/iThings.2014.87. doi:10.1109/iThings.2014.87. doi:doi:10.1515/jisys-2015-0089. [62] K. Vink, P. Schot, Multiple-objective optimization of drinking water production strategies using a genetic algorithm, Water Resources Research 38 (2002) 20–1–20–15. URL: https://agupubs.onlinelibrary.wiley.com/doi/abs/ 10.1029/2000WR000034. doi:https://doi.org/10.1029/2000WR000034. arXiv:https://agupubs.onlinelibrary.wiley.com/doi/pdf/10.1029/ 2000WR000034. [63] R. M. Khalaf, W. H. Hassan, Multi-objective groundwater management using genetic algorithms in kerbala desert area, iraq, IOP Conference Series: Materials Science and Engineering 1067 (2021) 012013. URL: https://doi.org/10.1088/1757-899x/1067/1/012013. doi:10.1088/1757-899x/1067/1/012013. [64] G. Rivera, L. Cisneros, P. Sánchez-Solís, N. Rangel-Valdez, J. Rodas-Osollo, Genetic algorithm for scheduling optimization considering heterogeneous containers: A realworld case study, Axioms 9 (2020). URL: https://www.mdpi.com/2075-1680/9/1/27. doi:10.3390/axioms9010027. [65] M. G. Filho, C. F. Barco, R. F. T. Neto, Using genetic algorithms to solve scheduling problems on flexible manufacturing systems (fms): a literature survey, classification and analysis, Flexible Services and Manufacturing Journal 26 (2014) 408–431. [66] K. Łazuga, L. Gucma, Genetic algorithm method for solving the optimal allocation of response resources problem on the example of polish zone of the baltic sea, Journal of KONBiN 38 (2016) 291–310. URL: https://doi.org/10.1515/jok-2016-0028. doi:doi:10. 1515/jok-2016-0028. [67] L. Deng, Y. Li, L. Yao, Y. Jin, J. Gu, Power-aware resource reconfiguration using genetic algorithm in cloud computing, Mob. Inf. Syst. 2016 (2016) 4859862:1–4859862:9. URL: https://doi.org/10.1155/2016/4859862. doi:10.1155/2016/4859862. [68] S. X. Q. H. Kai Peng, Bohai Zhao, Energy- and resource-aware computation ofloading for complex tasks in edge environment (2020). doi:10.1155/2020/9548262. [69] N. N. H. T. N. T. N. Quang-Hung N., Nien P.D., A genetic algorithm for power-aware virtual machine allocation in private cloud (2013). [70] F. Hoseiny, S. Azizi, M. Shojafar, F. Ahmadiazar, R. Tafazolli, Pga: A priority-aware genetic algorithm for task scheduling in heterogeneous fog-cloud computing, in: IEEE INFOCOM 2021 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), 2021, pp. 1–6. doi:10.1109/INFOCOMWKSHPS51825.2021.9484436. [71] Z. Zhou, X. Chang, Y. Yang, L. Li, Resource-aware virtual network parallel embedding based on genetic algorithm, 2016 17th International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT) (2016) 81–86. [72] P. Czarnul, Comparison of selected algorithms for scheduling workflow applications with dynamically changing service availability, J. Zhejiang Univ. Sci. C 15 (2014) 401–422. URL: https://doi.org/10.1631/jzus.C1300270. doi:10.1631/jzus.C1300270. [73] A. Krzywaniak, P. Czarnul, J. Proficz, Extended investigation of performance-energy trade-ofs under power capping in hpc environments, in: 2019 International Conference on High Performance Computing Simulation (HPCS), 2019, pp. 440–447. doi:10.1109/ HPCS48598.2019.9188149. [74] A. Krzywaniak, P. Czarnul, Performance/energy aware optimization of parallel applications