本文關(guān)鍵詞：若干供應(yīng)鏈排序問(wèn)題的算法研究

  更多相關(guān)文章： 供應(yīng)鏈排序 加工和運(yùn)輸 動(dòng)態(tài)規(guī)劃算法 算法復(fù)雜度 近似比

【摘要】：供應(yīng)鏈排序是研究供應(yīng)鏈管理中加工、分批和運(yùn)輸集成的排序模型、復(fù)雜性及其算法。本文主要研究了單機(jī)和平行機(jī)上,運(yùn)輸機(jī)數(shù)量和容量有限制或不受限制的供應(yīng)鏈排序問(wèn)題。 在單機(jī)環(huán)境下,我們研究了兩個(gè)供應(yīng)鏈排序問(wèn)題。對(duì)單客戶、運(yùn)輸機(jī)數(shù)量和容量不受限制的情形,我們研究了工件有不同到達(dá)時(shí)間、加工可中斷、以最大延遲加運(yùn)輸費(fèi)用為目標(biāo)的問(wèn)題,給出了復(fù)雜度為O(n3)的最優(yōu)算法。對(duì)單客戶、運(yùn)輸機(jī)數(shù)量和容量有限制的情形,我們考慮了機(jī)器在加工過(guò)程需要安排維護(hù)區(qū)間,使得機(jī)器連續(xù)加工的時(shí)間不超過(guò)T。我們以車輛運(yùn)完最后一批工件返回制造商處的時(shí)間為目標(biāo),對(duì)問(wèn)題給出了2-近似算法。 在平行機(jī)環(huán)境下,我們研究了運(yùn)輸機(jī)數(shù)量和容量不受限制的三個(gè)供應(yīng)鏈排序問(wèn)題。首先,我們研究了以最大延遲加運(yùn)輸費(fèi)用為目標(biāo)的兩個(gè)問(wèn)題。對(duì)單客戶情形,我們研究了工件有不同到達(dá)時(shí)間、加工不可中斷的問(wèn)題,設(shè)計(jì)了漸近最優(yōu)的近似算法。對(duì)多客戶情形,我們研究了工件在零時(shí)刻就緒、加工不可中斷的問(wèn)題,設(shè)計(jì)了漸近最優(yōu)的近似算法。然后,我們研究了在單客戶情形下,工件有不同到達(dá)時(shí)間、以送貨時(shí)間和加運(yùn)輸費(fèi)用為目標(biāo)的供應(yīng)鏈排序問(wèn)題,設(shè)計(jì)了近似比為3-1的算法。
【關(guān)鍵詞】：供應(yīng)鏈排序 加工和運(yùn)輸 動(dòng)態(tài)規(guī)劃算法 算法復(fù)雜度 近似比
【學(xué)位授予單位】：華東理工大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：O223
【目錄】：

• 摘要5-6
• Abstract6-9
• 第1章 緒論9-19
• 1.1 排序問(wèn)題9-10
• 1.2 供應(yīng)鏈排序問(wèn)題10-17
• 1.2.1 供應(yīng)鏈排序問(wèn)題的模型10-12
• 1.2.2 供應(yīng)鏈排序問(wèn)題研究綜述12-17
• 1.3 本文的研究?jī)?nèi)容17-19
• 第2章 單機(jī)可中斷以L_(max)+TC為目標(biāo)的問(wèn)題19-22
• 2.1 問(wèn)題描述19
• 2.2 算法設(shè)計(jì)和分析19-22
• 2.2.1 最優(yōu)性質(zhì)20-21
• 2.2.2 算法設(shè)計(jì)21
• 2.2.3 算法復(fù)雜性21-22
• 第3章 平行機(jī)不可中斷以L_(max)+TC為目標(biāo)的問(wèn)題22-29
• 3.1 問(wèn)題描述22-23
• 3.2 問(wèn)題P_m|r_j|V(∞,∞)|1|L_(max)+TC的近似算法23-25
• 3.2.1 算法設(shè)計(jì)23
• 3.2.2 算法性能分析23-25
• 3.3 問(wèn)題P_m||V(∞,∞)|k|L_(max)+TC的近似算法25-29
• 3.3.1 算法設(shè)計(jì)25-26
• 3.3.2 算法性能分析26-29
• 第4章 平行機(jī)不可中斷以∑D_j+TC為目標(biāo)的問(wèn)題29-34
• 4.1 問(wèn)題描述29-30
• 4.2 3-1-近似算法30-34
• 4.2.1 算法設(shè)計(jì)30-31
• 4.2.2 算法性能分析31-34
• 第5章 具有可選維護(hù)區(qū)間的單機(jī)排序問(wèn)題34-45
• 5.1 單機(jī)可選維護(hù)區(qū)間的加工排序問(wèn)題34-39
• 5.1.1 算法設(shè)計(jì)35-36
• 5.1.2 算法性能分析36-39
• 5.2 單機(jī)可選維護(hù)區(qū)間的集成排序問(wèn)題39-45
• 5.2.1 算法設(shè)計(jì)40-43
• 5.2.2 算法性能分析43-45
• 第6章 總結(jié)與展望45-46
• 參考文獻(xiàn)46-49
• 致謝49

【參考文獻(xiàn)】

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

1 陳榮軍;唐國(guó)春;;平行機(jī)物流排序的近似算法[J];應(yīng)用數(shù)學(xué)學(xué)報(bào);2011年06期

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

1 仲維亞;供應(yīng)鏈管理中的若干排序問(wèn)題研究[D];浙江大學(xué);2008年

，

本文編號(hào)：526030