基于微粒群和蛙跳算法的流水線調(diào)度問題研究.pdf

1、生產(chǎn)調(diào)度問題一個具有廣泛應(yīng)用背景和重要理論價值的組合優(yōu)化問題,是許多實(shí)際生產(chǎn)調(diào)度過程的簡化模型。它具有建模復(fù)雜性、計(jì)算復(fù)雜性、動態(tài)多約束、多目標(biāo)性等特點(diǎn),并已被證明屬NP完全問題。生產(chǎn)調(diào)度問題的核心是模型和算法,其中有效的調(diào)度算法是生產(chǎn)調(diào)度問題的重要研究內(nèi)容。蛙跳算法和微粒群算法是一種模擬青蛙和鳥群覓食的仿生算法,具有流程簡單易實(shí)現(xiàn)、需要調(diào)節(jié)的參數(shù)少、較強(qiáng)的全局收斂能力和魯棒性等優(yōu)勢。本文用微粒群和蛙跳算法解決批量流水線調(diào)度問題、多目標(biāo)

2、無等待流水線調(diào)度問題和批量無等待流水線調(diào)度問題。研究內(nèi)容如下:
　　1.綜述了生產(chǎn)調(diào)度理論的特點(diǎn)、分類、研究現(xiàn)狀和調(diào)度方法的發(fā)展,介紹了微粒群算法和蛙跳算法的研究現(xiàn)狀。
　　2.建立了批量流水線調(diào)度問題、多目標(biāo)無等待流水線調(diào)度問題和批量無等待調(diào)度問題的數(shù)學(xué)模型,給出了指標(biāo)函數(shù)的計(jì)算公式。介紹了標(biāo)準(zhǔn)微粒群算法的蛙跳算法。
　　3.利用連續(xù)微粒群算法求解基于交貨期的批量流水線調(diào)度問題。采用最小位置值規(guī)則,使具有連續(xù)本質(zhì)的微

3、粒群算法能直接應(yīng)用于調(diào)度問題,同時針對微粒群算法容易陷入局部最優(yōu)的缺陷,利用模擬退火算法的概率突跳機(jī)制改進(jìn)其優(yōu)化性能,設(shè)計(jì)了三種微粒群模擬退火混合算法。
　　4.利用離散微粒群優(yōu)化求解以E/T指標(biāo)為目標(biāo)值的批量流水線調(diào)度問題。采用了基于工序的編碼方式,設(shè)計(jì)了新的粒子生成公式,從而使微粒群算法可以直接應(yīng)用于調(diào)度問題。同時,針對微粒群算法容易陷入局部最優(yōu)的缺陷,將其與模擬退火算法結(jié)合,得到了改進(jìn)的微粒群優(yōu)化算法。
　　5.提出了

4、混合離散蛙跳算法解決批量流水線調(diào)度問題。根據(jù)蛙跳算法的原理,采用基于工序的編碼方式并利用兩點(diǎn)交叉操作設(shè)計(jì)了新的位置生成公式,結(jié)合擾動策略、模擬退火概率接受準(zhǔn)則和插入鄰域搜索對該算法進(jìn)行改進(jìn)。
　　6.針對以最大完工時間、最大拖后時間和總流經(jīng)時間為目標(biāo)值的無等待流水線調(diào)度問題的特性,提出了基于Pareto邊界和檔案集的改進(jìn)蛙跳算法。采用兩點(diǎn)交叉方法生成新解,使蛙跳算法能夠直接用于解決調(diào)度問題;同時,利用非支配解集動態(tài)更新群體,改善了

5、群體的質(zhì)量和多樣性;將基于插入鄰域的快速局部搜索算法嵌入到蛙跳算法中對算法進(jìn)行改進(jìn)。
　　7.將離散微粒群和蛙跳算法相結(jié)合解決以最大完工時間為指標(biāo)的批量無等待流水線調(diào)度問題。結(jié)合微粒群算法較強(qiáng)的全局收斂能力和蛙跳算法的較強(qiáng)的深度搜索能力,設(shè)計(jì)了三種混合算法,并將快速插入和快速交換局部搜索算法嵌入到混合算法中,進(jìn)一步增強(qiáng)算法的開發(fā)能力和效率。
　　本論文得到國家自然科學(xué)基金項(xiàng)目:復(fù)雜生產(chǎn)過程基于新型離散群優(yōu)化的混合智能調(diào)度理論