本文關(guān)鍵詞：排序理論中若干問題的理論分析和算法設(shè)計(jì)

  更多相關(guān)文章： 混合流水作業(yè) 供應(yīng)鏈問題 排序博弈 多項(xiàng)式時(shí)間算法 社會(huì)無序代價(jià)

【摘要】：排序理論是運(yùn)籌學(xué)組合優(yōu)化領(lǐng)域中最為活躍的分支之一.自上世紀(jì)50年代以來,一直備受生產(chǎn)制造、供應(yīng)鏈管理、互聯(lián)網(wǎng)等領(lǐng)域研究人員的關(guān)注,并隨著理論研究的深入及實(shí)際生產(chǎn)生活的需要,出現(xiàn)了很多新的模型.本文主要研究三類排序問題中的新模型：一個(gè)新的混合流水作業(yè)排序模型,一個(gè)新的兩階段供應(yīng)鏈排序模型和一個(gè)混合協(xié)調(diào)機(jī)制下的排序博弈模型.對(duì)于前兩個(gè)模型核心在于分析問題的計(jì)算復(fù)雜性并給出高效的最優(yōu)算法,對(duì)于第三個(gè)模型主要分析它的社會(huì)無序代價(jià)從而評(píng)判出該協(xié)調(diào)機(jī)制的優(yōu)劣.全文共分四章.第一章首先介紹了排序問題、計(jì)算復(fù)雜性和算法、算法博弈論和排序博弈等的基本概念和理論背景,接著論述了與本文相關(guān)的三類排序問題的研究背景和已有主要成果.第二章討論了一個(gè)兩臺(tái)機(jī)器兩個(gè)加工工序的混合流水作業(yè)問題.每個(gè)工件都包含兩個(gè)加工工序,第一個(gè)工序可以在任何一臺(tái)機(jī)器上加工,它被稱為柔性工序；但是第二個(gè)工序必須在第一個(gè)工序完成后只能放在第二臺(tái)機(jī)器上加工.該問題的關(guān)鍵在于如何選擇工件柔性工序的加工機(jī)器使最大完工時(shí)間(makespan)極小化.首先對(duì)于該問題的一般模型我們給出了一個(gè)完全多項(xiàng)式時(shí)間近似方案(FPTAS),而對(duì)于工件加工時(shí)間均為單位時(shí)間的特殊情況,根據(jù)兩臺(tái)機(jī)器之間的緩存情況不同分成幾個(gè)研究模型,我們分別給出了這些模型的最優(yōu)算法并且發(fā)現(xiàn)了一個(gè)非常有趣的結(jié)果：機(jī)器間的緩存空間不少于2的前提下,再增加緩存空間并不會(huì)得到更好的結(jié)果.第三章研究了一個(gè)分批加工以準(zhǔn)時(shí)交貨為目的的排序問題,該問題相當(dāng)于一個(gè)“生產(chǎn)-運(yùn)輸”兩階段的供應(yīng)鏈問題.在這個(gè)問題中有K個(gè)客戶的訂單需要加工,每個(gè)訂單包含若干個(gè)單位加工時(shí)間的工件并且有一個(gè)交貨期.一個(gè)客戶的訂單被分成若干批次,當(dāng)機(jī)器加工完一個(gè)批次的工件之后用具有載重限制的貨車運(yùn)送到客戶倉(cāng)庫(kù).客戶要求準(zhǔn)時(shí)交貨,早于交貨期或者晚于交貨期都要承擔(dān)一定懲罰費(fèi)用,而每次用貨車運(yùn)送一批完工的工件到客戶倉(cāng)庫(kù)都會(huì)產(chǎn)生定量的運(yùn)輸費(fèi)用.研究的目標(biāo)是找到一個(gè)加工安排方案使得工廠的總費(fèi)用最小.首先在工件必須從0時(shí)刻開始加工的假設(shè)下(記作假設(shè)(a)),針對(duì)單客戶模型,我們給出了最優(yōu)調(diào)度的一些性質(zhì),在此基礎(chǔ)上設(shè)計(jì)了一個(gè)多項(xiàng)式時(shí)間算法,并進(jìn)而針對(duì)多客戶模型的幾個(gè)特例給出了動(dòng)態(tài)規(guī)劃算法.其次我們考慮更接近實(shí)際的模型,也就是不帶上述假設(shè)(a)的情況下,針對(duì)單客戶模型我們也給出了一個(gè)多項(xiàng)式時(shí)間算法.而對(duì)于多客戶情況的幾個(gè)特例也給出類似帶假設(shè)(a)情況下的動(dòng)態(tài)規(guī)劃算法.第四章討論了一個(gè)排序博弈問題.在這個(gè)排序問題中,每個(gè)工件是一個(gè)自私的參與者,它可以自主地選擇一臺(tái)機(jī)器加工以謀求自身加工費(fèi)用(通常為工件的賦權(quán)完工時(shí)間)最小化.每個(gè)工件在0時(shí)刻到達(dá)并且不允許中斷加工,而每臺(tái)機(jī)器也是在0時(shí)刻達(dá)到并且可以任意選擇自己的協(xié)調(diào)機(jī)制.這一點(diǎn)不同于之前絕大多數(shù)排序博弈問題的研究.在那些研究中,機(jī)器被要求統(tǒng)一按照某種協(xié)調(diào)機(jī)制而不像本章研究的問題那樣,允許不同機(jī)器采用不同協(xié)調(diào)機(jī)制.本排序博弈問題中,共有兩個(gè)協(xié)調(diào)機(jī)制可供不同機(jī)器選擇,它們是賦權(quán)最小加工時(shí)間優(yōu)先(wSPT)機(jī)制和按比例分配速度(PS)機(jī)制.而問題的社會(huì)目標(biāo)為工件的賦權(quán)完工時(shí)間總和而不是以往的研究中通常所采用的最大完工時(shí)間(makespan).對(duì)于該排序博弈問題,我們首先給出一個(gè)該問題的松弛線性規(guī)劃,然后寫出該線性規(guī)劃問題的對(duì)偶規(guī)劃問題.通過比較上述兩個(gè)規(guī)劃問題的最優(yōu)目標(biāo)以及該排序博弈問題的最優(yōu)社會(huì)目標(biāo)和混合納什均衡解的最差社會(huì)目標(biāo)這四個(gè)數(shù)值,從而得到這個(gè)排序博弈問題的混合社會(huì)無序代價(jià)為4.
【關(guān)鍵詞】：混合流水作業(yè) 供應(yīng)鏈問題 排序博弈 多項(xiàng)式時(shí)間算法 社會(huì)無序代價(jià)
【學(xué)位授予單位】：上海大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2015
【分類號(hào)】：O223
【目錄】：

• 摘要6-8
• Abstract8-14
• 第一章 緒論14-26
• 1.1 排序問題14-15
• 1.2 計(jì)算復(fù)雜性和算法15-18
• 1.3 動(dòng)態(tài)規(guī)劃18-19
• 1.4 算法博弈論與排序博弈19-21
• 1.5 三類與本文相關(guān)的排序問題21-24
• 1.5.1 混合流水作業(yè)排序問題21-22
• 1.5.2 供應(yīng)鏈排序問題22-23
• 1.5.3 混合協(xié)調(diào)機(jī)制的排序博弈問題23-24
• 1.6 論文概述24-26
• 第二章 一類特殊的兩階段混合流水作業(yè)問題26-47
• 2.1 引言26-28
• 2.1.1 問題描述和背景26-27
• 2.1.2 相關(guān)的研究和結(jié)果27-28
• 2.1.3 我們的結(jié)果,28
• 2.2 基本假設(shè)和已有結(jié)果28-29
• 2.2.1 基本假設(shè)28-29
• 2.2.2 有的結(jié)果29
• 2.3 模型SHFS(∞)的一個(gè)全多項(xiàng)式時(shí)間近似方案29-30
• 2.4 工件均相同的SHFS(B)模型的最優(yōu)算法30-46
• 2.4.1 已知的性質(zhì)31-32
• 2.4.2 模型SHFSI(no)的最優(yōu)算法32-38
• 2.4.3 模型SHFSI(B)的最優(yōu)算法38-46
• 2.5 結(jié)束語46-47
• 第三章 一個(gè)加工-運(yùn)輸模式的兩階段供應(yīng)鏈調(diào)度問題47-74
• 3.1 引言47-49
• 3.2 符號(hào)說明和問題描述49-52
• 3.2.1 符號(hào)說明49
• 3.2.2 問題的定義49-52
• 3.3 假設(shè)(a)條件下問題IBSJS的單一訂單模型52-64
• 3.3.1 知的性質(zhì)53-54
• 3.3.2 d=0和054-55
• 3.3.3 d≥r時(shí)問題的最優(yōu)算法55-59
• 3.3.4 b59-64
• 3.4 滿足假設(shè)(a)的多客戶訂單問題K-IBSJS的幾個(gè)特殊情況64-69
• 3.4.1 已知的性質(zhì)65-66
• 3.4.2 兩個(gè)特殊情況的動(dòng)態(tài)規(guī)劃算法66-69
• 3.5 一般情況下的單訂單問題IBSJS的最優(yōu)算法69-73
• 3.6 結(jié)束語73-74
• 第四章 一個(gè)混合協(xié)調(diào)機(jī)制排序博弈問題的研究74-92
• 4.1 引言74-75
• 4.1.1 相關(guān)的研究情況介紹74-75
• 4.1.2 我們的結(jié)果75
• 4.2 基本概念和符號(hào)介紹75-77
• 4.3 存在純納什均衡解實(shí)例的PPoA的一個(gè)上界77-87
• 4.3.1 符號(hào)說明77-78
• 4.3.2 PPoA的一個(gè)上界78-87
• 4.4 排序博弈的混合社會(huì)無序代價(jià)分析87-90
• 4.4.1 混合策略組合87-88
• 4.4.2 排序博弈的混合社會(huì)無序代價(jià)88-90
• 4.5 結(jié)束語90-92
• 參考文獻(xiàn)92-99
• 博士期間完成的工作99-100
• 致謝100

，

本文編號(hào)：994243