面向柔性作業(yè)車間調(diào)度的改進(jìn)混合蛙跳算法*

王玉芳，繆 昇，葛嘉榮

(南京信息工程大學(xué) a.江蘇省大氣環(huán)境與裝備技術(shù)協(xié)同創(chuàng)新中心;b.自動(dòng)化學(xué)院;c.江蘇省大數(shù)據(jù)分析技術(shù)重點(diǎn)實(shí)驗(yàn)室,南京 210044)

0 引言

柔性作業(yè)車間調(diào)度問題(flexible job-shop scheduling problem,FJSP)作為作業(yè)車間調(diào)度問題(job-shop scheduling problem,JSP)的一個(gè)分支,它打破了機(jī)器唯一的限制,即待加工工件可以在可選機(jī)器集中選擇一臺(tái)或者多臺(tái)機(jī)器進(jìn)行加工，這無疑更加符合當(dāng)前復(fù)雜的生產(chǎn)制造環(huán)境，因此FJSP受到了越來越多的關(guān)注,并取得重大進(jìn)展[1-4]。

作為一個(gè)典型的NP-Hard難題,在過去的30年中,隨著科學(xué)技術(shù)的發(fā)展,許多的算法被用于解決這類問題,諸如遺傳算法[5]、粒子群算法[6]、模擬退火算法[7]、禁忌搜索算法[8]等,這些算法在求解FJSP上都取得了良好的效果。基于這類智能算法的啟發(fā),近年來,也是有越來越多的仿生智能算法被提出,并且在解決FJSP上展現(xiàn)了優(yōu)越的效果,連裕翔等[9]提出了一種改進(jìn)的Jaya算法,融合M.G和N7兩種鄰域結(jié)構(gòu)的禁忌搜索算法,使混合算法在分散搜索與集成搜索之間達(dá)到平衡,在解決FJSP上顯示出了良好的性能。趙詩奎[10]提出一種融合改進(jìn)鄰域結(jié)構(gòu)的混合算法,結(jié)合關(guān)鍵工序設(shè)計(jì)了相應(yīng)的移動(dòng)操作,對(duì)已有鄰域結(jié)構(gòu)進(jìn)行了優(yōu)化與擴(kuò)展,提高了鄰域結(jié)構(gòu)的精準(zhǔn)有效性。

蛙跳算法(shuffled frog leaping algorithm,SFLA)作為一種新型的仿生物學(xué)智能優(yōu)化算法，具有概念簡(jiǎn)單，調(diào)整的參數(shù)少,計(jì)算速度快,全局搜索尋優(yōu)能力強(qiáng),易于實(shí)現(xiàn)的特點(diǎn)[11-12]。張曉星等[13]構(gòu)建了以最大完工時(shí)間和總加工能耗最小為優(yōu)化目標(biāo)調(diào)度模型混合蛙跳算法,設(shè)計(jì)了多種局部搜索操作以及鄰域操作來防止算法陷入局部最優(yōu),但在種群初始化時(shí)并未考慮啟發(fā)式規(guī)則,這就大大削弱了算法的性能，延長(zhǎng)了算法尋找到最優(yōu)解的時(shí)間。……