求解作業(yè)車間調(diào)度問(wèn)題的元啟發(fā)式算法.pdf

1、作業(yè)車間調(diào)度問(wèn)題是最難的組合優(yōu)化問(wèn)題之一，已被證明是NP-Hard問(wèn)題，它的求解對(duì)于NP-hard問(wèn)題的求解將有很大的啟發(fā)和推動(dòng)作用。由于求解作業(yè)車間調(diào)度問(wèn)題有著巨大的理論和現(xiàn)實(shí)意義，它已經(jīng)成為了學(xué)術(shù)界的研究熱點(diǎn)。
　　遺傳算法是一種有效的求解車間調(diào)度問(wèn)題的元啟發(fā)式算法，遵從“適者生存，遺傳進(jìn)化”準(zhǔn)則，但其在求解過(guò)程中種群容易過(guò)早收斂。針對(duì)于遺傳算法過(guò)早收斂的缺點(diǎn)，本文引入了個(gè)體間分散度概念與其計(jì)算方法，提出了一種基于分散度的多種

2、群遺傳算法。在多種群遺傳算法中引入分散種群來(lái)防止種群過(guò)早收斂。在闡述了算法過(guò)程及算法設(shè)計(jì)的關(guān)鍵部分后，使用國(guó)際基準(zhǔn)實(shí)例測(cè)試多種群遺傳算法的搜索性能，驗(yàn)證該算法相比傳統(tǒng)的遺傳算法有著更好的搜索性能。
　　禁忌搜索算法是局部搜索算法中一種有效的求解車間調(diào)度問(wèn)題算法。算法時(shí)間復(fù)雜度較小，搜索效率較高，但禁忌搜索算法容易陷入局部最優(yōu)解和搜索死循環(huán)中。為使算法有更好的跳出局部最優(yōu)和循環(huán)搜索能力，本文通過(guò)引入了分散度概念，設(shè)計(jì)了一種新的更新精

3、華解集策略和一種禁忌表長(zhǎng)度動(dòng)態(tài)變化策略。并用國(guó)際基準(zhǔn)算例對(duì)這兩種策略進(jìn)行測(cè)試，驗(yàn)證了這兩種策略對(duì)傳統(tǒng)的禁忌搜索算法性能上有很大程度上的改進(jìn)。
　　單一的近似算法對(duì)作業(yè)車間調(diào)度問(wèn)題求解能力有限，而兩種或多種算法的混合算法具有更好的搜索能力。本文中將多種群遺傳算法與改進(jìn)型禁忌搜索算法組成一種多種群遺傳禁忌混合算法。算法通過(guò)遺傳算法的分散搜索與禁忌搜索算法的集中搜索來(lái)提高對(duì)作業(yè)車間調(diào)度問(wèn)題的求解能力。最后使用國(guó)際基準(zhǔn)算例對(duì)算法測(cè)試，發(fā)現(xiàn)