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

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

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

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

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