A Clustering-Based Adaptive Hybrid Algorithm for the Stochastic Resource Allocation Problem With Time Windows

The stochastic resource allocation (SRA) problem is widely encountered in complex systems, where the resource may probabilistically fail to complete its assigned task. In practical scenarios, the assignment of resources to tasks should be handled within specified time windows, and the success probability of each assignment changes over time. Such a problem can be represented as the SRA problem with time window (SRA-TW). Both the discrete assignment relationship and the corresponding continuous-valued assignment time are indispensable in the decision scheme of SRA-TW. This mixed-variable nature poses a great challenge for optimization. Based on these requirements, SRA-TW is formulated as a mixed-variable optimization problem (MVOP) with temporal constraints. To solve this problem, an adaptive hybrid algorithm with clustering-based diversity preservation (<roman xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">AHA</roman><sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><roman>CDP</roman></sub>) is proposed. Firstly, a variable-length hybrid encoding method with constructive decoding is proposed for incremental constraint handling. Secondly, a hybrid search mechanism incorporating a matching-similarity-guided adaptive selection method is proposed to balance the search in discrete and continuous subspaces. Then, a clustering-based diversity preservation strategy is developed, facilitating a good distribution of the population. Finally, an SRA-TW instance generator considering various problem features is designed, so as to comprehensively validate the algorithm’s performance. The statistical results over numerous instances demonstrate the superiority of <roman xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">AHA</roman><sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><roman>CDP</roman></sub> over prevailing algorithms in addressing SRA-TW.