We study the problem of resilient service provisioning for edge computing (RSPE), i.e., how to determine a service placement strategy to maximize the expected overall utility by service provisioning, in the presence of uncertain service failures. RSPE is extremely challenging to tackle, because the explicit expression of its objective function is difficult to obtain, and it is a resilient max–min problem subject to knapsack constraints, which is unexplored so far and cannot be addressed by existing resilient optimization techniques. We first explore the potential properties of the implicit objective function, and reveal that it is monotone submodular under certain conditions. We further prove that the knapsack constraints form a$q$-independence system constraint, where$q>0$is a constant related to the constraints. We propose two novel solutions for the general RSPE and homogeneous case, respectively. First, for the general problem, we propose a “two-step greedy” algorithm achieving a constant approximation ratio within polynomial time. Second, for the homogeneous case where one of the knapsack constraints reduces to a matroid constraint, we propose an improved “first-greedy-then-local search” polynomial time algorithm achieving better approximation ratio than the previous one. Both extensive simulations and field experiments validate the effectiveness of our proposed algorithms.

In recent years, many intelligent optimization algorithms have been applied to the class integration and test order (CITO) problem. These algorithms also have been proved to be able to efficiently solve the problem. Here, the design of fitness function is a key task to generate the optimal solution. To better solve the class integration and test order problem, we propose a new fitness function to generate the optimal solution that achieves a balanced compromise between the different measures (objectives) such as the total number of stubs and the total stubbing complexity in this paper. We used some programs to compare and evaluate the different approaches. The experimental results show that our proposed approach is encouraging to some extent in solving the class integration and test order problem.

In this paper, we study the problem ofRobust offloading schEduling for mobIle edge computiNg (REIN), i.e., in the presence of uncertain offloading failures, how to determine an offloading schedule to minimize the overall latency of all computation-intensive tasks. We mathematically formulate the problem in the form of min-max robust optimization, based on the twice equivalent transformations of the scheduling problem that originally does not consider robustness. REIN is challenging to solve because the min-max robust objective is computationally intractable with existing approaches, and the monotonicity of the objective function is uncertain, even if we transform the objective into the popular max-min form by introducing an appropriate constant upper bound. To solve the above challenges, we first construct a constant upper bound and a monotone modular function to approximate the transformed max-min objective function, and then propose a computationally feasible solution with provable performance bound. Moreover, given the fact of the weak computation ability of users in practical, we construct a tighter constant upper bound and a monotone submodular approximation function, and propose a feasible solution with possibly improved performance bound. Extensive results show that, given a maximum number of offloading failures, our proposed algorithms outperform three benchmark algorithms, and approach the optimum at small time costs.

In this work, we study the problem of Robust Server Placement (RSP) for edge computing, i.e., in the presence of uncertain edge server failures, how to determine a server placement strategy to maximize the expected overall workload that can be served by edge servers. We mathematically formulate the RSP problem in the form of robust max-min optimization, derived from two consequentially equivalent transformations of the problem that does not consider robustness and followed by a robust conversion. RSP is challenging to solve, because the explicit expression of the objective function in RSP is hard to obtain, and RSP is a robust max-min problem with a matroid constraint and a knapsack constraint, which is still an unexplored problem in the literature. To address the above challenges, we first investigate the special properties of the problem, and reveal that the objective function is monotone submodular. We then prove that the involved constraints form a p-independence system constraint, where p is a constant value related to the ratio of the coefficients in the knapsack constraint. Finally, we propose an algorithm that achieves a provable constant approximation ratio in polynomial time. Both synthetic and trace-driven simulation results show that, given any maximum number of server failures, our proposed algorithm outperforms three state-of-the-art algorithms and approaches the optimal solution, which applies exhaustive exponential searches.