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

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

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

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

【相似文獻(xiàn)】

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

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

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

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

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

5 ;[J];;年期

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

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

，

本文編號(hào)：1100971