Optimization Model for Multiple Backup Resource Allocation With Workload-Dependent Failure Probability
Optimization Model for Multiple Backup Resource Allocation With Workload-Dependent Failure Probability
复制标题
具有工作负载相关故障概率的多备份资源分配优化模型
DOI：
10.1109/tnsm.2021.3079937
复制
发表时间：
2021
影响因子：
5.3
通讯作者：
Oki Eiji
中科院分区：
文献类型：
--
作者：
Zhu Mengfei;He Fujun;Oki Eiji
本文提出了一种具有与工作负载相关的故障概率的多备份资源分配模型，以在保护优先策略下最小化最大预期不可用时间（MEUT）。与工作负载相关的故障概率是一个非递减函数，它揭示了工作负载与故障概率之间的关系。所提出的模型采用热备份和冷备份策略来提供保护。为了保护具有多个备份资源的每个功能，需要采用合适的优先级策略来确定预期不可用时间。分析了该模型中多备份资源保护优先策略的优越性；我们提供的定理阐明了政策对 MEUT 的影响。我们将优化问题表述为混合整数线性规划 (MILP) 问题。我们在所提出的模型中提供了最佳目标值的下限。我们证明所提出的模型中多资源分配问题的决策版本是 NP 完全的。受注水算法启发，开发了一种启发式算法，提供了该算法获得的预期不可用时间的上限。数值结果表明，与基线相比，所提出的模型减少了 MEUT。与其他优先级策略相比，所提出的模型中采用的优先级策略抑制了 MEUT。开发的启发式算法比 MILP 方法快约 106 倍，但 MEUT 上的性能损失为 10-4。
This paper proposes a multiple backup resource allocation model with a workload-dependent failure probability to minimize the maximum expected unavailable time (MEUT) under a protection priority policy. The workload-dependent failure probability is a non-decreasing function which reveals the relationship between the workload and the failure probability. The proposed model adopts hot backup and cold backup strategies to provide protection. For protection of each function with multiple backup resources, it is required to adopt a suitable priority policy to determine the expected unavailable time. We analyze the superiority of the protection priority policy for multiple backup resources in the proposed model; we provide the theorems that clarify the influence of policies on MEUT. We formulate the optimization problem as a mixed integer linear programming (MILP) problem. We provide a lower bound of the optimal objective value in the proposed model. We prove that the decision version of the multiple resource allocation problem in the proposed model is NP-complete. A heuristic algorithm inspired by the water-filling algorithm is developed with providing an upper bound of the expected unavailable time obtained by the algorithm. The numerical results show that the proposed model reduces MEUT compared to baselines. The priority policy adopted in the proposed model suppresses MEUT compared with other priority policies. The developed heuristic algorithm is approximately 106times faster than the MILP approach with 10-4performance penalty on MEUT.