本文關(guān)鍵詞：帶不可用時間段的若干單機供應(yīng)鏈排序問題的算法研究

  更多相關(guān)文章： 供應(yīng)鏈排序 不可用時間段 可恢復(fù) 不可恢復(fù) 近似算法

【摘要】：本文主要對單臺機器環(huán)境下有不可用時間段的供應(yīng)鏈排序問題進行了研究。這類排序問題同時考慮了工件的加工與運輸,目標(biāo)均為最小化總發(fā)送時間與總運輸費用之和。我們從機器有一個不可用時間段開始,由單個客戶到多個客戶,工件的加工時間由確定的到與開工時間有關(guān),運輸工具由容量無限制到容量有限制,再到機器有多個不可用時間段的情形,分別進行了深入研究。全文由五章組成。第一章介紹了與本文相關(guān)的一些排序問題的基本概念和定義,總結(jié)了供應(yīng)鏈排序問題的研究現(xiàn)狀,以及機器有不可用時間段的排序問題的一些概念及研究進展。第二章研究了運輸工具數(shù)量充足、容量無限制的單機供應(yīng)鏈排序問題。由于機器有一個不可用時間段,工件的加工過程可能被中斷。當(dāng)機器重新可用時,工件的加工有兩種情況,一種情況是加工可恢復(fù),即工件可繼續(xù)完成加工；另一種情況是加工不可恢復(fù),即工件需要重新開始加工。多個完成加工的工件可組成一批由運輸工具運輸給一個客戶。當(dāng)工件的加工可恢復(fù)時,我們給出了最優(yōu)算法,其時間復(fù)雜性為O(n2)；當(dāng)工件的加工不可恢復(fù)時,我們提出了3/2-近似算法,并進一步設(shè)計了多項式時間近似方案(PTAS)。第三章主要討論了運輸工具數(shù)量充足、但容量受限制的單機供應(yīng)鏈排序問題。工件完工后發(fā)送給多個客戶,目標(biāo)函數(shù)為最小化總發(fā)送時間與總運輸費用之和。我們分別研究了工件的加工可恢復(fù)及不可恢復(fù)兩種情況,而且運輸工具發(fā)送工件也有直接發(fā)送和選路線發(fā)送兩種方式。這里直接發(fā)送是指某客戶的工件完工后直接從生產(chǎn)工廠發(fā)送給該客戶；而選路線發(fā)送是指運輸工具發(fā)送的一批工件中有多個客戶的工件,可以選擇一條路線依次將工件發(fā)送給客戶。當(dāng)工件的加工可恢復(fù)時,我們分別就運輸工具直接發(fā)送及選路線發(fā)送工件兩種情形,在得到最優(yōu)加工序的基礎(chǔ)上,分別提出了動態(tài)規(guī)劃算法得到最優(yōu)發(fā)送序；當(dāng)工件的加工不可恢復(fù)、運輸工具直接發(fā)送工件時,我們提出了耗時短易操作的近似算法,該算法是2μ-近似算法,這里μ-min{c,1+(1-1/c)Σλi/λmin},其中c表示運輸工具的容量,入m。n表示運輸一批工件的最少費用；當(dāng)工件的加工是不可恢復(fù)、運輸工具選路線發(fā)送工件時,我們基于工件的加工是可恢復(fù)的最優(yōu)序,提供了2-近似算法。第四章研究的是工件帶惡化效應(yīng)的單機供應(yīng)鏈排序問題。工件的加工是不可恢復(fù)的,工件的實際加工時間與惡化率、開工時間有關(guān),并且在不可用時間段之前完工的工件必須在不可用時間段之前發(fā)送給客戶。我們證明問題是NP-難的,并在分析問題最優(yōu)序性質(zhì)的基礎(chǔ)上,提出了偽多項式時間的動態(tài)規(guī)劃算法。進一步地,我們確定了問題目標(biāo)函數(shù)值的上界及下界,并得到了問題的完全多項式時間近似方案(FPTAS)。第五章主要研究了機器有多個不可用時間段的單機供應(yīng)鏈排序問題。這個問題起源于醫(yī)院倉庫的醫(yī)用耗材的物流管理。醫(yī)用耗材需要用打包機打包后配送給醫(yī)院各科室。有的打包過程可中斷,而有的打包過程是不可中斷的,否則會使某些材料受到污染。配送需要由倉庫付費。倉庫經(jīng)理希望高效利用打包機,同時希望降低配送成本。如果我們將實際問題中的打包機視為一臺機器,將醫(yī)用耗材視為工件,那么問題即轉(zhuǎn)化為供應(yīng)鏈排序問題。對于機器有周期性不可用時間段,工件的加工不可恢復(fù),完工工件成批地由一個無容量限制的運輸工具發(fā)送至多個客戶,運輸工具的運輸時間固定在每個可用時間段結(jié)束時間的問題,我們證明該問題是強NP-難的,并提出了2-近似算法,以及可求得問題最優(yōu)解的分支定界算法。通過隨機生成實例所做的數(shù)值模擬,我們可以看到,近似算法是有效的算法。對于機器的可用時間段不可超過某固定值,運輸工具的發(fā)送時間不受限制的問題,若工件加工可恢復(fù),我們可在多項式時間內(nèi)得到最優(yōu)序；若工件加工不可恢復(fù),我們證明問題是強NP-難的,并提出了一個2-近似算法。
【關(guān)鍵詞】：供應(yīng)鏈排序 不可用時間段 可恢復(fù) 不可恢復(fù) 近似算法
【學(xué)位授予單位】：華東理工大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2015
【分類號】：O223
【目錄】：

• 摘要5-7
• Abstract7-12
• 第1章 緒論12-26
• 1.1 排序問題12-13
• 1.2 算法及計算復(fù)雜性13-15
• 1.3 NP問題15-18
• 1.4 供應(yīng)鏈排序問題簡介18-21
• 1.5 機器有不可用時間段的排序問題21-23
• 1.6 論文概述23-26
• 第2章 運輸工具容量無限制的單客戶供應(yīng)鏈排序問題26-40
• 2.1 引言26
• 2.2 問題描述26-27
• 2.3 工件加工可恢復(fù)的情形27-29
• 2.4 工件加工不可恢復(fù)的情形29-40
• 2.4.1 問題的一些性質(zhì)29-30
• 2.4.2 近似算法30-36
• 2.4.3 多項式時間近似方案(PTAS)36-40
• 第3章 運輸工具容量有限制的多客戶供應(yīng)鏈排序問題40-56
• 3.1 引言40-41
• 3.2 問題描述及符號說明41-42
• 3.3 工件加工可恢復(fù)的情形42-46
• 3.3.1 運輸工具直接發(fā)送43-45
• 3.3.2 運輸工具選路線發(fā)送45-46
• 3.4 工件加工不可恢復(fù)的情形46-56
• 3.4.1 運輸工具直接發(fā)送46-52
• 3.4.2 運輸工具選路線發(fā)送52-56
• 第4章 工件具有惡化效應(yīng)的單機供應(yīng)鏈排序問題56-64
• 4.1 引言56-57
• 4.2 問題描述及符號說明57
• 4.3 求解問題57-64
• 4.3.1 問題的性質(zhì)58-59
• 4.3.2 動態(tài)規(guī)劃算法59
• 4.3.3 完全多項式近似方案(FPTAS)59-64
• 第5章 單機帶多個不可用時間段的供應(yīng)鏈排序問題64-82
• 5.1 引言64-65
• 5.2 不可用時間段具有周期性的供應(yīng)鏈排序問題65-73
• 5.2.1 問題描述及符號說明65-66
• 5.2.2 問題的復(fù)雜性分析66-67
• 5.2.3 近似算法67-71
• 5.2.4 分支定界算法71-73
• 5.2.5 數(shù)值模擬73
• 5.3 可用時間段不超過固定值的供應(yīng)鏈排序問題73-82
• 5.3.1 問題描述及符號說明73-76
• 5.3.2 工件加工可恢復(fù)的情形76-77
• 5.3.3 工件加工不可恢復(fù)的情形77-82
• 第6章 結(jié)論與展望82-84
• 參考文獻84-94
• 致謝94-96
• 附錄：博士在讀期間發(fā)表的論文96

【相似文獻】

中國期刊全文數(shù)據(jù)庫 前5條

1 馬英;左春榮;楊善林;;帶不可用時間段和惡化加工時間的單機調(diào)度[J];系統(tǒng)工程學(xué)報;2010年03期

2 馬英;楊善林;儲誠斌;;帶不可用時間段的部分可續(xù)型單機最大完工時間調(diào)度[J];系統(tǒng)工程理論與實踐;2009年04期

3 馬英;左春榮;楊善林;;帶不可用時間段的兩臺同類機加權(quán)完工時間和調(diào)度[J];中國科學(xué)技術(shù)大學(xué)學(xué)報;2009年06期

4 王海明;劉吉紅;王慶磊;;帶不可用時間段的不允許等待柔性流水排序問題[J];蘭州大學(xué)學(xué)報(自然科學(xué)版);2007年01期

5 ;[J];;年期

中國博士學(xué)位論文全文數(shù)據(jù)庫 前1條

1 范靜;帶不可用時間段的若干單機供應(yīng)鏈排序問題的算法研究[D];華東理工大學(xué);2015年

，

本文編號：1100971