TY - GEN
T1 - Stochastic Resource Allocation with Time Windows
AU - Li, Yang
AU - Xin, Bin
N1 - Publisher Copyright:
© 2024, The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
PY - 2024
Y1 - 2024
N2 - The stochastic resource allocation problem with time windows (SRAPTW) refers to a class of combinatorial optimization problems which are aimed at finding the optimal scheme of assigning resources to given tasks within their time windows. In SRAPTW, the capability of resources to accomplish tasks is quantitatively characterized by probability. The expected allocation scheme should include not only the task-resource pairings but also their allocation time. This paper formulates SRAPTW as a nonlinear mixed 0–1 programming problem with the objective of maximizing the reward of completing specified tasks. Then, a general encoding/decoding method is proposed for the representation of solutions, and several different problem-solving methodologies are presented and compared. Results of computational experiments show that the utilization of SRAPTW-specific knowledge can bring in excellent performance, and a constructive heuristic combining maximal marginal return strategy and maximal probability strategy has remarkable advantages, especially in larger-scale cases.
AB - The stochastic resource allocation problem with time windows (SRAPTW) refers to a class of combinatorial optimization problems which are aimed at finding the optimal scheme of assigning resources to given tasks within their time windows. In SRAPTW, the capability of resources to accomplish tasks is quantitatively characterized by probability. The expected allocation scheme should include not only the task-resource pairings but also their allocation time. This paper formulates SRAPTW as a nonlinear mixed 0–1 programming problem with the objective of maximizing the reward of completing specified tasks. Then, a general encoding/decoding method is proposed for the representation of solutions, and several different problem-solving methodologies are presented and compared. Results of computational experiments show that the utilization of SRAPTW-specific knowledge can bring in excellent performance, and a constructive heuristic combining maximal marginal return strategy and maximal probability strategy has remarkable advantages, especially in larger-scale cases.
KW - Constructive Heuristic
KW - Stochastic Resource Allocation
KW - Time Windows
UR - http://www.scopus.com/inward/record.url?scp=85176953998&partnerID=8YFLogxK
U2 - 10.1007/978-981-99-7590-7_28
DO - 10.1007/978-981-99-7590-7_28
M3 - Conference contribution
AN - SCOPUS:85176953998
SN - 9789819975891
T3 - Communications in Computer and Information Science
SP - 348
EP - 358
BT - Advanced Computational Intelligence and Intelligent Informatics - 8th International Workshop, IWACIII 2023, Proceedings
A2 - Xin, Bin
A2 - Kubota, Naoyuki
A2 - Chen, Kewei
A2 - Dong, Fangyan
PB - Springer Science and Business Media Deutschland GmbH
T2 - 8th International Workshop on Advanced Computational Intelligence and Intelligent Informatics, IWACIII 2023
Y2 - 3 November 2023 through 5 November 2023
ER -