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

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

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

• 摘要6-8
• Abstract8-14
• 第一章 緒論14-26
• 1.1 排序問題14-15
• 1.2 計算復雜性和算法15-18
• 1.3 動態(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)機制的排序博弈問題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(∞)的一個全多項式時間近似方案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
• 第三章 一個加工-運輸模式的兩階段供應(yīng)鏈調(diào)度問題47-74
• 3.1 引言47-49
• 3.2 符號說明和問題描述49-52
• 3.2.1 符號說明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時問題的最優(yōu)算法55-59
• 3.3.4 b59-64
• 3.4 滿足假設(shè)(a)的多客戶訂單問題K-IBSJS的幾個特殊情況64-69
• 3.4.1 已知的性質(zhì)65-66
• 3.4.2 兩個特殊情況的動態(tài)規(guī)劃算法66-69
• 3.5 一般情況下的單訂單問題IBSJS的最優(yōu)算法69-73
• 3.6 結(jié)束語73-74
• 第四章 一個混合協(xié)調(diào)機制排序博弈問題的研究74-92
• 4.1 引言74-75
• 4.1.1 相關(guān)的研究情況介紹74-75
• 4.1.2 我們的結(jié)果75
• 4.2 基本概念和符號介紹75-77
• 4.3 存在純納什均衡解實例的PPoA的一個上界77-87
• 4.3.1 符號說明77-78
• 4.3.2 PPoA的一個上界78-87
• 4.4 排序博弈的混合社會無序代價分析87-90
• 4.4.1 混合策略組合87-88
• 4.4.2 排序博弈的混合社會無序代價88-90
• 4.5 結(jié)束語90-92
• 參考文獻92-99
• 博士期間完成的工作99-100
• 致謝100

，

本文編號：994243