發(fā)布時間：2017-12-31 01:41

  本文關(guān)鍵詞：工件帶權(quán)重的平行機(jī)博弈排序問題　出處：《曲阜師范大學(xué)》2015年碩士論文　論文類型：學(xué)位論文

  更多相關(guān)文章： 負(fù)載均衡 權(quán)重 啟動費(fèi)用 納什均衡

【摘要】：在資源配置問題中,不同的工作任務(wù)被安排到各個加工資源上來完成,例如:平行機(jī)排序問題.在近幾年的研究中,博弈論的概念和工具被應(yīng)用到資源配置問題中,形成了博弈排序.本文研究的是平行機(jī)博弈排序的三種模型:負(fù)載均衡模型、包含啟動費(fèi)用的新模型、恒速機(jī)上的負(fù)載均衡模型.前兩個模型中,機(jī)器是同速機(jī),第三個模型中,機(jī)器是恒速機(jī).與前人成果不同之處在于:我們考慮的是工件帶權(quán)重的情況,相應(yīng)的將目標(biāo)函數(shù)(社會成本)定義為所有工件的加權(quán)總成本.這里工件的成本或者是擁塞時間(定義為工件所在機(jī)器的負(fù)載),或者是復(fù)合成本(包含擁塞時間和分?jǐn)偟膯淤M(fèi)用).這一類平行機(jī)上的博弈排序問題,不同于傳統(tǒng)排序問題:一個權(quán)威專家做出排序決定.現(xiàn)在每一個局中人,以最小化自己的成本為目的,決定由哪臺機(jī)器加工他的工件.在運(yùn)行過程中,會導(dǎo)致納什均衡.然而就一個給定的目標(biāo)函數(shù)而言,這樣的均衡不一定達(dá)到最優(yōu),事實(shí)上,常常與最優(yōu)值相差甚遠(yuǎn).因此,分析納什均衡序相較于最優(yōu)序的性質(zhì)至關(guān)重要.我們用無序性代價(PoA)和穩(wěn)定性代價(PoS)兩個指標(biāo)來衡量納什均衡序的效果.針對每個模型,分析其納什均衡序的性質(zhì),并且得到了PoA和PoS的界.工件帶權(quán)重的同速機(jī)負(fù)載均衡模型,￡￡-+--PoSnmnm1)1()1(2min1wPoA￡;工件帶權(quán)重的啟動費(fèi)用分?jǐn)偰Ｐ?( )2121 wPoSPoA+￡￡￡r;工件帶權(quán)重的恒速機(jī)負(fù)載均衡模型,÷???è?+￡ 11mnswsPoAm.其中,min1pr=,minp是工件加工時間的最小值,min maxwww =,maxw和minw分別表示所有工件權(quán)重中的最大值和最小值,1s和ms分別是機(jī)器速度的最小值和最大值.
[Abstract]:In the problem of resource allocation in different tasks assigned to each processing resources to complete, for example: the parallel machine scheduling problem. In recent years, the concepts and tools of game theory are applied to the problem of resource allocation, formed game sort. This paper is a study of three parallel machine scheduling game model the load balancing model, the new model includes start-up costs, constant speed machine load balancing model. The first two models, the machine is the same speed machine, the third model, the machine is in constant speed machine. Unlike the previous results: we consider is the workpiece with the weight of the corresponding. The objective function (Social cost) is defined as the weighted total cost of all the jobs here. The cost of the part or congestion time (load is defined as the machine, the workpiece) or composite cost (including congestion time and sharing start-up costs) this. The game scheduling problem on parallel machines, different from the traditional scheduling problem: an authoritative expert to make sequencing decisions. Now every person in the game, to minimize their cost so as to decide which machine processing of his work. In the process of operation, will lead to a Nash equilibrium. However, an objective function given, this equilibrium is not necessarily optimal, in fact, often with the optimal value far. Therefore, it is important to determine the Nash equilibrium order compared with optimal properties. We use random price (PoA) and price stability (PoS) two indicators to measure the Nash equilibrium for each order. Analysis of the properties of Nash equilibrium model, order, and get PoA and PoS. A load balance model with the same speed machine workpiece with weight, F & -+--PoSnmnm1) 1 (1) 2min1wPoA (f; workpiece with the weight of the start-up cost allocation model, (2121) WPoSPoA+ & & F R; workpiece with the weight of the constant speed machine load balancing model, /??? S? F + 11mnswsPoAm. min1pr=, where MINP is the minimum processing time, min = maxwww, maxw and minw respectively, the maximum and minimum weight of all jobs, 1s and MS respectively. Minimum and maximum speed of the machine.

【學(xué)位授予單位】：曲阜師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：O225

【相似文獻(xiàn)】

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

1 張智聰;鄭力;翁小華;;基于增強(qiáng)學(xué)習(xí)的平行機(jī)調(diào)度研究[J];計(jì)算機(jī)集成制造系統(tǒng);2007年01期

2 陳榮軍;唐國春;;平行機(jī)的供應(yīng)鏈排序[J];系統(tǒng)科學(xué)與數(shù)學(xué);2010年02期

3 陳榮軍;張峰;唐國春;;平行機(jī)及自由作業(yè)的排序與轉(zhuǎn)包[J];系統(tǒng)工程學(xué)報(bào);2011年05期

4 陳榮軍;唐國春;;平行機(jī)的排序與轉(zhuǎn)包(英文)[J];數(shù)學(xué)季刊;2012年04期

5 蔣大奎;李波;;平行機(jī)作業(yè)環(huán)境下的訂單分配與排序[J];管理學(xué)報(bào);2013年06期

6 王成堯,汪定偉;有模機(jī)配合約束的平行機(jī)臺調(diào)度方法[J];東北大學(xué)學(xué)報(bào);1999年04期

7 曾歡歡,胡建華;可換速平行機(jī)工件帶起止值的搶先進(jìn)度表[J];數(shù)學(xué)理論與應(yīng)用;1999年02期

8 蔣大奎;李波;曹立思;;考慮轉(zhuǎn)包的平行機(jī)供應(yīng)鏈排序[J];控制與決策;2014年05期

9 陳仕平,張國川;兩臺平行機(jī)的實(shí)時到達(dá)在線排序[J];應(yīng)用數(shù)學(xué)學(xué)報(bào);2000年01期

10 周偉剛;高成修;黃凱;;加工時間可控和簡單線性增長的平行機(jī)排序[J];應(yīng)用數(shù)學(xué)學(xué)報(bào);2010年04期

相關(guān)會議論文 前1條

1 聞?wù)裥l(wèi);;一類平行機(jī)上的任務(wù)指派問題及其動態(tài)規(guī)劃算法[A];中國運(yùn)籌學(xué)會第九屆學(xué)術(shù)交流會論文集[C];2008年

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

1 程貞敏;平行機(jī)調(diào)度問題研究的若干結(jié)果[D];北京師范大學(xué);2008年

2 蔡圣義;同類平行機(jī)在線半在線排序參數(shù)界的若干研究[D];浙江大學(xué);2010年

3 何龍敏;一類平行機(jī)和批處理機(jī)組成的二階段柔性流水作業(yè)問題[D];上海大學(xué);2006年

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

1 郭平寧;工件帶權(quán)重的平行機(jī)博弈排序問題[D];曲阜師范大學(xué);2015年

2 洪文益;與平行機(jī)排序相關(guān)的幾個組合問題研究[D];清華大學(xué);2013年

3 李松松;在平行機(jī)博弈排序中的近似強(qiáng)納什均衡問題[D];曲阜師范大學(xué);2013年

4 王君麗;有加工權(quán)限平行機(jī)在線問題研究[D];浙江大學(xué);2012年

5 財(cái)玉華;具有非交叉維修時間的平行機(jī)在線排序[D];鄭州大學(xué);2007年

6 莫禎貞;改進(jìn)粒子群算法在模糊環(huán)境下平行機(jī)批調(diào)度問題中的應(yīng)用研究[D];中國科學(xué)技術(shù)大學(xué);2010年

7 林琳;具有同時性約束的平行機(jī)排序問題[D];鄭州大學(xué);2006年

8 徐武來;具有完工期和工裝數(shù)量約束的平行機(jī)調(diào)度方法[D];廣東工業(yè)大學(xué);2012年

9 何曉瓊;一致平行機(jī)上在線排序[D];湖南師范大學(xué);2009年

10 袁俊嶺;鏈組約束下的平行機(jī)在線排序[D];鄭州大學(xué);2008年

，

本文編號：1357525