發(fā)布時(shí)間：2018-03-17 15:35

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

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

【學(xué)位授予單位】：中國(guó)科學(xué)技術(shù)大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2016
【分類號(hào)】：TP393.09;TP301.6

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

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

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

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

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

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

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

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

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

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

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

相關(guān)會(huì)議論文 前2條

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

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

相關(guān)重要報(bào)紙文章 前9條

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

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

3 吉林大學(xué) 趙儒煜 馬雪嬌;略論東中西部智力資源優(yōu)化配置[N];光明日?qǐng)?bào);2012年

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

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

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

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

8 寶振國(guó) 王朝暉;加大投入推進(jìn)教育資源優(yōu)化進(jìn)程[N];朝陽(yáng)日?qǐng)?bào);2008年

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

相關(guān)博士學(xué)位論文 前2條

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

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

相關(guān)碩士學(xué)位論文 前2條

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

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

，

本文編號(hào)：1625357