車間調(diào)度問題是指被調(diào)度的工件需要在不同的機器上進行加工,每臺機器同時最多只能加工一個工件,而每個工件同時也最多只能在一臺機器上加工,工件的加工不允許中斷,問題是確定工件在機器上的加工順序和時間,使得目標(biāo)函數(shù)最優(yōu)化。由于車間調(diào)度問題廣泛存在于制造業(yè)和物流系統(tǒng)中,而且大多數(shù)車間調(diào)度問題都是NP難的,因此探討問題的啟發(fā)式進行近似求解成為學(xué)術(shù)界和工業(yè)界的主要研究手段。如何從理論上分析和評價啟發(fā)式的性能是調(diào)度領(lǐng)域具有挑戰(zhàn)性的研究課題。本文對流水車間和開放車間兩類典型車間調(diào)度模型進行了研究,分別設(shè)計了新的啟發(fā)式并從理論上對這些啟發(fā)式進行了漸近分析,針對問題已有的一些典型啟發(fā)式從理論上進行了漸近分析和最壞情況分析（離線）或最壞競爭分析（在線）。最后通過數(shù)值實驗仿真驗證了所分析的調(diào)度啟發(fā)式的性能。具體內(nèi)容概括如下：1)針對流水車間最小化最大完工時間問題,提出了單個工件優(yōu)先（SJF）啟發(fā)式,并證明了當(dāng)問題規(guī)模趨近于無窮大時該啟發(fā)式是漸近最優(yōu)的。為了進一步從數(shù)值上對提出的啟發(fā)式進行評價,提出了一個新的下界,證明了該下界的漸近最優(yōu)性,并指出其最壞情況比為機器數(shù)m,且為緊界。最后,通過數(shù)值實驗仿真與所提出的下... 

【文章來源】：東北大學(xué)遼寧省 211工程院校 985工程院校 教育部直屬院校

【文章頁數(shù)】：133 頁

【學(xué)位級別】：博士

【部分圖文】：

車間調(diào)度問題中各模型之間關(guān)系

圖2.2比值的下降趨勢 Fig.2.2Thedeereasingtrendoftheratios從圖2.2中，可以觀察到，隨著機器數(shù)的減少，比值越接近于1，換句話說，目標(biāo)函數(shù)值隨著機器數(shù)的減少而越來越接近其下界值。這是因為機器數(shù)越少，排序過程中產(chǎn)生的空閑時間越少，從而減小了目標(biāo)函數(shù)值與其相應(yīng)的下界值之間的誤差。對于固定的機器數(shù)，前面已經(jīng)證明了隨著工件數(shù)的增長，目標(biāo)函數(shù)值越來越接近其下界值。2.7本章小結(jié)本部分針對流水車間最小化最大完工時間問題，提出了SJF啟發(fā)式，并證明了當(dāng)問題規(guī)模趨近于無窮大時

我們看到，當(dāng)工件數(shù)增加機器數(shù)減少時，DSJF啟發(fā)式和FCFS規(guī)則的目標(biāo)函數(shù)值越來越接近最優(yōu)解。對于中等規(guī)模問題，DSJF啟發(fā)式的性能要優(yōu)于FCFS規(guī)則。圖3.4比較了5臺機器，Rt=l時，二者的比值。一一黯一一一一一一一目目目 目目目DSJFFF .........FCFSSS50叫祠門﹄圖3.4當(dāng)m一5，Rt=1時，DsJF啟發(fā)式與FCFS規(guī)則比較 Fig.3.4TheeomParisonofDSJFheuristiewithFCFSmarinerwhenm=sandRt=l‘‘‘’。551一.磊一一-一一一刁 刁;;;:……妞。羹羹羹羹羹羹羹 羹日日日日 日日日 515RtttDSJF ...........FcFSSSSS 1.055 1.05毖 1.045悶曰舀 1.04圖3.5當(dāng)m二5，n=1000時，DsJF啟發(fā)式與FCFS規(guī)則比較 Fig.3.5TheeomParisonofD


本文編號：3008144