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

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

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

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

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


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

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

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



本文編號：3300888