等級(jí)約束下的負(fù)載均衡問(wèn)題是組合優(yōu)化領(lǐng)域的經(jīng)典難題之一,其在近十年里得到了廣泛的研究。等級(jí)約束下的負(fù)載均衡問(wèn)題即把若干個(gè)帶等級(jí)的工件分配給一些帶等級(jí)的機(jī)器加工,工件可以在等級(jí)不低于自己的機(jī)器上加工,且每個(gè)工件只能被一臺(tái)機(jī)器不間斷的加工。目標(biāo)是尋找一種分配方案使得最大機(jī)器負(fù)載最小化,這里的負(fù)載一般定義為工件的加工時(shí)間或加工工件所需的各種資源。本文主要研究了等級(jí)約束下的負(fù)載均衡問(wèn)題的兩類(lèi)廣義形式:多重負(fù)載均衡問(wèn)題和多維負(fù)載均衡問(wèn)題。等級(jí)約束下的多重負(fù)載均衡問(wèn)題即給定若干個(gè)客戶(hù)和一些帶等級(jí)的機(jī)器,每個(gè)客戶(hù)提交若干個(gè)帶等級(jí)的工件給這些機(jī)器加工,工件可以在等級(jí)不低于自己的機(jī)器上加工,且每個(gè)工件只能被一臺(tái)機(jī)器不間斷的加工。目標(biāo)是尋找一種分配方案使得最大機(jī)器負(fù)載最小化。對(duì)等級(jí)約束下的多重負(fù)載均衡問(wèn)題,當(dāng)機(jī)器臺(tái)數(shù)m = 2時(shí),本文設(shè)計(jì)了一個(gè)5/4-近似算法,一個(gè)5/3-最優(yōu)在線(xiàn)算法和一個(gè)在所有工件加工時(shí)間之和的一半已知的情況下的3/2-最優(yōu)半在線(xiàn)算法并分析了近似比;當(dāng)機(jī)器臺(tái)數(shù)m ≥ 3時(shí),本文設(shè)計(jì)了一個(gè)2-1/m-1-近似算法并分析了近似比。m-1等級(jí)約束下的多維負(fù)載均衡問(wèn)題即把若干個(gè)帶等級(jí)的工件分配給... 

【文章來(lái)源】：云南大學(xué)云南省 211工程院校

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

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

【文章目錄】：
摘要
ABSTRACT
第一章 引言
    §1.1 基本知識(shí)
    §1.2 研究背景
    §1.3 主要結(jié)果
    §1.4 論文結(jié)構(gòu)
第二章 等級(jí)約束下的多重負(fù)載均衡問(wèn)題
    §2.1 問(wèn)題描述
    §2.2 離線(xiàn)算法
    §2.3 最優(yōu)在線(xiàn)算法
    §2.4 最優(yōu)半在線(xiàn)算法
第三章 等級(jí)約束下的多維負(fù)載平衡問(wèn)題
    §3.1 問(wèn)題描述
    §3.2 2d-近似算法
    §3.3 全多項(xiàng)式時(shí)間近似方案
結(jié)論
參考文獻(xiàn)
攻讀碩士學(xué)位期間完成的研究成果
致謝


【參考文獻(xiàn)】：
期刊論文
[1]lp范數(shù)下具有等級(jí)約束的負(fù)載均衡問(wèn)題[J]. 李偉東,李陳筠然,李建平.  計(jì)算機(jī)科學(xué)與探索. 2016(08)
[2]平行機(jī)上訂單半在線(xiàn)排序的LS算法的性能比分析[J]. 唐峰,聶勁.  系統(tǒng)工程. 2016(06)
[3]排序問(wèn)題的定義、分類(lèi)和在國(guó)內(nèi)的某些研究進(jìn)展[J]. 唐國(guó)春.  運(yùn)籌學(xué)雜志. 1990(02)

博士論文
[1]當(dāng)代工業(yè)中的若干排序問(wèn)題研究[D]. 季敏.浙江大學(xué) 2006

碩士論文
[1]單機(jī)半在線(xiàn)排序算法競(jìng)爭(zhēng)比分析[D]. 陶冶.上海交通大學(xué) 2010



本文編號(hào)：3300888