本文選題：資源優(yōu)化　切入點：連續(xù)資源　出處：《中國科學技術(shù)大學》2016年博士論文　論文類型：學位論文

【摘要】：資源是一種自然存在物或能夠給人類帶來財富的物質(zhì)、能量和信息的總稱。資源優(yōu)化是指決策者按相應的分配方案,對系統(tǒng)所屬資源進行具體分配,從而滿足系統(tǒng)收益最大化或其他既定目標。提高資源利用效率,優(yōu)化資源配置已經(jīng)成為相關學術(shù)研究中重點關注的問題。作為戰(zhàn)略規(guī)劃的核心任務,資源優(yōu)化廣泛存在于生產(chǎn)系統(tǒng)調(diào)度,項目調(diào)度,人力資源管理和云計算資源調(diào)度等系統(tǒng)中。資源的眾多存在形式使資源優(yōu)化不存在統(tǒng)一的模式。本文主要研究了啟發(fā)式算法在不同類型資源優(yōu)化問題的應用和求解方法,包括連續(xù)生產(chǎn)資源(如水,電力等),離散資源(如人力,設備等)和QoS資源(如CPU占用,延遲時間等)。本文的主要貢獻包括：(1)研究了單機批調(diào)度連續(xù)資源優(yōu)化問題與裝箱問題之間的轉(zhuǎn)化關系并提出相應的啟發(fā)式算法。尋找資源優(yōu)化問題和其他優(yōu)化問題之間的轉(zhuǎn)化關系不僅能為問題分析提供依據(jù),而且能使用對應的求解算法進行資源優(yōu)化。因此資源優(yōu)化問題與其他優(yōu)化問題的轉(zhuǎn)化關系亟待研究。我們關注如何將批生產(chǎn)調(diào)度中的連續(xù)資源優(yōu)化問題轉(zhuǎn)化為裝箱問題,從而利用裝箱問題的相關算法求解該資源優(yōu)化問題。(2)研究了一般資源函數(shù)在批調(diào)度連續(xù)資源優(yōu)化問題上的應用并提出了相應的近似求解算法。結(jié)合上一部分研究工作中批調(diào)度連續(xù)資源優(yōu)化背景,我們進一步研究了考慮一般資源函數(shù)的單機批調(diào)度連續(xù)資源優(yōu)化問題。一般資源函數(shù)能夠準確反應批調(diào)度環(huán)境下不同工件的差異性特征。相關研究指出,傳統(tǒng)資源函數(shù)(如線性和凸遞減資源函數(shù))的相關結(jié)論和算法不能用于求解考慮一般資源函數(shù)的資源優(yōu)化問題。我們采用邊際分析方法分析了考慮一般資源函數(shù)的批調(diào)度資源優(yōu)化問題的最優(yōu)化條件,并以此提出了相應的啟發(fā)式算法。(3)研究了考慮工件截止時間的離散資源優(yōu)化問題的復雜度并提出了一個分布估計算法。與上述研究工作不同,我們考慮了單機生產(chǎn)加工的離散資源優(yōu)化問題。由于離散資源和連續(xù)資源物理性質(zhì)不同,上述相關資源優(yōu)化方法和結(jié)論不能應用于此類問題。根據(jù)相關文獻研究,將離散資源分配引入傳統(tǒng)調(diào)度問題可能會改變問題的復雜度。因此,我們首先通過將離散資源優(yōu)化問題轉(zhuǎn)化為二劃分問題論證了該離散資源優(yōu)化問題的復雜度。由于二劃分問題是NP-難問題,并且該轉(zhuǎn)化過程可以在多項式時間內(nèi)完成,因此該離散資源優(yōu)化問題也是NP-難問題。為了求解該問題,我們基于一個近似的玻爾茲曼分布提出一個分布估計算法。我們提出了該分布的概率模型,并通過實驗論證提供了學習該概率模型的簡化方法。實驗論證顯示該分布估計算法在離散資源優(yōu)化性能方面優(yōu)于對比算法。(4)研究了QoS資源互補性的web服務組合問題并提出一個啟發(fā)式求解框架。QoS資源優(yōu)化問題存在于web服務組合應用中。不同于連續(xù)資源和離散資源,QoS資源是一個集合的概念并且部分QoS屬性不具有可加性性質(zhì),因此本章研究問題不能采用求解離散資源和連續(xù)資源優(yōu)化算法進行求解。近年來,有研究者指出在web服務組合問題中候選服務的QoS資源具有互補性,并且該互補性會顯著影響web服務組合的解的質(zhì)量。我們的研究主要關注實現(xiàn)相同功能的不同候選服務之間的互補性,并定義其為內(nèi)部互補性。我們從現(xiàn)實實際背景出發(fā),分析了QoS內(nèi)部互補性如何影響候選服務和整個web服務組合解。進而,我們根據(jù)相應的假設提出了該問題的數(shù)學模型并分析了該問題的復雜度：首先,我們通過將該QoS資源優(yōu)化問題的一個特例轉(zhuǎn)化為多維多選擇背包問題論證了該問題是NP-難問題：其次,我們證明了在一般情況下將該問題轉(zhuǎn)化為多維多選擇背包問題可能需要指數(shù)級時間,從而說明不能通過與背包問題的轉(zhuǎn)化求解考慮QoS內(nèi)部互補性的web服務組合問題。我們提出一個迭代式的求解框架。在每一次迭代中,該服務組合解的性能是通過求解一個分離背包問題實現(xiàn)的。根據(jù)該框架,我們提出兩個啟發(fā)式算法,并且在實驗論證中說明它們在時間性能和求解精度要優(yōu)于相應對比算法。上述實驗進一步也說明了本文提出的迭代式求解框架的有效性。
[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.

【學位授予單位】：中國科學技術(shù)大學
【學位級別】：博士
【學位授予年份】：2016
【分類號】：TP393.09;TP301.6

【相似文獻】

相關期刊論文 前10條

1 顏蔚;葛世倫;吳立人;;基于P3軟件的網(wǎng)絡計劃資源優(yōu)化方法研究[J];船海工程;2006年02期

2 藍伯雄;王威;;企業(yè)資源優(yōu)化模型系統(tǒng)的實現(xiàn)方法[J];計算機集成制造系統(tǒng);2009年09期

3 李杰;;企業(yè)計算機資源優(yōu)化系統(tǒng)[J];華北水利水電學院學報;2010年01期

4 ;“和佳ERP”企業(yè)資源優(yōu)化管理[J];計算機輔助設計與制造;2000年07期

5 劉志方;基于主動學習的資源優(yōu)化分配研究[J];科技資訊;2005年24期

6 李秋紅;資源量確定的時間-資源優(yōu)化問題的Petri網(wǎng)方法的應用[J];教育信息化;2002年05期

7 ;哈爾濱啤酒的資源優(yōu)化系統(tǒng)(BPR/ERP)項目[J];電子商務;2001年11期

8 董鳴皋,劉發(fā)全;基于MSProject2000VBA技術(shù)的網(wǎng)絡資源優(yōu)化計算機模型設計[J];系統(tǒng)工程理論與實踐;2003年12期

9 周康,同小軍,許進;資源優(yōu)化模型及遺傳算法[J];華中科技大學學報(自然科學版);2005年10期

10 彭松林;陳福生;;網(wǎng)絡資源優(yōu)化的思考和探討[J];科技資訊;2012年31期

相關會議論文 前2條

1 彭華;;鄭州市優(yōu)質(zhì)教育資源倍增工程中的教師資源優(yōu)化初探[A];2012管理創(chuàng)新、智能科技與經(jīng)濟發(fā)展研討會論文集[C];2012年

2 葉世亮;;SYBASE系統(tǒng)的資源優(yōu)化管理[A];面向21世紀的圖學教育——第十二屆全國圖學教育研討會暨第三屆制圖CAI課件演示交流會論文集[C];2000年

相關重要報紙文章 前9條

1 適閑;資源優(yōu)化配置的悖論[N];中國經(jīng)營報;2002年

2 袁楊;重慶院以規(guī)范管理促資源優(yōu)化[N];中國測繪報;2008年

3 吉林大學 趙儒煜 馬雪嬌;略論東中西部智力資源優(yōu)化配置[N];光明日報;2012年

4 本報記者 李曉海;銀行業(yè)委員縱論金融資源優(yōu)化配置[N];中國城鄉(xiāng)金融報;2013年

5 葉迎春;南化資源優(yōu)化項目全面試車[N];中國石化報;2007年

6 上海榮欣家庭裝潢有限公司 陳國宏;企業(yè)信息化是企業(yè)資源優(yōu)化配置的保證[N];中華建筑報;2004年

7 記者 葉迎春;南化資源優(yōu)化項目全部完成[N];中國石化報;2008年

8 寶振國 王朝暉;加大投入推進教育資源優(yōu)化進程[N];朝陽日報;2008年

9 記者 杭為民;謀求教育資源優(yōu)化布局 著力強化人才發(fā)展支撐[N];鹽阜大眾報;2013年

相關博士學位論文 前2條

1 梁新樂;資源優(yōu)化的啟發(fā)式算法研究[D];中國科學技術(shù)大學;2016年

2 王耀剛;高等學校教師資源優(yōu)化配置研究[D];天津大學;2006年

相關碩士學位論文 前2條

1 吳笑寒;科技資源優(yōu)化配置及管理創(chuàng)新[D];天津大學;2009年

2 張光輝;高校教師資源優(yōu)化配置研究[D];南京航空航天大學;2007年

，

本文編號：1625357