On The Heuristic Algorithms For Resource Optimization Problems

Resources are a summarized concept representing all the materials, energy and in-formation that can be used by human. Resource optimization represents the process that the decision-maker allocates the available resources according to corresponding al-location solutions, which can achieve the profit-maximization goal or other pre-made objectives. Resource allocations are the key task in strategic planning. The resource optimization applications widely exist in the following fields:production scheduling, project scheduling, human resource management and cloud resource management etc. There is no uniform resource allocation pattern due to various classifications of re-sources. The main concern of this work lies in finding resource allocation solutions considering resources of the following styles:continuous resources (including water, electricity), discrete resources (including human power, equipments) and QoS resources (including CPU and delay). The scenario for the continuous and discrete resources opti-mization the classical single machine manufacturing environment. For the QoS resource allocation, the scenario is QoS-aware web service composition The main contributions of this paper include:(1)In the first chapter, the transformation relations between continuous resource allo-cation in batch-scheduling environment with bin-packing problem istudied and then the corresponding heuristic algorithms are presented. In the existing researches about continuous resource allocations, few researchers have considered the transformation relations between these resource allocation problems and classical optimization prob-lems. Constructing the transformation relationships between continuous resource allo-cation and other classical problems can not only facilitate the analysis, but also present a way for building solving methods. This work focuses on transforming the continuous resource allocation problem into bin-packing problem. Therefore, some effective ap-proaches for the bin-packing problem can be employed for dealing with the continuous resource allocation problem. Moreover, different continuous resource allocation strate-gies among different jobs in the same batch are investigated. Corresponding to different real-life manufacturing background, the optimal conditions for different strategies are proposed.(2)In this chapter, the application of general resource functions in batch-scheduling with resource allocation problems is studied and then corresponding approximate algorithms are presented. The research is based on the manufacturing background in the first chap-ter. General resource function can accurately reflect the different characteristics of non-identical jobs. According to relevant researches, the conclusions and the approaches for traditional resource functions (e.g., linear or convex-decreasing functions) cannot be employed for the resource allocation processes considering general resource func-tions. Accordingly, to achieve the optimal conditions, marginal analysis on the batch-scheduling with resource allocation problems is employed. Then, according to these conditions, the approximate algorithms for the considered problems are proposed.(3) In this chapter, the discrete resource optimization problem in production scheduling is studied and then an estimation of distribution algorithm is proposed. Different from the above two researches, the discrete resource allocation problem in a single machine manufacturing environment is considered. Since the discrete and continuous resources have different properties, corresponding analysis and solving methods for continuous resource allocating cannot be employed for allocating discrete resources. Since there is no clear evidence whether the introduction of discrete resource allocation can change the complexity of traditional production scheduling problem, the complexity analysis of the considered discrete resource allocation problem is investigated firstly. The com-plexity analysis is based on the observation that the resource allocation problem under investigation can be reduced to a partition problem in polynomial time. Since the par-tition problem is NP-hard, the considered discrete resource allocation problem is also NP-hard. In order to solve the resource allocation problem, an estimation of distri-bution algorithm is proposed, which is based on an approximate Boltzmann distribu-tion.Correspondingly, the probabilistic model and propose the simplified approaches for learning by experiment evidences are presented. The results of experimental studies showed that the proposed algorithm outperform the comparative algorithms in terms of both solution quality.(4) The QoS-aware web service composition considering complementarity relations is studied in this chapter. Unlike continuous and discrete resources, QoS is a summariza-tion concept that contains multiple dimensions of resources, such as CPU and memory. Moreover, some of these QoS resources does not fit for the additivity constraint. There-fore, the methods for allocating continuous and discrete resources cannot be employed for QoS resource allocation. Recently, some researchers showed that complementarity relations exist in real-life system-based systems and considering them can significantly influence the performance of the composite web service. Different from discrete or continuous resources in manufacturing environment, QoS resource contains different dimensions of resources, which may not satisfy the additivity constraint. Our main concern is set on the complementarity relations between the candidate service for ful-filling the functionality of the same abstract service, which is specifically defined as internal complementarity. By presenting the real-life backgrounds, the problem of how internal complementarity can influence the performance of composite web service is investigated. Based on corresponding assumptions, the mathematical formulation is presented. The complexity is two-fold:firstly, the considered problem is proven to be NP-hard by transforming a simplified version into multi-dimensional multiple-choice knapsack problem (MMKP); Then in general cases, it is showed that transforming the considered problem into MMKP may cost exponential time, which indicates that it is not computational practical to solve the problem by the approaches for MMKP. In order to solve the problem, an iteratively improving framework is presented. At each iteration, the solution quality is improved by solving a corresponding disjunctively constrained knapsack problem (DCKP). According to this framework, two heuristic algorithms is re-alized and then it is proved that these heuristics outperform the comparative algorithms in terms of both solution quality and computational time, which in turn demonstrates the effectiveness of the proposed framework.