排序,也稱為調(diào)度,是組合優(yōu)化理論中的一個(gè)重要分支。對(duì)于傳統(tǒng)的排序問題,給定工件集和機(jī)器集,為了達(dá)到某個(gè)目標(biāo)值,決策者們通常考慮如何將工件最好的安排到機(jī)器上進(jìn)行加工。這個(gè)問題不僅在理論上具有很高的研究?jī)r(jià)值,在現(xiàn)實(shí)中也擁有廣泛的應(yīng)用背景。本文主要研究的是博弈排序問題中無秩序代價(jià),即在排序問題中考慮博弈理論。在博弈排序問題中,沒有中央決策者的存在,每個(gè)工件被看作是自私的博弈者或每個(gè)工件為一個(gè)代理所擁有,他們追求個(gè)體的最大利益;工件的策略集為可選擇的機(jī)器集。工件的完工時(shí)間的相反數(shù)作為工件的效用函數(shù),以所有工件的完工時(shí)間和（社會(huì)成本）為該問題的目標(biāo)函數(shù)。由于自由博弈產(chǎn)生的納什均衡解不一定是系統(tǒng)的最優(yōu)解,因此,納什均衡解與最優(yōu)解之間的差異的大小是我們所要討論的問題。常用無秩序代價(jià)（PoA）來刻畫納什均衡解和最優(yōu)解之間的差距。特別地,PoA值越接近于1說明納什均衡解對(duì)應(yīng)的目標(biāo)函數(shù)值與最優(yōu)值越接近。本文的第一章介紹了排序問題的背景知識(shí)、基本概念和定義。第二章研究了協(xié)調(diào)機(jī)制為L(zhǎng)PT的2臺(tái)同類機(jī)目標(biāo)函數(shù)為所有工件的完工時(shí)間和的博弈排序問題。我們證明了在LPT的協(xié)調(diào)機(jī)制下,各代理之間的自由博弈達(dá)到的穩(wěn)定狀態(tài)... 

【文章來源】：曲阜師范大學(xué)山東省

【文章頁(yè)數(shù)】：27 頁(yè)

【學(xué)位級(jí)別】：碩士

【文章目錄】：
摘要
Abstract
第1章 緒論
    1.1 排序問題的背景和相關(guān)概念
    1.2 博弈排序
        1.2.1 博弈論的基本概念
        1.2.2 博弈排序的協(xié)調(diào)機(jī)制和納什均衡
        1.2.3 無秩序代價(jià)的定義
    1.3 研究現(xiàn)狀
    1.4 本文的主要結(jié)果及章節(jié)安排
第2章 Q_2(LPT)|ut=-C_j| ∑C_j問題
    2.1 問題的模型
    2.2 問題的PoA分析
    2.3 總結(jié)
第3章 Q_m(LPT)|ut=-C_j|∑C_j題
    3.1 問題的模型
    3.2 問題的PoA分析
    3.3 總結(jié)
參考文獻(xiàn)
致謝



本文編號(hào)：3546112