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

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

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

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

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