资源优化的启发式算法研究

发布时间：2018-03-17 15:35

本文选题：资源优化　切入点：连续资源　出处：《中国科学技术大学》2016年博士论文　论文类型：学位论文

【摘要】：资源是一种自然存在物或能够给人类带来财富的物质、能量和信息的总称。资源优化是指决策者按相应的分配方案,对系统所属资源进行具体分配,从而满足系统收益最大化或其他既定目标。提高资源利用效率,优化资源配置已经成为相关学术研究中重点关注的问题。作为战略规划的核心任务,资源优化广泛存在于生产系统调度,项目调度,人力资源管理和云计算资源调度等系统中。资源的众多存在形式使资源优化不存在统一的模式。本文主要研究了启发式算法在不同类型资源优化问题的应用和求解方法,包括连续生产资源(如水,电力等),离散资源(如人力,设备等)和QoS资源(如CPU占用,延迟时间等)。本文的主要贡献包括：(1)研究了单机批调度连续资源优化问题与装箱问题之间的转化关系并提出相应的启发式算法。寻找资源优化问题和其他优化问题之间的转化关系不仅能为问题分析提供依据,而且能使用对应的求解算法进行资源优化。因此资源优化问题与其他优化问题的转化关系亟待研究。我们关注如何将批生产调度中的连续资源优化问题转化为装箱问题,从而利用装箱问题的相关算法求解该资源优化问题。(2)研究了一般资源函数在批调度连续资源优化问题上的应用并提出了相应的近似求解算法。结合上一部分研究工作中批调度连续资源优化背景,我们进一步研究了考虑一般资源函数的单机批调度连续资源优化问题。一般资源函数能够准确反应批调度环境下不同工件的差异性特征。相关研究指出,传统资源函数(如线性和凸递减资源函数)的相关结论和算法不能用于求解考虑一般资源函数的资源优化问题。我们采用边际分析方法分析了考虑一般资源函数的批调度资源优化问题的最优化条件,并以此提出了相应的启发式算法。(3)研究了考虑工件截止时间的离散资源优化问题的复杂度并提出了一个分布估计算法。与上述研究工作不同,我们考虑了单机生产加工的离散资源优化问题。由于离散资源和连续资源物理性质不同,上述相关资源优化方法和结论不能应用于此类问题。根据相关文献研究,将离散资源分配引入传统调度问题可能会改变问题的复杂度。因此,我们首先通过将离散资源优化问题转化为二划分问题论证了该离散资源优化问题的复杂度。由于二划分问题是NP-难问题,并且该转化过程可以在多项式时间内完成,因此该离散资源优化问题也是NP-难问题。为了求解该问题,我们基于一个近似的玻尔兹曼分布提出一个分布估计算法。我们提出了该分布的概率模型,并通过实验论证提供了学习该概率模型的简化方法。实验论证显示该分布估计算法在离散资源优化性能方面优于对比算法。(4)研究了QoS资源互补性的web服务组合问题并提出一个启发式求解框架。QoS资源优化问题存在于web服务组合应用中。不同于连续资源和离散资源,QoS资源是一个集合的概念并且部分QoS属性不具有可加性性质,因此本章研究问题不能采用求解离散资源和连续资源优化算法进行求解。近年来,有研究者指出在web服务组合问题中候选服务的QoS资源具有互补性,并且该互补性会显著影响web服务组合的解的质量。我们的研究主要关注实现相同功能的不同候选服务之间的互补性,并定义其为内部互补性。我们从现实实际背景出发,分析了QoS内部互补性如何影响候选服务和整个web服务组合解。进而,我们根据相应的假设提出了该问题的数学模型并分析了该问题的复杂度：首先,我们通过将该QoS资源优化问题的一个特例转化为多维多选择背包问题论证了该问题是NP-难问题：其次,我们证明了在一般情况下将该问题转化为多维多选择背包问题可能需要指数级时间,从而说明不能通过与背包问题的转化求解考虑QoS内部互补性的web服务组合问题。我们提出一个迭代式的求解框架。在每一次迭代中,该服务组合解的性能是通过求解一个分离背包问题实现的。根据该框架,我们提出两个启发式算法,并且在实验论证中说明它们在时间性能和求解精度要优于相应对比算法。上述实验进一步也说明了本文提出的迭代式求解框架的有效性。
[Abstract]:Resource is a kind of natural existence or to bring the wealth of material, energy and information in general. Resource optimization refers to the decision makers of distribution according to the corresponding scheme, the system resources of the genus specific distribution, so as to meet the maximum system profit or other goals. To improve resource utilization efficiency, optimize the allocation of resources has become focus on the relevant academic research problems. As the core task of strategic planning, resource optimization widely exists in the production system scheduling, project scheduling, human resources management and cloud computing resource scheduling system. Many forms of resources so that resources optimization does not exist a unified model. This paper mainly studies the application of heuristic algorithm in solving and methods of different types of resource optimization problems, including the continuous production of resources (such as water, electricity, etc.) discrete resource (such as manpower, equipment and other resources (such as QoS) and CPU With the delay time, etc.). The main contributions of this thesis include: (1) study the transformation relation between the single batch scheduling problem of resource optimization and continuous packing problem and put forward the corresponding heuristic algorithm. The transformation to find the relationship between resource optimization and other optimization problems can not only provide the basis for the algorithm to solve the problem analysis, but also can use the corresponding resource optimization. To study into the relationship between so resources optimization problem with other optimization problems. We focus on how to batch production scheduling of continuous resource optimization problem is transformed into solving packing problem, thus using correlation algorithm packing problem problem of the resource optimization. (2) studied the general resources function in continuous batch scheduling of resources optimization of application problems and put forward the corresponding approximate algorithm. Combined with a part of the research work in continuous batch scheduling optimization of resource background, I have Further study of the general resources function of single batch scheduling continuous resource optimization problem is considered. The general resource function can accurately reflect the batch scheduling environment of different workpiece characteristics. The study pointed out that the traditional resource function (such as linear and convex decreasing resource function) the relevant conclusions and algorithms cannot be used to solve optimization problems with general resource resources function. We use the marginal analysis method considering the general resources function of the batch scheduling problem of resource optimization optimization conditions, and puts forward the corresponding heuristic algorithm. (3) considering the workpiece as discrete resource optimization problem of time complexity and proposes an estimation of distribution algorithm. The research work with different, we consider the discrete optimization problem of single resource production and processing. Because of the discrete and continuous resources resources of different physical properties, the phase Resources optimization method and the conclusion can not be applied to such problems. According to the relevant literature, the complexity of the discrete resource allocation into the traditional scheduling problem may change the problem. Therefore, we first through the discrete resource optimization problem into the complexity of the two partition problem demonstrates the discrete resource optimization problems. As a result of the two partition problem is NP- hard problem, and the transformation process can be done in polynomial time, so the discrete resource optimization problem is NP- hard. In order to solve this problem, we propose an approximation of the Boltzmann distribution is a distribution estimation algorithm based on probability. We propose a model of the distribution, and provides a simplified method for learning the probability model through the experiments. Experiments show that the estimation of distribution algorithm in discrete resource optimization superior to other compared algorithms. (4) study of the QoS resource The complementary problem of web service composition and proposes a heuristic framework.QoS resource optimization problems in Web service composition application. Different from the continuous and discrete resource resources, QoS resources is a collection of concepts and part of the QoS attribute is not additive in nature, and therefore can not be solved by this chapter studies the problem of discrete resources and continuous resource optimization algorithm to solve this problem. In recent years, some researchers have pointed out the problem of web service composition QoS candidate services are complementary, and the complementary solutions will significantly affect the quality of web service composition. We mainly focus on the complementarity between different candidate services to achieve the same function, and its definition for the internal complementary. We start from the reality background, analyzes how to influence the candidate services and the entire web service combination solution of internal complementary QoS. Furthermore, we according to the corresponding The hypothesis put forward the mathematical model of the problem and the analysis of the complexity of the problem: first, we will through the QoS resource optimization problem into a special case of the multidimensional multiple-choice knapsack problem demonstrates that this problem is NP- hard problem. Secondly, we show that in general the problem is transformed into a multi-dimensional a knapsack problem may require exponential time, which indicates that QoS can not consider internal complementarity problem of web service composition through the transformation and solving knapsack problem. We propose an iterative solving framework. In each iteration, the performance of the service composition solution is achieved by solving a separate knapsack problem according to this framework, we propose two heuristic algorithms, and that they should be better than the corresponding comparison algorithm in time performance and accuracy in experiments. The experiment also shows that further The validity of the iterative solution framework proposed in this paper is proposed.

【学位授予单位】：中国科学技术大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：TP393.09;TP301.6

【相似文献】