有惡化效應的兩階段供應鏈排序問題.pdf

1、排序論是運籌學的一個非常重要的分支.供應鏈排序是將供應鏈管理與排序理論相結合產生的新領域,將生產調度和運輸整合進行研究,使整體目標達到最優(yōu).本文主要研究對半成品工件進行深一步加工的兩階段的供應鏈排序問題,第一階段:將半成品工件從儲存地運輸到工廠;第二階段:將運輸到工廠的半成品工件在批處理機上進行加工.為了方便起見,我們稱此問題為TBS問題.由于在現實生活中,特別是在鋼鐵行業(yè)中,工件的加工時間通常具有惡化效應,所以帶有惡化效應的供應鏈排序

2、的模型具有很重要的研究意義.本文依據TBS問題為背景,討論了幾個帶有惡化效應的TBS問題.
　　論文主要結構安排如下:
　　第一章主要介紹了排序的一系列相關問題、算法復雜性以及本文所需要的基礎知識,相關問題的研究現狀,并對本文的主要工作從總體上進行了介紹.
　　第二章主要研究了具有惡化效應的TBS問題:工件分為冷工件和熱工件,其中冷工件的加工時間大于熱工件的加工時間,如果工件的等待時間超過給定的臨界點,工件為冷工件,即

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

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