Energy constrained resource allocation optimization for mobile grids

A mobile grid incorporates mobile devices into Grid systems. But mobile devices at present have severe limitations in terms of processing, memory capabilities and energy. Minimizing the energy usage in mobile devices poses significant challenges in mobile grids. This paper presents energy constrained resource allocation optimization for mobile grids. The goal of the paper is not only to reduce energy consumption, but also to improve the application utility in a mobile grid environment with a limited energy charge, ensuring battery lifetime and the deadlines of the grid applications. The application utility not only depends on its allocated resources including computation and communication resources, but also on the consumed energy, this leads to a coupled utility model, where the utilities are functions of allocated resources and consumed energy. Energy constrained resources allocation optimization is formulated as a utility optimization problem, which can be decomposed into two subproblems, the interaction between the two sub-problems is controlled through the use of a pricing variable. The paper proposes a price-based distributed energy constrained resources allocation optimization algorithm. In the simulation, the performance evaluation of our energy constrained resources allocation optimization algorithm is conducted.     

Predefined-time distributed multiobjective optimization for network resource allocation

We consider the multiobjective optimization problem for the resource allocation of the multiagent network, where each agent contains multiple conflicting local objective functions. The goal is to find compromise solutions minimizing all local objective functions subject to resource constraints as much as possible, i.e., the Pareto optimums. To this end, we first reformulate the multiobjective optimization problem into one single-objective distributed optimization problem by using the weighted L<...     

网络功能虚拟化资源配置及优化研究综述

网络功能虚拟化(network functions virtualization,NFV)利用虚拟化技术将网络功能从专用硬件中分离形成虚拟网络功能,然后把虚拟网络功能映射到通用服务器、交换机或者存储器中,能有效地降低网络投资成本和运营成本,并提高网络服务部署的灵活性。网络功能虚拟化资源配置是实施NFV需要解决的一个关键问题。为深入剖析网络功能虚拟化资源配置,介绍了NFV的体系结构,重点阐述了资源配置的三个阶段及资源配置的优化,最后对高效资源配置面临的挑战和有价值的研究方向进行了思考,为NFV的研究提供参考。     

Ordinal optimization approach to rare event probability problems

In this paper we introduce a new approach to rare event simulation. Because of the extensive simulation required for precise estimation of performance criterion dependent on rare event occurrences, obstacles such as computing budget/time constraints and pseudo-random number generator limitations can become prohibitive, particularly if comparative study of different system designs is involved. Existing methods for rare events simulation have focused on simulation budget reduction while attempting to generate accurate performance estimates. In this paper we propose a new approach for rare events system analysis in which we relax the simulation goal to the isolation of a set of good enough designs with high probability. Given this relaxation, referred to as ordinal optimization and advanced by Ho et al. (1992), this paper's approach calls instead for the consideration of an appropriate surrogate design problem This surrogate problem is characterized by its approximate ordinal equivalence to the original problem and its performance criterion's dependence not on rare event occurrences, but on more frequent events. Evaluation of such a surrogate problem under the relaxed goals of ordinal optimization has experimentally resulted in orders of magnitude reduction in simulation burden.     

Stochastic resource allocation using a predictor-based heuristic for optimization via simulation

Some combinatorial stochastic resource allocation problems lack algebraically defined objective functions and hence require optimization via simulation as a mechanism for obtaining good solutions. For this class of problems, we propose a new predictor-based heuristic that uses a distance criterion to perform the solution search. To demonstrate our solution approach, we apply this heuristic to the problem of selecting the proper design configuration of an unmanned aerial system (UAS) fleet so as to maximize mission effectiveness. We compare our approach to black box optimization via simulation approaches (two tabu search-based procedures and a greedy heuristic) and glean both methodological and practical insights.     

Multi-criteria human resource allocation for solving multistage combinatorial optimization problems using multiobjective hybrid genetic algorithm

Multi-criteria human resource allocation involves deciding how to divide human resource of limited availability among multiple demands in a way that optimizes current objectives. In this paper, we focus on multi-criteria human resource allocation for solving multistage combinatorial optimization problem. Hence we tackle this problem via a multistage decision-making model. A multistage decision-making model is similar to a complex problem solving, in which a suitable sequence of decisions is to be found. The task can be interpreted as a series of interactions between a decision maker and an outside world, at each stage of which some decisions are available and their immediate effect can be easily computed. Eventually, goals would be reached due to the found of optimized variables. In order to obtain a set of Pareto solutions efficiently, we propose a multiobjective hybrid genetic algorithm (mohGA) approach based on the multistage decision-making model for solving combinatorial optimization problems. According to the proposed method, we apply the mohGA to seek feasible solutions for all stages. The effectiveness of the proposed algorithm was validated by its application to an illustrative example dealing with multiobjective resource allocation problem.     

Radio resource allocation problems for OFDMA cellular systems

Orthogonal frequency division multiple-access (OFDMA) manages to efficiently exploit the inherent multi-user diversity of a cellular system by performing dynamic resource allocation. Radio resource allocation is the technique that assigns to each user in the system a subset of the available radio resources (mainly power and bandwidth) according to a certain optimality criterion on the basis of the experienced link quality. In this paper we address the problem of resource allocation in the downlink of a multi-cellular OFDMA system. The allocation problem is formulated with the goal of minimizing the transmitted power subject to individual rate constraint for each user. Exact and heuristic algorithms are proposed for the both the single-cell and the multi-cell scenario. In particular, we show that in the single-cell scenario the allocation problem can be efficiently solved following a network flow approach. In the multi-cell scenario we assume that all cells use the same frequencies and therefore the allocation problem is complicated by the presence of strong multiple access interference. We prove that the problem is strongly NP-hard, and we present an exact approach based on an MILP formulation. We also propose two heuristic algorithms designed to be simple and fast. All algorithms are tested and evaluated through an experimental campaign on simulated instances. Experimental results show that, although suboptimal, a Lagrangian-based heuristic consisting in solving a series of minimum network cost flow problems is attractive for practical implementation, both for the quality of the solutions and for the small computational times.     

面向资源分配问题的Q-CF多智能体强化学习

多智能体强化学习算法在用于复杂的分布式系统时存在着状态空间大、学习效率低等问题.针对网络环境中的资源分配问题对多智能体强化学习算法进行了研究,将Q-学习算法和链式反馈(chain feedback,CF)学习算法相结合,提出了Q-CF多智能体强化学习算法,利用一种称为信息链式反馈的机制实现了多智能体之间的高效协同.仿真...     

Variable neighborhood search for multi-objective resource allocation problems

The Resource Allocation Problem (RAP) is a classical problem in the field of operations management that has been broadly applied to real problems such as product allocation, project budgeting, resource distribution, and weapon-target assignment. In addition to focusing on a single objective, the RAP may seek to simultaneously optimize several expected but conflicting goals under conditions of resources scarcity. Thus, the single-objective RAP can be intuitively extended to become a Multi-Objective Resource Allocation Problem (MORAP) that also falls in the category of NP-Hard. Due to the complexity of the problem, metaheuristics have been proposed as a practical alternative in the selection of techniques for finding a solution. This study uses Variable Neighborhood Search (VNS) algorithms, one of the extensively used metaheuristic approaches, to solve the MORAP with two important but conflicting objectives—minimization of cost and maximization of efficiency. VNS searches the solution space by systematically changing the neighborhoods. Therefore, proper design of neighborhood structures, base solution selection strategy, and perturbation operators are used to help build a well-balanced set of non-dominated solutions. Two test instances from the literature are used to compare the performance of the competing algorithms including a hybrid genetic algorithm and an ant colony optimization algorithm. Moreover, two large instances are generated to further verify the performance of the proposed VNS algorithms. The approximated Pareto front obtained from the competing algorithms is compared with a reference Pareto front by the exhaustive search method. Three measures are considered to evaluate algorithm performance: D1_R, the Accuracy Ratio, and the number of non-dominated solutions. The results demonstrate the practicability and promise of VNS for solving multi-objective resource allocation problems.     

Non deterministic polynomial optimization problems and their approximations

A unified and general framework for the study of nondeterministic polynomial optimization problems (NPOP) is presented and some properties of NPOP's are investigated. A characterization of NPOP's with regard to their approximability properties is given by proving necessary and sufficient conditions for two approximability schemes. Known approximability results are shown to fit within the general frame developed in the paper. Finally NPOP's are classified and studied with regard to the possibility or impossibility of ‘reducing’ certain types of NPOP's to other types in a sense specified in the text.     

RAPS: a rule-based language for specifying resource allocation andtime-tabling problems

A general language for specifying resource allocation and time-tabling problems is presented. The language is based on an expert system paradigm that was developed previously by the authors and that enables the solution of resource allocation problems by using experts' knowledge and heuristics. The language enables the specification of a problem in terms of resources, activities, allocation rules, and constraints, and thus provides a convenient knowledge acquisition tool. The language syntax is powerful and allows the specification of rules and constraints that are very difficult to formulate with traditional approaches, and it also supports the specification of various control and backtracking strategies. We constructed a generalized inference engine that runs compiled resource allocation problem specification language (RAPS) programs and provides all necessary control structures. This engine acts as an expert system shell and is called expert system for resource allocation (ESRA). The performance of RAPS combined with ESRA is demonstrated by analyzing its solution of a typical resource allocation problem     

Solving a dynamic resource allocation problem through continuous optimization

A class of dynamic resource allocation problems with infinite planning horizon are studied. We observe special structures in the dynamic programming formulation of the problem, which enable us to convert it to continuous optimization problems that can be more easily solved. Structural properties of the problems are discussed, and explicit solutions are given for some special cases.     

求解一类随机优化问题的社会认知算法

提出了解随机优化问题的社会认知算法.该算法易于理解及程序易实现,克服了随机优化问题难以高效实现全局优化的缺点,为随机优化问题的求解提供了一种新的途径,并为社会认知算法的应用拓展了新的空间.     

Reliability-based and deterministic design optimization of a FSAE brake pedal: a risk allocation analysis

While probabilistic designs can translate into significant weight savings through better risk allocation, deterministic design optimization remains widely used in industry. To promote the use of probabilistic designs among engineering students and practitioners, this work solves reliability based design optimization (RBDO) and deterministic design optimization (DDO) models of a FSAE brake pedal with multiple failure modes (stress and buckling) with their relative performance evaluated through a risk allocation analysis. The problems of interest were systematically solved through the following steps: i) topology optimization to specify the brake-pedal shape, ii) numerical 3D brake-pedal modeling under uncertainty for stress and buckling analysis, iii) mass (M), maximum von Mises stress (S_max) and buckling load factor (f_buck) surrogate modeling, iv) global sensitivity analysis and surrogate model selection, and v) surrogate-based RBDO and DDO with risk allocation analysis. Results show that when compared to DDO with alternative safety factors, for the same probability of system failure, the RBDO brake pedal designs were significantly lighter and more robust (less mass variability).     

On a class of optimization problems for framed structures

A unified treatment is presented for four types of problems on limit analysis of framed structures and related design problems. With the use of the lower bound theorem in plasticity these problems are formulated as standard linear programming problems. Two significant improvements are made. The new formulation of the design problems reduces the number of equations in the resulting linear program. An improved simplex algorithm for large and sparse linear programs is employed. The formulational and algorithmic improvements provide large capacity and high efficiency that are indispensable for computational analysis and design of large and complex structures.     

一类非凸优化问题的遗传算法

线性二层规划是一类特殊的非凸优化问题,为了有效求解该问题,提出了一种基于单纯形方法的遗传算法。首先基于下层约束给出了一种新的编码方法;其次利用单纯形表的信息得到了下层问题的解函数,并结合最优性条件给出了适应度函数;最后基于个体编码的特点,设计了新的遗传算子。数值结果表明,所提出的算法是可行有效的。     

A population game approach for dynamic resource allocation problems

We consider a water distribution system as an example of resource allocation, and investigate the use of a population game for its control. We use a game-theoretic approach based on two evolutionary dynamics, the Brown–von Neumann–Nash and the Smith dynamics. We show that the closed-loop feedback interconnection of the water distribution system and the game-theoretic-based controller has a Nash equilibrium as an asymptotically stable equilibrium point. The stability analysis is performed based on passivity concepts and the Lyapunov stability theorem. An additional control subsystem is considered for disturbance rejection. We verify the effectiveness of the method by simulations under different scenarios.     

A parallel hypercube algorithm for discrete resource allocation problems

It has been suggested that parallel processing helps in the solution of difficult discrete optimization problems, in particular, those problems that exhibit combinatorial search and require large-scale computations. By using a number of processors that are connected, coordinated and operating simultaneously, the solutions to such problems can be obtained much more quickly. The purpose of this paper is to propose an efficient parallel hypercube algorithm for the discrete resource allocation problem (DRAP). A sequential divide-and-conquer algorithm is first proposed. The algorithm is then modified for a parallel hypercube machine by exploiting its inherent parallelism. To allocate N units of discrete resources to n agents using a d-dimensional hypercube of p=2/sup d/ nodes, this parallel algorithm solves the DRAP in O((n/p+log/sub 2/p)N/sup 2/) time. A simulation study is conducted on a 32-node nCUBE/2 hypercube computer to present the experimental results. The speedup factor of the parallel hypercube algorithm is found to be more significant when the number of agents in the DRAP is much greater than the number of processing nodes on the hypercube. Some issues related to load balancing, routing, scalability, and mappings of the parallel hypercube algorithm are also discussed.     

Assessment of a non-adaptive deterministic global optimization algorithm for problems with low-dimensional non-convex subspaces

The optimum and at least one optimizing point for convex nonlinear programs can be approximated well by the solution to a linear program (a fact long used in branch and bound algorithms). In more general problems, we can identify subspaces of ‘non-convex variables’ such that, if these variables have sufficiently small ranges, the optimum and at least one optimizing point can be approximated well by the solution of a single linear program. If these subspaces are low-dimensional, this suggests subdividing the variables in the subspace a priori, then producing and solving a fixed, known number of linear programs to obtain an approximation to the solution. The total amount of computation is much more predictable than that required to complete a branch and bound algorithm, and the scheme is ‘embarrassingly parallel’, with little need for either communication or load balancing. We compare such a non-adaptive scheme experimentally to our GlobSol branch and bound implementation, on those problems from the COCONUT project Lib1 test set with non-convex subspaces of dimension four or less, and we discuss potential alterations to both the non-adaptive scheme and our branch and bound process that might change the scope of applicability.     

Safe states in Banker-like resource allocation problems

This paper is concerned with methods of describing the set of safe states in the Banker's Problem. Using a Petri net model, formulas for this set (SAFE) and for its subset of minimal elements (MIN) are derived. Moreover, by partitioning MIN into subclasses such that elements of the same subclass differ only by a permutation of their components, an even smaller representation is given by a set SORT. Lower and upper bounds for the size of SORT are calculated. Since we give an algorithm which computes SORT in time linear to its size, these bounds are also applicable to the time complexity of computing SORT. Finally, some of the results are extended to the multidimensional Banker's Problem with different currencies, whereas other properties are shown to be not extendible to this case.