本文關(guān)鍵詞：分批的供應(yīng)、加工、配送供應(yīng)鏈排序問(wèn)題

  更多相關(guān)文章： 排序 分批供應(yīng) 分批加工 分批配送 多項(xiàng)式時(shí)間算法 近似算法 近似比

【摘要】：排序問(wèn)題是一類(lèi)重要的組合最優(yōu)化問(wèn)題,是在某些約束條件下合理安排工件在機(jī)器上的加工順序從而使目標(biāo)值達(dá)到最優(yōu).供應(yīng)鏈排序則是將排序的方法應(yīng)用到供應(yīng)鏈管理上使生產(chǎn)、運(yùn)輸?shù)冗^(guò)程得到整體優(yōu)化.隨著時(shí)代的發(fā)展和競(jìng)爭(zhēng)的加劇,如何合理安排生產(chǎn)和運(yùn)輸使客戶需求得到滿足即提高服務(wù)水平變得尤為重要.本文研究了綜合考慮原材料的供應(yīng)、工件加工以及成品配送目標(biāo)函數(shù)為極小化最大完工時(shí)間的供應(yīng)鏈排序問(wèn)題.文章結(jié)構(gòu)安排如下：第一章,介紹了一些基本概念如：3-劃分問(wèn)題、算法的復(fù)雜性等,并對(duì)文中符號(hào)進(jìn)行了說(shuō)明,最后對(duì)本文所研究問(wèn)題的產(chǎn)生背景、研究現(xiàn)狀、研究成果進(jìn)行簡(jiǎn)要闡述.第二章,研究了極小化最大完工時(shí)間分批加工、分批配送的供應(yīng)鏈排序問(wèn)題.制造商與客戶都只有一個(gè),制造商為一臺(tái)容量為B的并行批加工機(jī)器;運(yùn)輸工具僅有一臺(tái)且容量為K;共有n個(gè)工件需要加工和配送.可將整個(gè)調(diào)度過(guò)程劃分為兩個(gè)階段：第一階段工件在機(jī)器上進(jìn)行加工,第二階段運(yùn)輸工具將已完成加工的工件配送給客戶.首先對(duì)K≥n的情況給出復(fù)雜性為O(nlog n)的多項(xiàng)式時(shí)間最優(yōu)算法.然后對(duì)Kn的情況進(jìn)行了分析;對(duì)K=B的情形給出復(fù)雜性為O(nlog n)的多項(xiàng)式時(shí)間最優(yōu)算法;對(duì)兩種特殊情形KB、KB分別給出復(fù)雜性為O(nB3 log n)、O(nB log n),近似比上界為3/2的近似算法.最后對(duì)問(wèn)題的一般情形給出復(fù)雜性為O(nB3 log n)、近似比小于3/2的近似算法.第三章,研究了極小化最大完工時(shí)間分批的供應(yīng)、加工、配送供應(yīng)鏈排序問(wèn)題.該問(wèn)題在第二章所研究問(wèn)題的基礎(chǔ)上增加了一個(gè)供應(yīng)商,可將該問(wèn)題劃分為三個(gè)階段：第一階段工件由一臺(tái)容量為K1的運(yùn)輸工具將工件從供應(yīng)商處運(yùn)至制造商處,第二階段工件在容量為B的并行批機(jī)器上進(jìn)行加工,第三階段容量為K2的運(yùn)輸工具將已完成加工的工件配送給客戶.首先證明了該問(wèn)題是強(qiáng)NP-難的,然后給出復(fù)雜性為O(nB3 log n)、近似比上界為5/2的近似算法,并對(duì)某些特殊情形給出多項(xiàng)式時(shí)間最優(yōu)算法.
【關(guān)鍵詞】：排序 分批供應(yīng) 分批加工 分批配送 多項(xiàng)式時(shí)間算法 近似算法 近似比
【學(xué)位授予單位】：曲阜師范大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類(lèi)號(hào)】：O223
【目錄】：

• 摘要3-4
• Abstract4-7
• 第1章 緒論7-11
• 1.1 引言7
• 1.2 基本概念7-9
• 1.3 本文所研究問(wèn)題的應(yīng)用背景與研究現(xiàn)狀9-10
• 1.4 本文的主要工作10-11
• 第2章 極小化最大完工時(shí)間分批加工、分批配送的供應(yīng)鏈排序問(wèn)題11-23
• 2.1 問(wèn)題描述11-12
• 2.2 符號(hào)說(shuō)明12
• 2.3 多項(xiàng)式可解情形12-14
• 2.4 一般情形14-22
• 2.5 本章小結(jié)22-23
• 第3章 極小化最大完工時(shí)間分批的供應(yīng)、加工、配送供應(yīng)鏈排序問(wèn)題23-29
• 3.1 符號(hào)說(shuō)明23
• 3.2 問(wèn)題描述23-24
• 3.3 多項(xiàng)式可解情形24-26
• 3.4 一般情形26-27
• 3.5 本章小結(jié)27-29
• 參考文獻(xiàn)29-32
• 在讀期間發(fā)表的學(xué)術(shù)論文及研究成果32-33
• 致謝33

【相似文獻(xiàn)】

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

1 周泓,張惠民;求解多目標(biāo)作業(yè)排序問(wèn)題的遺傳算法[J];系統(tǒng)工程理論與實(shí)踐;2001年08期

2 周泓,姬彬;求解作業(yè)排序問(wèn)題的通用混合遺傳算法研究[J];系統(tǒng)工程理論與實(shí)踐;2001年12期

3 陳德伍,張 峰;一類(lèi)新的可控排序問(wèn)題(英文)[J];運(yùn)籌學(xué)學(xué)報(bào);2001年04期

4 張瑞,劉國(guó)珍;單機(jī)排序問(wèn)題最優(yōu)解方法[J];聊城師院學(xué)報(bào)(自然科學(xué)版);2001年02期

5 黎群;單臺(tái)機(jī)器多目標(biāo)作業(yè)排序問(wèn)題的探討[J];系統(tǒng)工程理論方法應(yīng)用;2001年02期

6 方保昒,徐漢忠;用單親遺傳算法解具有窗口式交貨期的多機(jī)加工排序問(wèn)題[J];系統(tǒng)工程理論方法應(yīng)用;2001年04期

7 宋政芳,孫世杰,吳春燕;一個(gè)超前有獎(jiǎng)遲后受罰的排序問(wèn)題(英文)[J];運(yùn)籌學(xué)學(xué)報(bào);2002年04期

8 趙傳立,唐恒永;具有相關(guān)調(diào)整時(shí)間的排序問(wèn)題[J];沈陽(yáng)師范學(xué)院學(xué)報(bào)(自然科學(xué)版);2002年01期

9 鄭自途;關(guān)于"三臺(tái)以上機(jī)床作業(yè)排序問(wèn)題"的算法[J];天津理工學(xué)院學(xué)報(bào);2002年04期

10 張玉忠,苗翠霞;復(fù)制法及其在分批排序問(wèn)題中的應(yīng)用[J];曲阜師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2004年02期

中國(guó)重要會(huì)議論文全文數(shù)據(jù)庫(kù) 前10條

1 柏孟卓;唐國(guó)春;;加工時(shí)間可控的同時(shí)加工排序問(wèn)題[A];2006年中國(guó)運(yùn)籌學(xué)會(huì)數(shù)學(xué)規(guī)劃分會(huì)代表會(huì)議暨第六屆學(xué)術(shù)會(huì)議論文集[C];2006年

2 張蓮珠;;關(guān)于六角鏈的極值和排序問(wèn)題的一些結(jié)果[A];中國(guó)運(yùn)籌學(xué)會(huì)第六屆學(xué)術(shù)交流會(huì)論文集（上卷）[C];2000年

3 周支立;李懷祖;;有重疊區(qū)域的兩抓鉤周期性排序問(wèn)題的求解[A];Systems Engineering, Systems Science and Complexity Research--Proceeding of 11th Annual Conference of Systems Engineering Society of China[C];2000年

4 孫世杰;陳躍;;參數(shù)可控的排序問(wèn)題[A];2001年全國(guó)數(shù)學(xué)規(guī)劃及運(yùn)籌研討會(huì)論文集[C];2001年

5 張玉忠;;分批排序問(wèn)題研究[A];中國(guó)運(yùn)籌學(xué)會(huì)第七屆學(xué)術(shù)交流會(huì)論文集（上卷）[C];2004年

6 張玉忠;;分批排序問(wèn)題研究[A];中國(guó)運(yùn)籌學(xué)會(huì)第七屆學(xué)術(shù)交流會(huì)論文集（中卷）[C];2004年

7 譚萬(wàn)達(dá);;二元對(duì)比排序中的最少逆序原理[A];中國(guó)系統(tǒng)工程學(xué)會(huì)模糊數(shù)學(xué)與模糊系統(tǒng)委員會(huì)第五屆年會(huì)論文選集[C];1990年

8 呂緒華;楊漢興;;求解裝配式排序問(wèn)題的歸并算法及其性能比研究[A];中國(guó)運(yùn)籌學(xué)會(huì)第六屆學(xué)術(shù)交流會(huì)論文集（下卷）[C];2000年

9 樊保強(qiáng);;帶倉(cāng)儲(chǔ)約束的準(zhǔn)時(shí)排序問(wèn)題[A];中國(guó)運(yùn)籌學(xué)會(huì)第九屆學(xué)術(shù)交流會(huì)論文集[C];2008年

10 陳榮軍;唐國(guó)春;;自由作業(yè)環(huán)境下的供應(yīng)鏈排序問(wèn)題[A];中國(guó)運(yùn)籌學(xué)會(huì)第九屆學(xué)術(shù)交流會(huì)論文集[C];2008年

中國(guó)重要報(bào)紙全文數(shù)據(jù)庫(kù) 前1條

1 山東 趙玉勇;數(shù)組，你的規(guī)律機(jī)器[N];電腦報(bào);2004年

，

本文編號(hào)：814304