A Note on Grid-Type Directed Acyclic Graph for Important Property of Resource Allocation Problem
- DOI
- 10.2991/978-94-6463-138-8_15How to use a DOI?
- Keywords
- grid-type directed acyclic graph; resource allocation; dynamic programming; machine order; constrained problem
- Abstract
We consider the following resource allocation problem on a directed acyclic graph (the precedence graph). Suppose we have a given X units of a resource that must be distributed among N activities with some of given return functions ri(x). The problem is to allocate all of the X units of resource to the activities so as to maximize the total return. Specific constraint is added that the total allocation to the designated M machines (M < N) that must be at least Y but at most Z units (Y ≤ Z ≤ X). We present and illustrate the dynamic programming procedure in a grid-type directed acyclic graph by conducting a numerical solution. As the result, we point out the optimal policy is in independent of the order of machines as important property of resource allocation problem. We represent the posed constrained problem in finding a best obstacle-avoiding path.
- Copyright
- © 2023 The Author(s)
- Open Access
- Open Access This chapter is licensed under the terms of the Creative Commons Attribution-NonCommercial 4.0 International License (http://creativecommons.org/licenses/by-nc/4.0/), which permits any noncommercial use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.
Cite this article
TY - CONF AU - Mochamad Nizar Palefi Ma’ady AU - Tabina Shafa Nabila Syahda PY - 2023 DA - 2023/04/27 TI - A Note on Grid-Type Directed Acyclic Graph for Important Property of Resource Allocation Problem BT - Proceedings of the 6th International Conference of Combinatorics, Graph Theory, and Network Topology (ICCGANT 2022) PB - Atlantis Press SP - 170 EP - 176 SN - 2352-541X UR - https://doi.org/10.2991/978-94-6463-138-8_15 DO - 10.2991/978-94-6463-138-8_15 ID - Ma’ady2023 ER -