关键词: 随机资源分配, 嵌套分区, 序优化, 最优计算量分配

Abstract: To solve the stochastic resource allocation problem effectively, an optimization method based on order under the framework of Nested Partitions (NP) algorithm was proposed. This method combined ordinal optimization and Optimal Computing Budget Allocation (OCBA) technique with NP framework. Ordinal comparison method was used to greatly reduce computation budget. And OCBA technique could improve the convergence rate and reliability of result further by allocating the computing budget intelligently. However, the NP method guaranteed sampling from entire feasible region in each iteration and thereby guaranteed the global convergence of hybrid algorithm. Detailed operation steps were given out and convergent result was proved. Job shop scheduling benchmark problems were used to verify this algorithm and the result of simulation, which was compared to other wellknown algorithms, indicated that this algorithm was better than several other algorithms both in convergence rate and quality of optimization.

Key words: stochastic resource allocation, nested partitions, ordinal optimization, optimal computing budget allocation, Job Shop scheduling