有惡化效應(yīng)的兩階段供應(yīng)鏈排序問(wèn)題.pdf

1、排序論是運(yùn)籌學(xué)的一個(gè)非常重要的分支.供應(yīng)鏈排序是將供應(yīng)鏈管理與排序理論相結(jié)合產(chǎn)生的新領(lǐng)域,將生產(chǎn)調(diào)度和運(yùn)輸整合進(jìn)行研究,使整體目標(biāo)達(dá)到最優(yōu).本文主要研究對(duì)半成品工件進(jìn)行深一步加工的兩階段的供應(yīng)鏈排序問(wèn)題,第一階段:將半成品工件從儲(chǔ)存地運(yùn)輸?shù)焦S;第二階段:將運(yùn)輸?shù)焦S的半成品工件在批處理機(jī)上進(jìn)行加工.為了方便起見(jiàn),我們稱此問(wèn)題為TBS問(wèn)題.由于在現(xiàn)實(shí)生活中,特別是在鋼鐵行業(yè)中,工件的加工時(shí)間通常具有惡化效應(yīng),所以帶有惡化效應(yīng)的供應(yīng)鏈排序

2、的模型具有很重要的研究意義.本文依據(jù)TBS問(wèn)題為背景,討論了幾個(gè)帶有惡化效應(yīng)的TBS問(wèn)題.
　　論文主要結(jié)構(gòu)安排如下:
　　第一章主要介紹了排序的一系列相關(guān)問(wèn)題、算法復(fù)雜性以及本文所需要的基礎(chǔ)知識(shí),相關(guān)問(wèn)題的研究現(xiàn)狀,并對(duì)本文的主要工作從總體上進(jìn)行了介紹.
　　第二章主要研究了具有惡化效應(yīng)的TBS問(wèn)題:工件分為冷工件和熱工件,其中冷工件的加工時(shí)間大于熱工件的加工時(shí)間,如果工件的等待時(shí)間超過(guò)給定的臨界點(diǎn),工件為冷工件,即

3、工件具有惡化效應(yīng),否則為熱工件.加工時(shí)批加工時(shí)間由批內(nèi)加工時(shí)間最長(zhǎng)工件決定,即并行批加工,每批加工費(fèi)用恒定.我們的研究背景為運(yùn)輸階段只有一輛車,加工階段機(jī)器數(shù)量不限,對(duì)如下兩個(gè)目標(biāo)進(jìn)行研究:（1）極小化總完工時(shí)間與加工費(fèi)用之和;（2）極小化最大延誤與加工費(fèi)用之和.證明了這兩個(gè)問(wèn)題都是強(qiáng)NP-hard的,并分別分析了每個(gè)問(wèn)題的特殊情形,給出了多項(xiàng)式時(shí)間算法,并對(duì)一般問(wèn)題給出了近似算法.
　　第三章令批加工費(fèi)用不是恒定的,而是由批加工

4、時(shí)間決定,通常批加工時(shí)間長(zhǎng)的加工批加工費(fèi)用也高,同時(shí)也考慮了工件從0時(shí)刻到開(kāi)始被加工這段時(shí)間具有庫(kù)存費(fèi)用.我們對(duì)如下兩個(gè)問(wèn)題進(jìn)行了研究:（1）運(yùn)輸階段只有一輛車,加工階段批處理機(jī)數(shù)量不限的背景下,目標(biāo)為極小化工件的庫(kù)存費(fèi)用與加工費(fèi)用之和;（2）運(yùn)輸階段有多輛相同的車,加工階段批處理機(jī)數(shù)量不限的背景下,目標(biāo)為極小化工件的庫(kù)存費(fèi)用與加工費(fèi)用之和.我們證明了這兩個(gè)問(wèn)題均為強(qiáng)NP-hard的,分別對(duì)問(wèn)題的特殊情形進(jìn)行了分析,并對(duì)一般問(wèn)題給出了近