基于適應(yīng)度地形理論的集成式工藝規(guī)劃與車間調(diào)度方法研究.pdf

1、集成式工藝規(guī)劃與車間調(diào)度（Integrated Process Planning and Scheduling, IPPS）問題是一類經(jīng)典的車間調(diào)度問題，并已被證明為NP-Complete問題。該類問題的適應(yīng)度地形非常復(fù)雜，傳統(tǒng)優(yōu)化算法難以有效對其進(jìn)行求解，同時大部分國際標(biāo)準(zhǔn)測試問題還遠(yuǎn)未求得最優(yōu)解，因此，對IPPS問題求解方法的研究任重道遠(yuǎn)，該研究重點(diǎn)包括兩方面的內(nèi)容：一是對算法的流程和操作方法進(jìn)行有效地改進(jìn)；二是在研究該問題適應(yīng)度地

2、形的基礎(chǔ)上，結(jié)合已有的優(yōu)化算法，設(shè)計(jì)高效的混合優(yōu)化算法。
　　本文在結(jié)合IPPS問題求解方法已有研究的基礎(chǔ)上，提出了基于改進(jìn)遺傳算法的IPPS問題高效求解方法。通過對遺傳算法的特點(diǎn)進(jìn)行分析的基礎(chǔ)上，結(jié)合IPPS問題的本質(zhì)特點(diǎn)，對算法的求解流程進(jìn)行了改進(jìn)，同時對算法的編碼、更新算子等要素進(jìn)行了合理設(shè)計(jì)，實(shí)驗(yàn)表明該方法取得了較好的效果。
　　接著，以典型實(shí)例為對象，對IPPS問題的適應(yīng)度地形進(jìn)行了深入的研究。通過引入Logist

3、ic模型的概念對IPPS問題解的結(jié)構(gòu)進(jìn)行了統(tǒng)計(jì)分析，發(fā)現(xiàn)該問題的適應(yīng)度地形符合Logistic模型分布，并通過實(shí)驗(yàn)證明該類問題的Logistic模型具有很高的分布穩(wěn)定性?；贗PPS問題的Logistic模型分布，對局部搜索中的鄰域結(jié)構(gòu)進(jìn)行了深入研究和分析，為局部搜索算法設(shè)計(jì)優(yōu)良的鄰域結(jié)構(gòu)提供了較好的依據(jù)。
　　基于以上研究成果，設(shè)計(jì)了高效的基于變鄰域搜索（Variable Neighborhood Search,VNS）的局部優(yōu)

4、化算法，并將其嵌入改進(jìn)了的遺傳算法中，提出了求解 IPPS問題新的高效混合遺傳變鄰域搜索（GAVNS）算法。該算法能較好地平衡全局搜索能力和局部搜索能力，彌補(bǔ)了單一算法的劣勢，使其在求解復(fù)雜IPPS問題時變得更加高效。通過該算法對國際通用的Kim標(biāo)準(zhǔn)測試集的24個問題進(jìn)行求解，刷新了9個問題的世界最好解，另有12個已獲得最優(yōu)解，實(shí)驗(yàn)結(jié)果表明該算法能很有效地求解IPPS問題。
　　結(jié)合以上研究成果，本文設(shè)計(jì)并開發(fā)了IPPS原型系統(tǒng)，