發(fā)布時間：2021-01-30 03:24

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

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

【文章頁數】：133 頁

【學位級別】：博士

【部分圖文】：

車間調度問題中各模型之間關系

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

我們看到，當工件數增加機器數減少時，DSJF啟發(fā)式和FCFS規(guī)則的目標函數值越來越接近最優(yōu)解。對于中等規(guī)模問題，DSJF啟發(fā)式的性能要優(yōu)于FCFS規(guī)則。圖3.4比較了5臺機器，Rt=l時，二者的比值。一一黯一一一一一一一目目目 目目目DSJFFF .........FCFSSS50叫祠門﹄圖3.4當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當m二5，n=1000時，DsJF啟發(fā)式與FCFS規(guī)則比較 Fig.3.5TheeomParisonofD


本文編號：3008144