Proceedings of the 6th International Conference of Combinatorics, Graph Theory, and Network Topology (ICCGANT 2022)

<Previous Article In Volume
Next Article In Volume>

A Note on Grid-Type Directed Acyclic Graph for Important Property of Resource Allocation Problem

Authors
Mochamad Nizar Palefi Ma’ady1, *, Tabina Shafa Nabila Syahda1
1Department of Information System, Institut Teknologi Telkom Surabaya, Surabaya, Indonesia
*Corresponding author. Email: nizar@ittelkom-sby.ac.id
Corresponding Author
Mochamad Nizar Palefi Ma’ady
Available Online 27 April 2023.
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.

Download article (PDF)

<Previous Article In Volume
Next Article In Volume>
Volume Title
Proceedings of the 6th International Conference of Combinatorics, Graph Theory, and Network Topology (ICCGANT 2022)
Series
Advances in Physics Research
Publication Date
27 April 2023
ISBN
10.2991/978-94-6463-138-8_15
ISSN
2352-541X
DOI
10.2991/978-94-6463-138-8_15How to use a DOI?
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

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