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

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

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

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

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

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