啟發(fā)式算法及其在同順序流水作業(yè)問題中的應用.pdf

1、對于NP-完全問題，通常不能有效地求得問題的最優(yōu)解，而是使用啟發(fā)式算法在可接受的時間內(nèi)找到問題的盡量好的解。車間調(diào)度(shop scheduling)問題具有約束性、非線性、多極小性、大規(guī)模性、多目標性等特點，一般屬于NP-完全問題，目標解的搜索涉及解空間的組合爆炸。線性規(guī)劃、分支定界等傳統(tǒng)方法對于稍大規(guī)模的車間調(diào)度問題的求解無能為力，因此，通常使用啟發(fā)式算法求解。 車間調(diào)度是一個交叉性研究領域，吸引了運籌學、數(shù)學、管理學、決策

2、學、自動化、計算機等領域的眾多專家學者，同時，車問調(diào)度與控制技術是實現(xiàn)生產(chǎn)高效率、高柔性和高可靠性的關鍵，有效實用的調(diào)度方法和優(yōu)化技術的研究與應用已成為先進制造技術的基礎，因此研究求解車間調(diào)度問題的啟發(fā)式算法有現(xiàn)實意義。 本文研究了啟發(fā)式算法在一類經(jīng)典的車間調(diào)度問題--同順序流水作業(yè)--中的應用，取得的主要研究成果如下： 1.針對以最小化最大完工時間為目標的同順序流水作業(yè)，在著名的NEH算法的基礎上，提出了一個改進的構造

3、性算法NEH-D。NEH-D算法主要從兩點改進了NEH算法：首先使用一個更優(yōu)的排序規(guī)則，在該規(guī)則中，不僅考慮了工件的總加工時間，而且考慮了這些加工時間的標準方差；其次，使用了一個消解插入沖突的策略。使用的優(yōu)先規(guī)則有利于改進算法的性能：使用的消解插入沖突的策略對算法性能的改進起關鍵的作用。實驗表明，NEH-D算法的性能優(yōu)于NEH算法的性能，也優(yōu)于最近提出的NEHKK算法和NEHKK1算法的性能； 2.研究了求解目標為最小化最大完工

4、時間的禁忌搜索算法的幾個要素對算法性能的影響。結果表明提出的搜索策略對算法性能有較明顯的影響，而提出的禁忌表結構、禁忌狀態(tài)和不同的初始解對算法的性能沒有明顯的影響； 3.針對以最小化總流程時間為目標的同順序流水作業(yè)，提出了一個迭代局部搜索算法。該算法對初始解不是很敏感；當算法陷于局部極小時，需要對當前最優(yōu)解做擾動并繼續(xù)搜索，此時擾動強度對算法的性能有叫顯的影響。實驗表明該算法的性能優(yōu)十當前已有的算法，且該算法改進了90個基準問題

5、中47個問題的當前最優(yōu)解： 4.針對求解最小化最大完工時間和總流程時間的多目標同順序流水作業(yè)，提出了一個多目標局部搜索算法。針對兩個目標，用現(xiàn)有的構造性算法牛成兩個解，作為該算法的初始解，然后從這兩個初始解出發(fā)，以貪婪的方式求出新的Pareto最優(yōu)解集，持續(xù)改進Pareto前沿。選擇新的Pareto解的條件是該解既不被原解支配，也不被產(chǎn)生原解的解支配，同時對某個目標改進最大。當所有的解都陷入局部極小時，擾動已得到的Pareto解