一類Flow shop生產(chǎn)調(diào)度問題及其優(yōu)化方法之分析與研究.pdf

1、上海交通大學博士學位論文一類Flowshop生產(chǎn)調(diào)度問題及其優(yōu)化方法之分析與研究姓名：高守瑋申請學位級別：博士專業(yè)：控制理論與控制工程指導教師：張衛(wèi)東20071101水平子路徑概念，把Grabowski定義的關鍵塊普通化和形象化；研究了路徑以及路徑長度的公式，給出了幾種進行路徑變換的方法，推導并擴展了各種不同情況下的下界公式；把單次關鍵路徑構建和動態(tài)關鍵路徑構建兩種方法應用在NEH優(yōu)化算法中，進一步證明了下界公式的有效性。3除基本的算法

2、外，研究了不同的計算makespan的方法并作了證明，給出了這些方法的適用范圍，通過實驗對其進行了驗證。利用flowshop的可逆性質(zhì)，一個排列的makespan可以用前向的完成時間和逆向的完成時間共同來表示。這樣，在評估很多較為相似的排列時，可以盡可能多地利用中間結果，大大減少評估時間，增加算法的效率。在塊插入的鄰域搜索中，利用擴展的關鍵路徑概念給出了評估此時相似排列makespan的快速計算方法。此方法相對于參考文獻中的技巧，更為有

3、效，能節(jié)省更多的時間。4給出了多種解除NEH優(yōu)化方法中ties的方法。綜合考慮所能獲得的最終解的質(zhì)量和所花費的計算時間，幾十年來NEH啟發(fā)式一直是最好的算法。在NEH初始化排列的形成階段和部分排列的構造過程中均存在ties，先前的研究中大都采用最自然的方式解除它們，而本文給出了42種不同的解除NEH中ties的方法。這些改進的算法中，大部分都相對于原始NEH有性能的上提高。此外，文中還給出了使用了ties解除方法之后算法所耗時間的變化，

4、指出耗時并沒有顯著的增加。因此，這些改進后的算法都可以用來替代原來的NEH啟發(fā)式，以便為其它的提高式啟發(fā)式方法和元啟發(fā)式方法提供更好的初始解。5已有的NEH算法研究著重于初始化排列的形成階段，本文將研究集中在對新工件的插入階段?？紤]到原算法中新工件的插入過程等同于鄰域搜索，對于幾種的精簡的鄰域與原NEH算法中的鄰域作了比較分析，又給出了兩種增強的鄰域搜索方法，并取得了較優(yōu)的結果。由于該較優(yōu)的結果是建立在計算花費增加很大的基礎上的，文中給